A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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
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:
- nastav koreň ako aktuálny uzol (u)
- pokiaľ je v u uložená hodnota h, algoritmus končí (a vráti u)
- ak je u list, algoritmus končí (hodnota h nebola v strome nájdená)
- hodnota h sa porovná s hodnotou v u (nech je táto hodnota h')
- ak je , do u sa uloží ľavý potomok u
- inak sa do u uloží pravý potomok u
- pokračuj bodom 2
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.
Pozri aj
Externé odkazy
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk