Uživatel:Penkape1/Pískoviště

Binární stromy

Binární strom je datová struktura pro reprezentaci dat. Tato struktura má hierarchické uspořádání. Tím je myšleno, že jeden prvek je nadřazen jiným podprvkům a tyto podprvky náleží tomuto prvku. Abychom mohli tuto strukturu vysvětlit je nutné si vysvětlit základní pojmy.

• Kořen
• Uzel
• List
• Otec
• Syn

Otec

Otec je uzel, který má pod sebou další uzly jemu náležící.

Syn

Syn je uzel, který je podřízen jemu nadrazenému uzlu.

Kořen

Je uzel, který je nadřazen všem ostatním uzlům. Tento uzel stojí hierarchický nejvýše a již nemá žádného otce. Neboli nemá žadné nadřazené uzly. Kořen může vždy mít pouze syny, neboli uzly jemu náležící.

Uzel

Uzel je prvek, který má syny a zároveň otce. Neboli tento uzel má uzel, který je tomuto uzlu nadřazen a zároveň pod něj spadají uzly jemu náležicí.

List

Tento uzel je koncovým uzlem této datové struktury. Jedná se o uzel, který nemá syny, ale pouze otce.

Příklad

Abychom tyto pojmy lépe pochopili, uvedem se zde příklad binárního stromu.

V tomto obrázku mamé uzly označené kružnicí a spoje mezi nimi jsou prezentovány úsečkou mezi těmito kružnicemi. Každý uzel má určitou číselnou hodnotu. Uzel s číselnou hodnotou '6' je prostým uzlem a má 2 syny (uzly s číselnou hodnotou '5', '11'). Tento uzel je zároveň otcem těchto uzlů a jeho otcem je uzel s číselnou hodnotou '7'. Listy jsou zde spodní uzly a jedná se o uzly s číselnou hodnotou '5', '11' a '4'. Kořenem je zde vrchní uzel s číselnou hodnotou '2' a jeho synové jsou uzly s číselnou hodnotou '7' a '5'. Kořen již nemá otce.

Jedná se tedy o orientovaný graf s jedním vrcholem (kořenem), z něhož existuje cesta do všech vrcholů grafu. Aby se jednalo o binární strom musí každý otec mít maximálně dva syny.

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$.