Binární vyhledávací strom: Porovnání verzí

Skočit na navigaci Skočit na vyhledávání
Přidáno 2 215 bajtů ,  před 14 lety
bez shrnutí editace
m (robot přidal: id:Pohon biner terurut)
No edit summary
'''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 ==
[[vi:Cây tìm kiếm nhị phân]]
[[zh:二元搜尋樹]]
<br />
16

editací

Navigační menu