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 počítačích.

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
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 reprezentovaná 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 listy.
• Plný binární strom každý vnitřní uzel má dva syny.
• Vyvážený binární strom hloubka listů 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

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 = {2^h}+1$ a maximální počet $n=2^{h+1}-1$.
  • počet nillů (NULL ukazatelů) roven $ni=n+1$.
  • 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$.