Binární vyhledávací strom (BST) s příkladem

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 reprezentovány ve vztahu rodič-dítě
• Každý nadřazený uzel může mít nula podřízených uzlů nebo maximálně dva poduzly nebo podstromy na levé a pravé straně.
• Každý podstrom, také známý jako binární vyhledávací strom, má podvětve napravo a nalevo od sebe.
• Všechny uzly jsou propojeny pomocí párů klíč–hodnota.
• Klíče uzlů přítomných v levém podstromu jsou menší než klíče jejich nadřazeného uzlu
• Podobně klíče uzlů levého podstromu mají menší hodnoty než klíče jejich nadřazeného uzlu.

1. Je zde hlavní uzel nebo nadřazená úroveň 11. Pod ním jsou levý a pravý uzel/větve s vlastními hodnotami klíče
2. Pravý podstrom má hodnoty klíčů větší než nadřazený uzel
3. Levý podstrom má hodnoty než nadřazený uzel

Proč potřebujeme binární vyhledávací strom?

• Dva hlavní faktory, díky kterým je binární vyhledávací strom optimálním řešením jakýchkoli reálných problémů, jsou rychlost a přesnost.
• Vzhledem k tomu, že binární vyhledávání je ve větvím podobném formátu s vztahy rodič-dítě, algoritmus ví, ve kterém umístění stromu je třeba prvky hledat. Tím se sníží počet porovnání párů klíč–hodnota, které musí program provést, aby nalezl 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í, kterou stranu stromu má hledat. Důvodem je, že levý podstrom je vždy menší než nadřazený uzel a pravý podstrom má hodnoty vždy stejné nebo větší než nadřazený uzel.
• BST se běžně používá k implementaci komplexního vyhledávání, robustní herní logiky, činností automatického dokončování a grafiky.
• Algoritmus efektivně podporuje operace jako vyhledávání, vkládání a mazání.

Typy binárních stromů

Tři druhy binárních stromů jsou:

• Kompletní binární strom: Všechny úrovně ve stromech jsou plné možných výjimek poslední úrovně. Podobně jsou všechny uzly plné a směřují zcela vlevo.
• Úplný 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ě potomky. Kromě toho existuje stejná úroveň každého poduzlu.

Další informace o Binární strom v datové struktuře Pokud máte zájem.

Jak funguje binární vyhledávací strom?

Strom má vždy kořenový uzel a další podřízené uzly, ať už vlevo nebo vpravo. 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 podstromu.

V závislosti na prvku, který má být vložen, prohledán nebo odstraněn, po porovnání může algoritmus snadno vypustit 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: vyhledá prvek z binárního stromu
• Vložit: přidá prvek do binárního stromu
• Smazat: odstranění prvku z binárního stromu

Každá operace má svou vlastní strukturu a způsob provedení/analýzy, ale nejsložitější ze všech je operace Delete.

Hledat Operavání

Analytický strom vždy zahajte v kořenovém uzlu a poté přejděte dále do pravého nebo levého podstromu 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.

1. Prvek, který se má hledat, je 10
2. Porovnejte prvek s kořenovým uzlem 12, 10 < 12, proto se přesunete do levého podstromu. Není třeba analyzovat pravý podstrom
3. Nyní porovnejte 10 s uzlem 7, 10 > 7, takže přejděte do pravého podstromu
4. Poté porovnejte 10 s dalším uzlem, což je 9, 10 > 9, podívejte se do pravého potomka podstromu
5. 10 odpovídá hodnotě v uzlu, 10 = 10, vrátí hodnotu uživateli.

Pseudokód pro vyhledávání v BST

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

Vložit Operavání

Toto je velmi přímočará operace. Nejprve se vloží kořenový uzel a poté se porovná další hodnota s kořenovým uzlem. Pokud je hodnota větší než kořen, přidá se do pravého podstromu, a pokud je menší než kořen, přidá se do levého podstromu.

