05.2 Binomiální strom
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Binomiální strom
Binomiální strom řádu $k$ (značíme $B_{k}$) je uspořádaný (tj. záleží na pořadí synů) zakořeněný strom, pro který platí:
- $B_{0}$ je tvořen pouze kořenem
- Pro $k \ge 1$ získáme $B_{k}$ ze stromů $B_{0}, B_{1}, \dots B_{k-1}$ tak, že přidáme nový kořen a kořeny těchto stromů uděláme (takto popořadě) syny nového kořene
Binomiální strom řádu $k$ (značíme $B^{’}_{0}$) je uspořádaný zakořeněný strom, pro který platí:
- $B^{’}_{0}$ je tvořen pouze kořenem
- Pro $k \ge 1$ se $B^{’}{k}$ skládá ze stromu $B^{’}{k-1}$, pod jehož kořenem je jako nejpravější syn napojený další strom $B^{’}_{k-1}$
# Počet vrcholů
- Každý strom $B_{k}$ má $2^{k}$ vrcholů
- Počet vrcholů na $i$. hladině je $n_{k}(i)=\binom{k}{i}$ (navíc, nepamatovat)
# Počet hladin
- Každý strom $B_{k}$ má $k+1$ hladin, stupeň kořene je $k$
- Každý strom s $n$ vrcholy má $1+\log{n}$ hladin, počet synů kořene je $\log{n}$