Binární vyhledávací strom

Podcast

Binární vyhledávací strom: Jak najít jehlu v kupce sena za 20 kroků0:00 / 10:01

0:001:00 zbývá

1x

Binární vyhledávací strom (zkráceně BST z anglického Binary Search Tree) je základní datová struktura v informatice, která slouží k efektivnímu ukládání a organizaci dat. Díky ní je možné rychle vyhledávat, vkládat a mazat prvky. Jedná se o speciální typ binárního stromu, který dodržuje specifické uspořádání hodnot v uzlech, což mu propůjčuje jeho unikátní vyhledávací schopnosti. Pochopit binární vyhledávací strom je klíčové pro každého studenta informatiky.

Co je Binární Vyhledávací Strom? Základní charakteristika a principy

Binární strom je hierarchická datová struktura složená z uzlů. Každý uzel v binárním stromu může mít maximálně dva potomky: levého potomka a pravého potomka. Uzel bez potomků se nazývá list, zatímco uzel bez rodiče je kořen stromu. Každý uzel kromě kořene má právě jednoho rodiče.

Klíčová vlastnost binárního vyhledávacího stromu spočívá v uspořádání hodnot uzlů. Pro každý uzel U ve stromu platí specifická pravidla, která zajišťují jeho funkčnost:

• Pravidlo 1: Všechny hodnoty v levém podstromu uzlu U jsou menší než hodnota samotného uzlu U.
• Pravidlo 2: Všechny hodnoty v pravém podstromu uzlu U jsou větší než hodnota samotného uzlu U.
• Pravidlo 3: Levý i pravý podstrom uzlu U jsou samy o sobě binárními vyhledávacími stromy.

Tato uspořádanost dat umožňuje logaritmickou časovou složitost pro většinu operací, pokud je strom vyvážený.

Klíčové operace na Binárním Vyhledávacím Stromu

Porozumění operacím je zásadní pro práci s BST. Zde je rozbor binárního vyhledávacího stromu a jeho základních operací.

Hledání prvku v BST

Hledání prvku s danou hodnotou X v BST začíná u kořene stromu. Algoritmus postupuje rekurzivně nebo iterativně:

1. Porovnejte X s hodnotou aktuálního uzlu U.
2. Pokud se X rovná hodnotě U, prvek byl nalezen.
3. Pokud je X menší než hodnota U, pokračujte v hledání v levém podstromu uzlu U.
4. Pokud je X větší než hodnota U, pokračujte v hledání v pravém podstromu uzlu U.
5. Pokud se dostanete k prázdnému podstromu (aktuální uzel je null), prvek ve stromu není.

Příklad hledání hodnoty 50:

Předpokládejme, že hledáme hodnotu 50 v následujícím stromu (po vložení všech prvků): kořen 40, levý potomek 20 (má 10 a 30), pravý potomek 60 (má 50 a 70).

• Začneme u 40. 50 > 40, jdeme doprava (na 60).
• Aktuální uzel je 60. 50 < 60, jdeme doleva (na 50).
• Aktuální uzel je 50. Nalezeno!

Vkládání nového prvku do BST

Vkládání nové hodnoty X do BST se provádí podobně jako hledání. Začíná se u kořene a postupuje se dolů stromem, dokud se nenajde vhodné místo pro vložení nového uzlu jako listu:

1. Začněte u kořene stromu.
2. Porovnejte X s hodnotou aktuálního uzlu U.
3. Pokud je X menší než hodnota U:

• Pokud má U levého potomka, pokračujte vlevo.
• Pokud U nemá levého potomka, vložte X jako levého potomka uzlu U.

4. Pokud je X větší než hodnota U:

• Pokud má U pravého potomka, pokračujte vpravo.
• Pokud U nemá pravého potomka, vložte X jako pravého potomka uzlu U.

5. Duplikáty obvykle nejsou povoleny; pokud se X rovná hodnotě U, operace se často ignoruje.

Příklad vkládání hodnoty 25:

Předpokládejme, že vkládáme 25 do stromu:

 40
 / \
 20 60
 / \ / \
10 30 50 70

• 25 < 40, jdeme doleva (na 20).
• 25 > 20, jdeme doprava (na 30).
• 25 < 30, uzel 30 nemá levého potomka. Vložíme 25 jako levého potomka uzlu 30.

