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:

1. 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.
2. 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í: ${\displaystyle h}$ – hloubka stromu, ${\displaystyle n}$ – počet uzlů, ${\displaystyle n_{0}}$ – počet listů , ${\displaystyle n_{2}}$ – počet vnitřních uzlů, ${\displaystyle ni}$ – počet nillů,

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

• Plný binární strom
  • počet uzlů získáme z rovnice ${\displaystyle n=2^{h+1}-1}$.
  • počet uzlů v úplném binárním získáme ${\displaystyle 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.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