Binární vyhledávací strom: Porovnání verzí
Smazaný obsah Přidaný obsah
m robot přidal: id:Pohon biner terurut |
Bez shrnutí editace |
||
Řádek 1:
'''Binární vyhledávací strom''' je [[datová struktura]] založená na [[binární strom|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.▼
[[Soubor:Binary search tree.svg|right|192|thumb|Jednoduchý binární vyhledávací strom]]
▲'''Binární vyhledávací strom''' (BST) je [[datová struktura]] založená na [[binární strom|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 [[Strom (datová struktura)#Procházení stromem do hloubky|in-order procházení]] může být velmi efektivní.
Binární vyhledávací stromy jsou zásadní [[datová struktura|datovou strukturou]] při konstrukci daleko [[Abstraktní datový typ|abstraktnějších datových struktur]] jako jsou [[množina|množiny]], [[multi-množina|multi-množiny]]<br />a [[asociované pole|asociovaná pole]].
Pokud BST umožňuje duplicity hodnot, pak představuje [[multi-množina|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 [[množina|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 ==
Řádek 47 ⟶ 66:
[[vi:Cây tìm kiếm nhị phân]]
[[zh:二元搜尋樹]]
<br />
| |||