Výsledek:

 40
 / \
 20 60
 / \ / \
10 30 50 70
 /
 25

Mazání prvku z BST

Mazání uzlu z BST je nejsložitější operace, protože je třeba zachovat vlastnost BST. Existují tři hlavní případy pro mazaný uzel U:

1. Uzel U je list (nemá žádné potomky): Jednoduše odstraníme uzel U a nastavíme odkaz jeho rodiče na null.
2. Uzel U má jednoho potomka: Nahradíme uzel U jeho jediným potomkem. Rodič uzlu U nyní odkazuje na potomka uzlu U.
3. Uzel U má dva potomky: Toto je nejsložitější případ. Uzel U nelze jednoduše odstranit. Místo toho najdeme náhradní uzel, který zachová vlastnost BST. Nejčastěji se používá:

• Nejmenší prvek v pravém podstromu (inorder následník): Najdeme nejmenší hodnotu v pravém podstromu uzlu U. Zkopírujeme jeho hodnotu do uzlu U a poté rekurzivně smažeme tento náhradní uzel z jeho původního místa (což spadá do případu 1 nebo 2).
• Alternativně se může použít největší prvek v levém podstromu (inorder předchůdce).

Příklad mazání hodnoty 20 (uzel se dvěma potomky):

Předpokládejme, že mažeme 20 z následujícího stromu:

 40
 / \
 20 60
 / \ / \
10 30 50 70
 /
 25

• Najdeme inorder následníka uzlu 20. Tím je nejmenší prvek v pravém podstromu uzlu 20. Pravý podstrom začíná u 30. Nejmenší prvek zde je 25 (protože 30 má levého potomka 25, a 25 je list). Kdyby 30 nemělo levého potomka, byl by to 30.
• Zkopírujeme hodnotu 25 do uzlu 20. Uzel, který byl 20, má nyní hodnotu 25.
• Smažeme uzel s hodnotou 25 z jeho původního místa. Uzel 25 je levým potomkem uzlu 30 a nemá žádné potomky (je list). Spadá do případu 1. Jednoduše nastavíme levý odkaz uzlu 30 na null.

Výsledek po smazání 20:

 40
 / \
 25 60
 / \ / \
10 30 50 70

Výška stromu a vyvážení: Proč je to důležité pro výkon BST?

Výška stromu je délka nejdelší cesty od kořene k listu. Výška stromu h je klíčovým faktorem pro výkonnost operací na BST. Časová složitost většiny operací (hledání, vkládání, mazání) je přímo úměrná výšce stromu, tedy O(h).

Vyvážený vs. Nevyvážený Binární Vyhledávací Strom

• Vyvážený strom: V ideálním případě, kdy je strom dokonale vyvážený, je výška stromu logaritmická vzhledem k počtu uzlů n (h ≈ log₂ n). To umožňuje velmi rychlé operace. Například pro strom s milionem uzlů by výška byla přibližně 20.
• Nevyvážený strom: V nejhorším případě, pokud jsou prvky vkládány do stromu v seřazeném pořadí (např. 1, 2, 3, 4, 5), se BST degeneruje na lineární strukturu (spojový seznam). V takovém případě je výška stromu h = n - 1 (nebo n), a časová složitost operací se stává O(n). To je stejně neefektivní jako prohledávání neseřazeného pole.

Aby se zabránilo degeneraci a zajistila se logaritmická časová složitost, používají se vyvážené binární vyhledávací stromy. Tyto stromy automaticky provádějí rebalancování po operacích vkládání a mazání, aby udržely výšku stromu co nejmenší. Mezi nejznámější vyvážené BST patří AVL stromy a červeno-černé stromy, které zaručují, že výška stromu bude vždy O(log n).

Průchody stromem: Inorder, Preorder, Postorder

Průchod stromem je systematický způsob, jak navštívit každý uzel ve stromu právě jednou. Existují tři základní typy průchodů pro binární stromy, které jsou důležité pro binární vyhledávací strom shrnutí jeho obsahu.

