# Binárny vyhľadávací strom

### Z Wikipédie

Binárny vyhľadávací strom je dátová štruktúra založená na binárnom strome, v ktorom sú jednotlivé prvky (uzly, vrcholy) usporiadané tak, aby v tomto strome bolo možné rýchlo vyhľadávať danú hodnotu.

## [úprava] Vyhľadávanie v strome

Hodnoty v uzloch sú usporiadané tak, že pre každý uzol stromu u platí:

- hodnota uložená v u je väčšia alebo rovná ako hodnota uložená v ľavom podstrome u
- hodnota uložená v u je menšia alebo rovná ako hodnota uložená v pravom podstrome u

Potom je možné v tomto strome jednoduchým spôsobom vyhľadať danú hodnotu h:

1. nastav koreň ako aktuálny uzol (u)
2. pokiaľ je v u uložená hodnota h, algoritmus končí (a vráti u)
3. ak je u list, algoritmus končí (hodnota h nebola v strome nájdená)
4. hodnota h sa porovná s hodnotou v u (nech je táto hodnota h')
   1. ak je , do u sa uloží ľavý potomok u
   2. inak sa do u uloží pravý potomok u
5. pokračuj bodom 2

## [úprava] Rýchlosť vyhľadávania

Rýchlosť vyhľadávania závisí od toho, ako je strom vyvážený. Pre vyhľadanie danej hodnoty v strome ním stačí prejsť raz vyššie uvedeným spôsobom. Časová zložitosť tohto algoritmu je úmerná výške stromu. Ak má binárny strom n listov, je jeho výška (a teda aj rýchlosť vyhľadávania) rovná minimálne log2 n a maximálne n. Otázka správneho vyváženia je z tohoto pohľadu kritická a rieši ju napríklad AVL strom.

## [úprava] Pozri aj

- Cyklický graf
- AVL strom
- B-strom
- Binárne delenie

Zdroj: "http://sk.wikipedia.org../../../b/i/n/Bin%C3%A1rny_vyh%C4%BEad%C3%A1vac%C3%AD_strom.html"

Kategória: Údajové štruktúry

##### Views

- Stránka
- Diskusia
- Aktuálna verzia

##### Hľadaj

##### Iné jazyky

- Česky
- Dansk
- Deutsch
- English
- Español
- Suomi
- Français
- עברית
- Italiano
- 日本語
- Nederlands
- Polski
- Português
- Русский
- Svenska
- Українська
- Tiếng Việt
- 中文