![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/langcs-640px-Binary_search_tree.svg.png&w=640&q=50)
Binární vyhledávací strom
seřazený strom s maximálně dvěma potomky v každém uzlu / From Wikipedia, the free encyclopedia
Binární vyhledávací strom (BST – z angl. Binary Search Tree) je datová struktura založená na 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:
- Jedná se o binární strom, každý uzel tedy má nanejvýš dva potomky – levého a pravého.
- Každému uzlu je přiřazen určitý klíč. Podle hodnot těchto klíčů jsou uzly uspořádány.
- Levý podstrom uzlu obsahuje pouze klíče menší než je klíč tohoto uzlu.
- Pravý podstrom uzlu obsahuje pouze klíče větší než je klíč tohoto uzlu.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/220px-Binary_search_tree.svg.png)
Hlavní výhodou binárních vyhledávacích stromů je vysoká efektivita vyhledávání hodnot v nich, byť proti hašovací tabulce je pomalejší. Lze je využít při dobré implementaci také k efektivnímu řazení hodnot – in-order průchod binárním vyhledávacím stromem vydá seznam uložených hodnot uspořádaný podle velikosti. Ale důležitější jsou na tom postavené intervalové dotazy a průběžné udržování uspořádaných klíčů, protože řadit na místě, tj. efektivněji, umí spousta jiných algoritmů.
Binární vyhledávací stromy jsou zásadní datovou strukturou při konstrukci daleko abstraktnějších datových struktur jako jsou množiny, multimnožiny a asociativní pole.
Pokud BST neumožňuje duplicity hodnot, pak se jedná o strom s unikátními hodnotami, stejně jako matematická množina. Stromy bez duplicit využívají ostrou 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.
Pokud BST umožňuje duplicity hodnot, pak představuje multimnožinu. Tento typ stromu využívá neostrou nerovnost. Všechny hodnoty uzlů v levém podstromu uzlu jsou menší než je hodnota uzlu, ale všechny hodnoty v pravém podstromu jsou buď větší, nebo shodné s hodnotou 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 neostrou nerovnost v obou podstromech, což usnadní vyvážení stromu obsahujícího mnoho duplicit, ale utrpí efektivita vyhledávání.
Strom se mnohem častěji než na množiny a multimnožiny používá pro asociativní paměť (nepřesně asociativní pole), kde se podle klíče hledá přidružená hodnota. Vyhledávací stromy (včetně nebinárních) mají mnoho implementačních variant (majících vlastní jména a články) případně i s lepšími vlastnostmi. Na druhé straně pro asociativní pole se dají použít i jiné konkrétní datové struktury.
BST Vyhledávací stromy slouží jako ideový základ pro konstrukci složitějších vyhledávacích datových struktur, konkrétně pro složené klíče a dotazy s částečně zadanými klíči.
Složitost operací je, zjednodušeně řečeno, při dobré implementaci logaritmická a obecně lineární vzhledem k počtu reprezentovaných prvků.