Implementace binárního vyhledávacího stromu

2024 Autor: Angel Austin | [email protected]. Naposledy změněno: 2023-12-17 05:20

Binární vyhledávací strom – strukturovaná databáze obsahující uzly, dva odkazy na další uzly, pravý a levý. Uzly jsou objekt třídy, který má data, a NULL je znak, který označuje konec stromu.

Často se označuje jako BST, což má zvláštní vlastnost: uzly větší než kořen jsou umístěny napravo od něj a menší nalevo.

Obecná teorie a terminologie

V binárním vyhledávacím stromě je každý uzel, kromě kořene, spojen přímou hranou z jednoho uzlu do druhého, který se nazývá rodič. Každý z nich může být připojen k libovolnému počtu uzlů, nazývaných děti. Uzly bez "dětí" se nazývají listy (vnější uzly). Prvky, které nejsou listy, se nazývají vnitřní. Uzly se stejným rodičem jsou sourozenci. Nejvyšší uzel se nazývá kořen. V BST přiřaďte prvek ke každému uzlu a ujistěte se, že pro něj mají nastavenou speciální vlastnost.

Terminologie stromu:

Hloubka uzlu je počet hran definovaných od kořene k němu.
Výška uzlu je počet hran definovaných od něj k nejhlubšímu listu.
Výška stromu je určena výškou kořene.
Binární vyhledávací strom je speciální design, poskytuje nejlepší poměr výšky a počtu uzlů.
Výška h s N uzly nejvýše O (log N).

To můžete snadno dokázat spočítáním uzlů na každé úrovni, počínaje od kořene, za předpokladu, že jich obsahuje největší počet: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Vyřešením tohoto pro h dostaneme h=O (log n).

Výhody dřeva:

Odrážejí strukturální vztahy dat.
Slouží k reprezentaci hierarchií.
Zajistěte efektivní instalaci a vyhledávání.
Stromy jsou velmi flexibilní data, která vám umožňují přesouvat podstromy s minimálním úsilím.

Metoda vyhledávání

Obecně platí, že chcete-li zjistit, zda je hodnota v BST, spusťte binární vyhledávací strom u jeho kořene a zjistěte, zda splňuje požadavky:

být u kořene;
být v levém podstromu kořene;
v pravém podstromu kořene.

Pokud není splněn žádný základní registr, provede se rekurzivní vyhledávání v odpovídajícím podstromu. Ve skutečnosti existují dvě základní možnosti:

Strom je prázdný – vrátí hodnotu false.
Hodnota je v kořenovém uzlu – vrátí true.

Je třeba poznamenat, že binární vyhledávací strom s rozvinutým schématem vždy začíná hledat podél cesty od kořene k listu. V horším případě to jde až na list. Nejhorší čas je tedy úměrný délce nejdelší cesty od kořene k listu, což je výška stromu. Obecně v tomto případě potřebujete vědět, jak dlouho trvá vyhledání v závislosti na počtu hodnot uložených ve stromu.

Jinými slovy, existuje vztah mezi počtem uzlů v BST a výškou stromu v závislosti na jeho „tvaru“. V nejhorším případě mají uzly pouze jednoho potomka a vyvážený binární vyhledávací strom je v podstatě propojený seznam. Například:

Tento strom má 5 uzlů a výšku=5. Nalezení hodnot v rozsahu 16-19 a 21-29 bude vyžadovat následující cestu od kořene k listu (uzel obsahující hodnotu 20), tzn., bude to trvat čas úměrný počtu uzlů. V nejlepším případě mají všichni 2 děti a listy jsou umístěny ve stejné hloubce.

Tento binární vyhledávací strom má 7 uzlů a výšku=3. Obecně bude mít strom jako tento (celý strom) výšku přibližně log 2 (N), kde N je počet uzlů ve stromu. Hodnota log 2 (N) je počet, kolikrát (2), kdy lze N vydělit, než se dosáhne nuly.

Shrnutí: nejhorší čas potřebný k hledání v BST je O (výška stromu). Nejhorším případem "lineárního" stromu je O(N), kde N je počet uzlů ve stromu. V nejlepším případě je "úplný" strom O(log N).

BST binární vložka

