Binární strom
Binární strom je pojem z teorie grafů a zároveň datová struktura, používaná k ukládání a vyhledávání dat v informatice.
Binární strom je strom ve smyslu používaném v teorii grafů. Jedná se o orientovaný graf s jedním vrcholem (kořenem), z něhož existuje cesta do všech vrcholů grafu. Každý vrchol binárního stromu může mít maximálně dva orientované syny a s výjimkou kořene právě jednoho předka. Kořen předka nemá.
V praktickém programování je obvykle binární strom reprezentován dvěma způsoby:
- pomocí dynamické struktury, kde jsou hrany reprezentovány ukazateli. Takto se reprezentuje například AVL-strom. Implementačně mohou mít vrcholy též ukazatel na rodiče, kromě dvou ukazatelů na potomky.
- pomocí pole, kde prvek s indexem i má následníky s indexem 2i+1 a 2i+2 (za předpokladu, že pole je indexováno od 0). Takto je například reprezentována halda v algoritmu heapsort.
Binární strom je nejčastěji používán jako binární vyhledávací strom a halda.
Typy binárních stromů
- Binární strom obsahuje uzly které mají nejvýš 2 syny.
- Plný binární strom: každý vnitřní uzel má dva syny.
- Vyvážený binární strom: hloubka podstromů se od sebe liší maximálně o jedna.
- Úplný binární strom: vyvážený binární strom plněný zleva. Jeden poslední vnitřní uzel nemusí být stupně k
(Terminologie okolo vyvážení a (ú)plnosti není ustálená a jednotná. V různých aplikacích se hodí různě přísné podmínky.)
Vlastnosti stromů
poznámka: pro níže uvedené rovnice platí: – hloubka stromu, – počet uzlů, – počet listů , – počet vnitřních uzlů, – počet nillů,
- Úplný binární strom
- minimální počet uzlů získáme z rovnice a maximální počet .
- počet nillů (NULL ukazatelů) roven .
- počet listů roven (n/2 zaokrouhleno nahoru).
- Plný binární strom
- počet uzlů získáme z rovnice .
- počet uzlů v úplném binárním získáme .
Související články
- Huffmanův strom používaný v Huffmanově kódování je binární, ale má data pouze v listech
- Binary Trees http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
- University of Florida http://www.cise.ufl.edu/class/cop3530sp13/lectures/Lecture18.pdf (ověřený zdroj)
Externí odkazy
- Obrázky, zvuky či videa k tématu binární strom na Wikimedia Commons
Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |
Stromové datové struktury | |
---|---|
Vyhledávací stromy (dynamické množiny/ asociativní pole) | 2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • Bx • (Optimální) Binární vyhledávací • Dancing • HTree • Intervalový • Stromy s pořadím (Order statistic) • (Doleva převážený) Červeno-černý • Scapegoat • Splay • T • Treap • UB • Váhově vyvážený (tj. BB[α]) |
Haldy | Binární • Binomiální • Brodal • Fibonacciho • Leftist • Pairing • Skew • Van Emde Boasův strom • Slabá |
Trie | Ctrie • C-trie • Hašovací • Komprimovaná trie (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast |
Prostorové indexační stromy | Ball • BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • PH • Prioritní R • Čtyřstrom (Quadtree) • R • R+ • R* • Segmentový • VP (vantage-point) • X |
Jiné stromy | Strom pokrytí • Obousměrně provázaný (Doubly chained tree) • Exponenciální • Fenwickův • (Binární) Strom s prstem • Fraktálový indexový • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný spojovací • Hašový Merkleův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom) |
Kategorie:Stromy (dat. strukt.) |