Binární strom

Jednoduchý 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. +more 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. +more 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.

Diagram binárního stromu

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. +more * 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í: h - hloubka stromu, n - počet uzlů, n_0 - počet listů , n_2 - počet vnitřních uzlů, ni - počet nillů,

* Úplný binární strom ** minimální počet uzlů získáme z rovnice n = {h}+1 a maximální počet n=2^{h+1}-1. ** počet nillů (NULL ukazatelů) roven ni=n+1. +more ** počet listů roven \lceil \frac{n}{2} \rceil (n/2 zaokrouhleno nahoru).

* Plný binární strom ** počet uzlů získáme z rovnice n=2^{h+1}-1. ** počet uzlů v úplném binárním získáme 2n_0-1.

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. +morecmu. 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

Kategorie:Stromy (datové struktury)