Zajímalo by mě, kde by měl býtnový uzel se nachází v BST, musíte rozumět logice, musí být umístěn tam, kde jej uživatel najde. Kromě toho si musíte pamatovat pravidla:

Duplikáty nejsou povoleny, pokus o vložení duplicitní hodnoty vyvolá výjimku.
Veřejná metoda vkládání používá pomocnou rekurzivní "pomocnou" metodu ke skutečnému vkládání.
Uzel obsahující novou hodnotu je vždy vložen jako list v BST.
Metoda public insert vrací void, ale pomocná metoda vrací BSTnode. Dělá to proto, aby zvládl případ, kdy je uzel, který je mu předán, null.

Pomocná metoda obecně označuje, že pokud je původní binární vyhledávací strom prázdný, výsledkem je strom s jedním uzlem. V opačném případě bude výsledkem ukazatel na stejný uzel, který byl předán jako argument.

Smazání v binárním algoritmu

Jak můžete očekávat, odstranění prvku zahrnuje nalezení uzlu, který obsahuje hodnotu, která má být odstraněna. V tomto kódu je několik věcí:

BST používá pomocnou, přetíženou metodu mazání. Pokud hledaný prvek není ve stromu, pak bude pomocná metoda nakonec volána s n==null. To se nepovažuje za chybu, strom se v tomto případě prostě nezmění. Pomocná metoda delete vrací hodnotu – ukazatel na aktualizovaný strom.
Když je list odstraněn, odstranění z binárního vyhledávacího stromu nastaví odpovídající podřízený ukazatel jeho rodiče na hodnotu null nebo kořen na hodnotu null, pokud je odstraněnuzel je kořen a nemá žádné potomky.
Všimněte si, že volání delete musí být jedno z následujících: root=delete (kořen, klíč), n.setLeft (delete (n.getLeft (), klíč)), n.setRight (delete(n. getRight(), klíč)). Ve všech třech případech je tedy správné, že metoda delete jednoduše vrátí hodnotu null.
Když je hledání uzlu obsahující hodnotu, která má být odstraněna, úspěšné, existují tři možnosti: uzel, který se má odstranit, je list (nemá žádné potomky), uzel, který se má odstranit, má jednoho potomka, má dva děti.
Když má odstraňovaný uzel jednoho potomka, můžete ho jednoduše nahradit potomkem a vrátit ukazatel na dítě.
Pokud má uzel, který má být odstraněn, nula nebo 1 potomka, bude metoda odstranění "sledovat cestu" od kořene k tomuto uzlu. Nejhorší čas je tedy úměrný výšce stromu, pro vyhledávání i vkládání.

Pokud má uzel, který má být odebrán, dva potomky, provedou se následující kroky:

Najděte uzel, který chcete odstranit, podle cesty od kořenového adresáře k němu.
Najděte nejmenší hodnotu v v pravém podstromu a pokračujte po cestě k listu.
Rekurzivně odstraňte hodnotu v, postupujte stejnou cestou jako v kroku 2.
V nejhorším případě se tedy cesta od kořene k listu provádí dvakrát.

Pořadí přejezdů

Traversal je proces, který navštíví všechny uzly ve stromu. Protože binární vyhledávací strom C je nelineární datová struktura, neexistuje žádné jedinečné procházení. Například někdy několik algoritmů procházeníseskupeny do následujících dvou typů:

hloubka křížení;
první průchod.

Existuje pouze jeden druh křížení šířky – obcházení úrovně. Toto procházení navštěvuje uzly o úroveň níže a vlevo, nahoře a vpravo.

Existují tři různé typy hloubkových přechodů:

Předběžná objednávka – nejprve navštivte rodiče a poté levé a pravé dítě.
Passing InOrder – návštěva levého dítěte, poté rodiče a pravého dítěte.
Past the PostOrder – návštěva levého dítěte, poté pravého dítěte a poté rodiče.

Příklad čtyř průchodů binárním vyhledávacím stromem:

Předobjednávka – 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
V pořadí – 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
PostOrder – 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
Pořadí úrovní – 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Obrázek ukazuje pořadí, ve kterém jsou uzly navštěvovány. Číslo 1 je první uzel v konkrétním průchodu a číslo 7 je poslední uzel.