• Inorder (Infixový) průchod: Navštíví levý podstrom, poté aktuální uzel, a nakonec pravý podstrom. Pro BST tento průchod vypíše hodnoty uzlů ve vzestupném seřazeném pořadí (levý -> kořen -> pravý).
• Preorder (Prefixový) průchod: Navštíví aktuální uzel, poté levý podstrom, a nakonec pravý podstrom. Tento průchod je užitečný pro kopírování stromu (kořen -> levý -> pravý).
• Postorder (Postfixový) průchod: Navštíví levý podstrom, poté pravý podstrom, a nakonec aktuální uzel. Tento průchod je užitečný pro mazání celého stromu, protože odstraňuje listy jako první (levý -> pravý -> kořen).

Časté chyby a mylné představy při práci s BST

Jako studenti se můžete setkat s několika typickými problémy při implementaci nebo pochopení BST:

• Nezachování vlastnosti BST: Nejčastější chybou je nesprávné vkládání nebo mazání, které poruší pravidlo, že leví potomci jsou menší a praví větší. To vede k nefunkčnímu vyhledávání.
• Nepochopení mazání uzlu se dvěma potomky: Správné nahrazení uzlu s dvěma potomky nalezením inorder následníka (nebo předchůdce) a jeho odstranění z původního místa je klíčové.
• Ignorování vyvážení: Mnoho začátečníků si neuvědomuje, jak kritická je výška stromu pro jeho výkon. Předpokládají, že BST je vždy rychlý, aniž by zvážili degenerované případy a potřebu vyvážených variant.
• Záměna průchodů: Někdy dochází k záměně mezi inorder, preorder a postorder průchody a jejich specifickými aplikacemi.

Simulace a pozorování chování BST

Interaktivní simulace binárního vyhledávacího stromu je vynikajícím nástrojem pro hlubší pochopení jeho chování. Při vkládání a mazání uzlů v simulaci si můžete všimnout následujících aspektů:

• Vkládání uzlů: Sledujte, jak se nové uzly vždy vkládají jako listy. Pozorujte, jak se strom dynamicky rozšiřuje a jak se mění jeho výška v závislosti na pořadí vkládaných prvků. Pokud vkládáte prvky v seřazeném pořadí, uvidíte, jak se strom stává degenerovaným (lineární struktura).
• Mazání uzlů: Pozorujte, jak se strom přizpůsobuje po odstranění uzlu, zejména v případě uzlů se dvěma potomky a nahrazování inorder následníkem.

FAQ: Často kladené otázky k Binárnímu Vyhledávacímu Stromu

Jaký je hlavní rozdíl mezi binárním stromem a binárním vyhledávacím stromem?

Hlavní rozdíl spočívá v uspořádání dat. Zatímco binární strom je obecná struktura, kde každý uzel má nanejvýš dva potomky, binární vyhledávací strom dodržuje specifická pravidla uspořádání. Všechny hodnoty v levém podstromu jsou menší než kořen a všechny hodnoty v pravém podstromu jsou větší. Tato vlastnost umožňuje efektivní vyhledávání.

Proč je důležité, aby byl binární vyhledávací strom vyvážený?

Vyvážený strom zajišťuje, že výška stromu bude logaritmická vzhledem k počtu uzlů (O(log n)). To je zásadní pro efektivitu operací jako hledání, vkládání a mazání, které pak mají logaritmickou časovou složitost. Nevyvážený strom se může degenerovat na lineární strukturu, což zhorší výkon na O(n).

Jak se liší inorder, preorder a postorder průchod?

Tyto průchody se liší pořadím, ve kterém navštěvují kořenový uzel, levý podstrom a pravý podstrom. Inorder průchod (levý-kořen-pravý) vypíše prvky BST ve vzestupném pořadí. Preorder průchod (kořen-levý-pravý) je užitečný pro kopírování stromu. Postorder průchod (levý-pravý-kořen) se používá například pro mazání celého stromu.

Co je to inorder následník a k čemu se používá při mazání BST?

Inorder následník uzlu U je nejmenší hodnota v pravém podstromu uzlu U. Používá se při mazání uzlu se dvěma potomky. Hodnota inorder následníka nahradí hodnotu mazaného uzlu, a poté se inorder následník odstraní ze své původní pozice ve stromu. Tím se zachová vlastnost BST.