Binární vyhledávací strom

Z Wikipedie, otevřené encyklopedie

Binární vyhledávací strom 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.

[editovat] 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 , do u se uloží levý syn u
   2. jinak se do u uloží pravý syn u
5. pokračuj bodem 2

[editovat] 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.

[editovat] Podívejte se také na

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