Tyto obecné průchody lze reprezentovat jako jeden algoritmus za předpokladu, že každý uzel je navštíven třikrát. Eulerova prohlídka je procházka kolem binárního stromu, kde je každá hrana považována za zeď, kterou uživatel nemůže přejít. V této procházce bude každý uzel navštíven buď vlevo, nebo níže nebo vpravo. Eulerova cesta, která navštěvuje uzly vlevo, způsobí vynechání předložky. Když navštívíte uzly níže, projdou se v pořadí. A když jsou navštíveny uzly vpravo - dostatkrok za krokem obejít.

Navigace a ladění

Abyste si usnadnili navigaci ve stromu, vytvořte funkce, které nejprve zkontrolují, zda se jedná o levé nebo pravé dítě. Chcete-li změnit polohu uzlu, musí být snadný přístup k ukazateli v nadřazeném uzlu. Správná implementace stromu je velmi obtížná, takže musíte znát a používat ladicí procesy. Binární vyhledávací strom s implementací má často ukazatele, které ve skutečnosti neoznačují směr cesty.

Abyste to všechno pochopili, používá se funkce, která kontroluje, zda může být strom správný, a pomáhá najít mnoho chyb. Například kontroluje, zda je nadřazený uzel podřízeným uzlem. S příkazem assist(is_wellformed(root)) lze mnoho chyb zachytit předčasně. Pomocí několika daných bodů přerušení v rámci této funkce můžete také přesně určit, který ukazatel je špatný.

Funkce Konsolenausgabe

Tato funkce vyprázdní celý strom do konzole a je proto velmi užitečná. Pořadí, ve kterém se provádí cíl výstupu stromu, je:

Abyste to mohli udělat, musíte nejprve určit, jaké informace budou výstupem přes uzel.
A také potřebujete vědět, jak je strom široký a vysoký, abyste mohli ponechat prostor.
Následující funkce vypočítají tyto informace pro strom a každý podstrom. Vzhledem k tomu, že do konzole můžete zapisovat pouze řádek po řádku, budete také muset vytisknout strom řádek po řádku.
Nyní potřebujeme jiný způsob odstoupení od smlouvycelý strom, nejen řádek po řádku.
Pomocí funkce výpisu můžete číst strom a výrazně zlepšit výstupní algoritmus, pokud jde o rychlost.

Tuto funkci však bude obtížné použít na velkých stromech.

Kopírovat konstruktor a destruktor

Protože strom není triviální datová struktura, je lepší implementovat konstruktor kopírování, destruktor a operátor přiřazení. Destruktor lze snadno implementovat rekurzivně. U velmi velkých stromů si poradí s „přetečením haldy“. V tomto případě je formulován iterativně. Cílem je odstranit list představující nejmenší hodnotu ze všech listů, takže je na levé straně stromu. Odříznutím prvních listů vzniknou nové a strom se zmenšuje, až nakonec přestane existovat.

Konstruktor kopírování lze také implementovat rekurzivně, ale buďte opatrní, pokud dojde k vyvolání výjimky. Jinak se strom rychle stane matoucím a náchylným k chybám. Proto je preferována iterativní verze. Cílem je projít starý strom a nový strom, jako byste to udělali v destruktoru, a naklonovat všechny uzly, které jsou ve starém stromu, ale ne ty nové.

U této metody je implementace binárního vyhledávacího stromu vždy ve zdravém stavu a může být destruktorem odstraněna i v neúplném stavu. Pokud dojde k výjimce, vše, co musíte udělat, je instruovat destruktor, aby smazal rozpracovaný strom. operátor přiřazenílze snadno implementovat pomocí funkce Copy & Swap.

Vytvoření binárního vyhledávacího stromu

Optimální binární vyhledávací stromy jsou neuvěřitelně efektivní, pokud jsou správně spravovány. Některá pravidla pro binární vyhledávací stromy:

Rodičovský uzel má maximálně 2 podřízené uzly.
Levý podřízený uzel je vždy menší než nadřazený uzel.
Platný podřízený uzel je vždy větší nebo roven nadřazenému uzlu.

Pole, které bude použito k vytvoření binárního vyhledávacího stromu:

