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

Co je 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 k vrácení hodnoty. BST je navržen na architektuře základního binárního vyhledávacího algoritmu; umožňuje tak rychlejší vyhledávání, vkládání a odebírání uzlů. Díky tomu je program opravdu rychlý a přesný.

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ě jsou klíče uzlů přítomných v pravém podstromu větší než klíče jejich nadřazeného uzlu.

1. Existuje hlavní uzel neboli nadřazená úroveň 11. Pod ním jsou levé a pravé uzly/větve s vlastními klíčovými hodnotami.
2. Pravý podstrom má klíčové hodnoty větší než nadřazený uzel.
3. Levý podstrom má menší počet klíčových hodnot než nadřazený uzel.

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

• Dva hlavní faktory, které dělají z binárního vyhledávacího stromu optimální řešení jakéhokoli problému z reálného světa, 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 je prohledávaný prvek větší nebo menší než nadřazený uzel, uzel ví, na které straně stromu má prohledávat. Důvodem je, že levý podstrom je vždy menší než nadřazený uzel a pravý podstrom má hodnoty vždy rovné 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 stromu jsou plné, s možnou výjimkou na poslední úrovni. Podobně jsou plné všechny uzly, směřující úplně doleva.
• Úplný binární strom: Všechny uzly mají 2 podřízené uzly kromě listu.
• Vyvážený nebo dokonalý binární strom: Ve stromové struktuře mají všechny uzly dva potomky. Kromě toho je pro každý poduzel stejná úroveň.

Více informací 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, může algoritmus po porovnání snadno odstranit 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í:

• Vyhledávání: vyhledá prvek z binárního stromu.
• Vložit: přidá prvek do binárního stromu.
• Vymazat: odstraní prvek 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í

Analýzu stromu vždy začněte v kořenovém uzlu a poté se přesuňujte dále k pravému nebo levému podstromu kořenového uzlu v závislosti na tom, zda je prvek, který má být nalezen, menší nebo větší než kořen.

1. Hledaný prvek je 10.
2. Porovnejte prvek s kořenovým uzlem 12, 10 < 12, a 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 se přesuňme do pravého podstromu.
4. Pak porovnejte 10 s dalším uzlem, který je 9, 10 > 9, a podívejte se do pravého potomka podstromu.
5. 10 odpovídá hodnotě v uzlu, 10 = 10, vrátí hodnotu uživateli.

Nepravý Code 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 s ním porovná další hodnota. 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 umístěte je odpovídajícím způsobem. 19 > 12, umístěte jej jako pravého potomka uzlu 12; 5 < 12 a 5 < 7, proto jej umístěte jako levého potomka uzlu 7. Nyní porovnejte 10, 10 je < 12 a 10 je > 7 a 10 je > 9, umístěte 10 jako pravý podstrom uzlu 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í určité případy, například odstranění kořene nebo odstranění koncového uzlu. Po odstranění kořene musíme také zvážit 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 vpravo ani vlevo.
• Případ 2 – Uzel s jedním potomkem: Jakmile uzel smažete, jednoduše propojte jeho podřízený uzel s nadřazeným uzlem smazané hodnoty.
• Případ 3 – Uzel se dvěma potomky: Toto je nejobtížnější situace a funguje na základě následujících dvou pravidel:
  • 3a – Předchůdce v pořadí: Musíte odstranit uzel se dvěma podřízenými uzly a nahradit ho největší hodnotou v levém podstromu odstraněného uzlu.
  • 3b – Nástupce v pořadí: Musíte smazat uzel se dvěma potomky a nahradit ho nejmenší hodnotou v pravém podstromu smazaného uzlu.

1. Toto je první případ smazání, kdy smažete uzel, který nemá žádné potomky. Jak vidíte na diagramu, 19, 10 a 5 žádné potomky nemají. 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 vidíte na diagramu, 9 má jednoho potomka.
2. Odstraňte uzel 9 a nahraďte ho jeho potomkem 10 a přidejte propojení mezi 7 a 10.
3. Podívejte se na novou strukturu BST bez 9.

1. Zde smažete uzel 12, který má dva potomky.
2. K odstranění uzlu dojde na základě pravidla předchůdců v pořadí, což znamená, že jej nahradí největší prvek v levém podstromu 12.
3. Odstraňte uzel 12 a nahraďte jej číslem 10, protože se jedná o největší hodnotu v levém podstromu.
4. Zobrazit novou strukturu BST po smazání 12.

1. Odstraňte uzel 12, který má dva potomky.
2. K odstranění uzlu dojde na základě pravidla nástupnictví v pořadí, což znamená, že jej nahradí nejmenší prvek v pravém podstromu 12.
3. Odstraňte uzel 12 a nahraďte jej číslem 19, protože se jedná o nejmenší hodnotu v pravém podstromu.
4. Zobrazit novou strukturu BST po smazání 12.

Nepravý Code pro odstraně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, delete the successor
        free(newNode)
    else
        free(y)

Důležité podmínky

• Vložit: Vloží prvek do stromu / vytvoří strom.
• Vyhledávání: Hledá prvek ve stromu.
• Předobjednávkový průchod: Prochází stromem v předběžném pořadí.
• Procházení v pořadí: Prochází stromem v určitém pořadí.
• Procházení poštovní objednávky: Prochází stromem způsobem po pořadí.

Nejčastější dotazy