Binárny vyhľadávací strom

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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.

Vyhľadávanie v strome[upraviť | upraviť zdroj]

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 h \le h', do u sa uloží ľavý potomok u
    2. inak sa do u uloží pravý potomok u
  5. pokračuj bodom 2

Rýchlosť vyhľadávania[upraviť | upraviť zdroj]

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.

Pozri aj[upraviť | upraviť zdroj]

Externé odkazy[upraviť | upraviť zdroj]