Základní celočíselné pole sedmi hodnot v netříděném pořadí.
První hodnota v poli je 10, takže prvním krokem při vytváření stromu je vytvoření 10 kořenového uzlu, jak je znázorněno zde.
Se sadou kořenových uzlů budou všechny ostatní hodnoty potomky tohoto uzlu. Podle pravidel je prvním krokem k přidání 7 do stromu jeho porovnání s kořenovým uzlem.
Pokud je hodnota 7 menší než 10, stane se levým podřízeným uzlem.
Pokud je hodnota 7 větší nebo rovna 10, posune se doprava. Protože je známo, že 7 je menší než 10, je označen jako levý podřízený uzel.
Rekurzivně provádějte srovnání pro každý prvek.
Podle stejného vzoru proveďte stejné srovnání se 14. hodnotou v poli.
Porovnání hodnoty 14 s kořenovým uzlem 10 s vědomím, že 14 je správný potomek.
Procházení polem,přijďte do 20.
Začněte porovnáním pole s 10, podle toho, která hodnota je větší. Přesuňte se tedy doprava a porovnejte to se 14, je mu více než 14 a vpravo nemá žádné děti.
Nyní je zde hodnota 1. Podle stejného vzoru jako ostatní hodnoty porovnejte 1 až 10, přesuňte se doleva a porovnejte se 7 a nakonec s 1 levým potomkem 7. uzlu.
Pokud je hodnota 5, porovnejte ji s 10. Protože 5 je menší než 10, přejděte doleva a porovnejte ji se 7.
S vědomím, že 5 je méně než 7, pokračujte ve stromu dolů a porovnejte 5 s 1 hodnotou.
Pokud 1 nemá žádné potomky a 5 je větší než 1, pak 5 je platným potomkem 1 uzlu.
Nakonec vložte hodnotu 8 do stromu.
Když je 8 menší než 10, posuňte ji doleva a porovnejte se 7, 8 je větší než 7, posuňte ji tedy doprava a doplňte strom, čímž se 8 stane správným potomkem 7.

Získání a vyhodnocení jednoduché elegance optimálních binárních vyhledávacích stromů. Jako mnoho témat v programování, síla binárních vyhledávacích stromů pochází z jejich schopnosti rozkládat data na malé, související komponenty. Od této chvíle můžete pracovat s celou datovou sadou organizovaným způsobem.

Potenciální problémy s binárním vyhledáváním

Binární vyhledávací stromy jsou skvělé, ale je třeba mít na paměti několik upozornění. Obvykle jsou účinné pouze tehdy, jsou-li vyvážené. Vyvážený strom je strom, ve kterémrozdíl mezi výškami podstromů libovolného uzlu ve stromu je nejvýše jedna. Podívejme se na příklad, který by mohl pomoci objasnit pravidla. Představme si, že pole začíná jako seřaditelné.

Pokud se pokusíte spustit algoritmus binárního vyhledávacího stromu na tomto stromě, bude fungovat přesně tak, jako by pouze procházel polem, dokud nebude nalezena požadovaná hodnota. Síla binárního vyhledávání spočívá ve schopnosti rychle odfiltrovat nežádoucí hodnoty. Když strom není vyvážený, nebude poskytovat stejné výhody jako vyvážený strom.

Při vytváření binárního vyhledávacího stromu je velmi důležité prozkoumat data, se kterými uživatel pracuje. Před implementací binárního vyhledávacího stromu pro celá čísla můžete integrovat rutiny, jako je randomizace pole.

Příklady výpočtu binárního vyhledávání

Potřebujeme určit, jaký druh stromu vznikne, pokud je 25 vložena do následujícího binárního vyhledávacího stromu:

5 15

/ /

2 12 20

Při vkládání x do stromu T, který ještě neobsahuje x, se klíč x vždy umístí do nového listu. V souvislosti s tím bude nový strom vypadat takto:

5 15

/ /

2 12 20

Jaký druh stromu byste získali, kdybyste do následujícího binárního vyhledávacího stromu vložili 7?

5 15

/ /

2 12 20

Odpověď:

5 15

/ / /

2 7 12 20

Binární vyhledávací strom lze použít k uložení libovolného objektu. Výhodou použití binárního vyhledávacího stromu místo propojeného seznamu je to, že pokud je strom přiměřeně vyvážený a podobá se spíše „plnému“stromu než „lineárnímu“, lze implementovat operace vkládání, vyhledávání a všechny operace mazání tak, aby běžely v O(log N) čas.