Binární vyhledávací strom

Jednoduchý binární vyhledávací strom

Binární vyhledávací strom (BST) je datová struktura založená na binárním stromu, v němž jsou jednotlivé prvky (uzly) uspořádány tak, aby v tomto stromu bylo možné rychle vyhledávat danou hodnotu. To zajišťují tyto vlastnosti:

• Každý uzel je ohodnocen číslem.
• Celkové seřazení uzlů je dáno těmito číselnými hodnotami.
• Levý podstrom uzlu obsahuje pouze hodnoty menší než je hodnota tohoto uzlu.
• Pravý podstrom uzlu obsahuje pouze hodnoty stejné nebo větší než je hodnota tohoto uzlu.

Hlavní výhoda binárních vyhledávacích stromů je ta, že příslušný třídicí a vyhledávací algoritmus jako je in-order procházení může být velmi efektivní.

Binární vyhledávací stromy jsou zásadní datovou strukturou při konstrukci daleko abstraktnějších datových struktur jako jsou množiny, multi-množiny
a asociovaná pole.

Pokud BST umožňuje duplicity hodnot, pak představuje multi-množinu. Tento typ stromu využívá nestriktní nerovnost. Všechny hodnoty uzlů v levém podstromu uzlu jsou striktně menší než je hodnota uzlu, ale všechny hodnoty v pravém podstromu jsou buď větší nebo shodné s hodnotou uzlu.

Pokud BST neumožňuje duplicity hodnot, pak se jedná o strom s unikátními hodnotami, stejně jako matematická množina. Stromy bez duplicit využívají striktní nerovnost, tedy hodnoty uzlů levého podstromu jsou menší než je hodnota uzlu a pravý podstrom obsahuje pouze hodnoty větší než je hodnota uzlu.

Uložení duplicitních hodnot právě v pravém podstromu není povinné. Stejně tak je lze uchovávat i v levém podstromu. Lze též užít nestriktní ekvivalenci na obou stranách. Toto řešení sice napomáhá stromu obsahujícímu mnoho duplicit k lepšímu vyvážení, ale zároveň ztěžuje vyhledávání.

Operace

Všechny operace na binárním stromě využívají několik volání komparátoru, který je podprogramem pro zjištění pořadí dvou hodnot. V obecných implementacích BST program při tvorbě stromu běžně poskytuje zpětné volání komparátoru, buď explicitně nebo v jazycích, které podporují polymorfismus hodnotou, kterou lze porovnávat.

Vyhledávání ve stromu

Hodnoty v uzlech jsou uspořádány tak, že pro každý uzel stromu u platí:

• hodnota uložená v u je větší nebo rovna než hodnota uložená v levém podstromu u
• hodnota uložená v u je menší nebo rovna než hodnota uložená v pravém podstromu u

Pak lze v tomto stromu jednoduchým způsobem vyhledat danou hodnotu h:

1. nastav kořen jako aktuální uzel (u)
2. pokud je v u uložená hodnota h, algoritmus končí (a vydá u)
3. je-li u list, algoritmus končí (hodnota h nebyla ve stromu nalezena)
4. hodnota h se porovná s hodnotou v u (nechť je tato hodnota h')
   1. je-li $h\leq h'$, do u se uloží levý syn u
   2. jinak se do u uloží pravý syn u
5. pokračuj bodem 2

Rychlost vyhledávání

Rychlost vyhledávání závisí na tom, jak je strom vyvážen. Pro vyhledání dané hodnoty ve stromu jím stačí jednou projít výše uvedeným způsobem. Časová složitost tohoto algoritmu je úměrná výšce stromu. Má-li binární strom n listů, je jeho výška (a tedy i rychlost vyhledávání) rovna minimálně log₂ n a maximálně n. Otázka správného vyvážení je z tohoto pohledu kritická a řeší jí například AVL-strom.

Související články

• Cyklický graf
• AVL-strom
• B-strom
• Binární půlení