1. Existuje seznam 6 prvků, které je třeba vložit do BST v pořadí zleva doprava
2. 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
3. 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ístěte jej jako pravé dítě z 12, 5 < 12 & 5 < 7, tedy jako levé dítě ze 7. Nyní porovnejte 10, 10 je < 12 & 10 je > 7 & 10 je > 9, místo 10 jako pravý podstrom 9.

Pseudokód pro vložení uzlu do BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Vymazat Operace

Pro odstranění uzlu z BST existují některé případy, např. odstranění kořene nebo odstranění listového uzlu. Také po odstranění kořene musíme myslet na kořenový uzel.

Řekněme, že chceme odstranit listový uzel, můžeme ho smazat, ale pokud chceme smazat kořen, musíme nahradit hodnotu kořene jiným uzlem. Vezměme si následující příklad:

• Případ 1 – Uzel s nulovými potomky: toto je nejjednodušší situace, stačí smazat uzel, který nemá žádné další potomky napravo ani nalevo.
• Případ 2 – Uzel s jedním podřízeným uzlem: jakmile uzel odstraníte, jednoduše připojte jeho podřízený uzel s nadřazeným uzlem odstraněné hodnoty.
• Případ 3 Node se dvěma dětmi: toto je nejobtížnější situace a funguje podle následujících dvou pravidel
• 3a – V předchůdci objednávky: musíte odstranit uzel se dvěma potomky a nahradit jej největší hodnotou v levém podstromu odstraněného uzlu
• 3b – V pořadí následník: musíte odstranit uzel se dvěma potomky a nahradit jej největší hodnotou v pravém podstromu odstraněného uzlu

1. Toto je první případ odstranění, kdy odstraníte uzel, který nemá žádné potomky. Jak můžete vidět na obrázku, 19, 10 a 5 nemají žádné děti. Ale smažeme 19.
2. Odstraňte hodnotu 19 a odeberte odkaz z uzlu.
3. Podívejte se na novou strukturu BST bez 19

1. Toto je druhý případ odstranění, kdy odstraníte uzel, který má 1 potomka, jak můžete vidět na diagramu, že 9 má jednoho potomka.
2. Odstraňte uzel 9 a nahraďte jej jeho potomkem 10 a přidejte odkaz od 7 do 10
3. Podívejte se na novou strukturu BST bez 9

1. Zde odstraníte uzel 12, který má dva potomky
2. K odstraně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 z 12.
3. Odstraňte uzel 12 a nahraďte jej 10, protože je to největší hodnota v levém podstromu
4. Prohlédněte si novou strukturu BST po odstranění 12

1. 1 Odstraňte uzel 12, který má dva potomky
2. 2 K odstranění uzlu dojde na základě pravidla In Order Successor, což znamená, že největší prvek v pravém podstromu z 12 jej nahradí.
3. 3 Odstraňte uzel 12 a nahraďte jej 19, protože je to největší hodnota v pravém podstromu
4. 4 Prohlédněte si novou strukturu BST po odstranění 12

Pseudo kód pro smazání uzlu

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Důležité podmínky

• Vložit: Vloží prvek do stromu/vytvoří strom.
• Hledat: Vyhledá prvek ve stromu.
• Preorder Traversal: Prochází strom předobjednávkovým způsobem.
• Inorder Traversal: Prochází stromem v pořadí.
• Postorder Traversal: Prochází strom způsobem po objednávce.

Shrnutí

• BST je algoritmus pokročilé úrovně, který provádí různé operace založené na porovnání hodnot uzlů s kořenovým uzlem.
• Kterýkoli z bodů v hierarchii rodiče a potomka představuje uzel. Po celou dobu zůstává přítomen 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 nulu, jednoho nebo dva potomky.
• Binární vyhledávací strom usnadňuje primární operace, jako je vyhledávání, vkládání a mazání.
• Delete, protože je nejsložitější, má více případů, například uzel bez potomka, uzel s jedním potomkem a uzel se dvěma potomky.
• Algoritmus se používá v reálných řešeních, jako jsou hry, automatické doplňování dat a grafika.