Binární strom

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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.
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ů[editovat | editovat zdroj]

  • 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 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

(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ů[editovat | editovat zdroj]

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.
    • 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[editovat | editovat zdroj]