Co je to binární vyhledávací strom?
Binární vyhledávací strom je pokročilý algoritmus používaný k analýze uzlu, jeho levé a pravé větve, které jsou modelovány ve stromové struktuře a vracejí hodnotu. BST je navržen na architektuře základního algoritmu binárního vyhledávání; proto umožňuje rychlejší vyhledávání, vkládání a odebírání uzlů. Díky tomu je program opravdu rychlý a přesný.
V tomto výukovém programu Datová struktura se naučíte:
- Co je to binární vyhledávací strom?
- Atributy binárního vyhledávacího stromu
- Proč potřebujeme binární vyhledávací strom?
- Druhy binárních stromů
- Jak funguje binární vyhledávací strom?
- Důležité podmínky
Atributy binárního vyhledávacího stromu
BST se skládá z více uzlů a skládá se z následujících atributů:
- Uzly stromu jsou zastoupeny ve vztahu rodič-dítě
- Každý nadřazený uzel může mít nulové podřízené uzly nebo maximálně dva poduzly nebo podstromy na levé a pravé straně.
- Každý dílčí strom, známý také jako binární vyhledávací strom, má dílčí větve vpravo a vlevo od sebe.
- Všechny uzly jsou propojeny páry klíč – hodnota.
- Klíče uzlů přítomných v levém podstromu jsou menší než klíče jejich nadřazeného uzlu
- Podobně mají klíče uzlů levého podstromu nižší hodnoty než klíče jejich nadřazeného uzlu.
- Existuje hlavní uzel nebo nadřazená úroveň 11. Pod ním jsou levé a pravé uzly / větve s vlastními hodnotami klíče
- Pravý podstrom má klíčové hodnoty větší než nadřazený uzel
- Levý podstrom má hodnoty než nadřazený uzel
Proč potřebujeme binární vyhledávací strom?
- Dva hlavní faktory, díky nimž je binární vyhledávací strom optimálním řešením jakýchkoli problémů v reálném světě, jsou rychlost a přesnost.
- Vzhledem k tomu, že binární vyhledávání je ve větvovém formátu se vztahy rodič-dítě, algoritmus ví, ve kterém umístění stromu je nutné prvky prohledávat. Tím se snižuje počet srovnání párů klíč – hodnota, které musí program provést, aby vyhledal požadovaný prvek.
- Navíc v případě, že prvek, který má být prohledán, je větší nebo menší než nadřazený uzel, uzel ví, na které straně stromu má být vyhledán. Důvodem je, že levý podstrom je vždy menší než nadřazený uzel a pravý podstrom má hodnoty vždy stejné nebo vyšší než nadřazený uzel.
- BST se běžně používá k implementaci komplexního vyhledávání, robustní logiky her, aktivit automatického dokončování a grafiky.
- Algoritmus účinně podporuje operace, jako je vyhledávání, vkládání a mazání.
Druhy binárních stromů
Tři druhy binárních stromů jsou:
- Kompletní binární strom: Všechny úrovně na stromech jsou plné možných výjimek poslední úrovně. Podobně jsou všechny uzly plné a směřují zcela vlevo.
- Celý binární strom: Všechny uzly mají 2 podřízené uzly kromě listu.
- Vyvážený nebo dokonalý binární strom: Ve stromu mají všechny uzly dvě děti. Kromě toho existuje stejná úroveň každé poduzlu.
Jak funguje binární vyhledávací strom?
Strom má vždy kořenový uzel a další podřízené uzly, ať už nalevo nebo napravo. Algoritmus provádí všechny operace porovnáním hodnot s kořenem a jeho dalšími podřízenými uzly v levém nebo pravém dílčím stromu.
Závisí na prvku, který má být vložen, prohledán nebo odstraněn, po porovnání může algoritmus snadno upustit levý nebo pravý podstrom kořenového uzlu.
BST primárně nabízí následující tři typy operací pro vaše použití:
- Hledat: prohledá prvek z binárního stromu
- Vložit: přidá prvek do binárního stromu
- Odstranit: odstranění prvku z binárního stromu
Každá operace má svou vlastní strukturu a metodu provádění / analýzy, ale nejsložitější ze všech je operace Odstranit.
Vyhledávací operace
Vždy inicializujte analytický strom v kořenovém uzlu a poté se přesuňte dále na pravý nebo levý podstrom kořenového uzlu v závislosti na tom, zda je prvek, který má být umístěn, menší nebo větší než kořen.
- Prohledávaný prvek je 10
- Porovnejte prvek s kořenovým uzlem 12, 10 <12, proto se přesunete do levého podstromu. Není nutné analyzovat pravý podstrom
- Nyní porovnejte 10 s uzlem 7, 10> 7, takže přejděte do pravého podstromu
- Pak porovnejte 10 s dalším uzlem, což je 9, 10> 9, podívejte se do pravého podřízeného stromu
- 10 shoduje se s hodnotou v uzlu, 10 = 10, vrací hodnotu uživateli.
Operace vložení
Jedná se o velmi přímočarou operaci. Nejprve se vloží kořenový uzel, poté se porovná další hodnota s kořenovým uzlem. Pokud je hodnota větší než root, přidá se do pravého podstromu a pokud je menší než root, přidá se do levého podstromu.
- Existuje seznam 6 prvků, které je třeba vložit do BST v pořadí zleva doprava
- Vložte 12 jako kořenový uzel a porovnejte další hodnoty 7 a 9 pro odpovídající vložení do pravého a levého podstromu
- Porovnejte zbývající hodnoty 19, 5 a 10 s kořenovým uzlem 12 a podle toho je umístěte. 19> 12 umístit jako pravé dítě 12, 5 <12 & 5 <7, tedy umístit jako levé dítě 7.
- Nyní porovnejte 10, 10 je <12 a 10 je> 7 a 10 je> 9, místo 10 jako pravý podstrom 9.
Odstranit operace
Odstranit je nejpokročilejší a nejsložitější ze všech ostatních operací. Existuje několik případů zpracovaných k odstranění v BST.
- Případ 1 - Uzel s nulovými potomky: toto je nejjednodušší situace, stačí odstranit uzel, který nemá žádné další potomky vpravo nebo vlevo.
- Případ 2 - Uzel s jedním podřízeným: Jakmile odstraníte uzel, jednoduše připojte jeho podřízený uzel s nadřazeným uzlem odstraněné hodnoty.
- Případ 3 Uzel se dvěma dětmi: toto je nejtěžší situace a funguje na následujících dvou pravidlech
- 3a - V pořadí předchůdce: musíte odstranit uzel se dvěma podřízenými položkami a nahradit ho největší hodnotou v levém podstromu odstraněného uzlu
- 3b - In Order Successor: musíte odstranit uzel se dvěma potomky a nahradit ho největší hodnotou v pravém podstromu odstraněného uzlu
- Toto je první případ odstranění, ve kterém odstraníte uzel, který nemá žádné potomky. Jak je vidět na obrázku, 19, 10 a 5 nemají žádné děti. Ale odstraníme 19.
- Odstraňte hodnotu 19 a odeberte odkaz z uzlu.
- Zobrazit novou strukturu BST bez 19
- Toto je druhý případ odstranění, ve kterém odstraníte uzel, který má 1 podřízený, jak vidíte na diagramu, že 9 má jedno podřízené.
- Odstraňte uzel 9 a nahraďte jej podřízeným 10 a přidejte odkaz od 7 do 10
- Zobrazit novou strukturu BST bez 9
- Zde budete mazat uzel 12, který má dvě děti
- K vymazání uzlu dojde na základě pravidla předchůdce v pořadí, což znamená, že jej nahradí největší prvek v levém podstromu 12.
- Odstraňte uzel 12 a nahraďte jej 10, protože je to největší hodnota v levém podstromu
- Zobrazit novou strukturu BST po odstranění 12
- 1 Odstraňte uzel 12, který má dvě děti
- 2 Vymazání uzlu proběhne na základě pravidla In Order Successor, což znamená, že největší prvek na pravém podstromu 12 jej nahradí
- 3 Odstraňte uzel 12 a nahraďte jej 19, protože to je největší hodnota v pravém podstromu
- 4 Po odstranění 12 zobrazte novou strukturu BST
Důležité podmínky
- Vložit - Vloží prvek do stromu / vytvoří strom.
- Hledat - Hledá prvek na stromě.
- Předobjednat Traversal - Prochází strom předobjednávkovým způsobem.
- Inorder Traversal - Prochází strom v pořadí.
- Postorder Traversal - Prochází strom post-order způsobem.
souhrn
- BST je pokročilý algoritmus úrovně, který provádí různé operace na základě porovnání hodnot uzlů s kořenovým uzlem.
- Libovolný z bodů v hierarchii rodič-dítě představuje uzel. Po celou dobu zůstává alespoň jeden nadřazený nebo kořenový uzel.
- Existuje levý podstrom a pravý podstrom. Levý podstrom obsahuje hodnoty, které jsou menší než kořenový uzel. Pravý podstrom však obsahuje hodnotu, která je větší než kořenový uzel.
- Každý uzel může mít buď nulu, jedno nebo dvě děti.
- Binární vyhledávací strom usnadňuje primární operace, jako je vyhledávání, vkládání a mazání.
- Smazání, které je nejsložitější, má více případů, například uzel bez potomka, uzel s jedním dítětem a uzel se dvěma podřízenými.
- Algoritmus se používá v reálných řešeních, jako jsou hry, data automatického doplňování a grafika.