Binomiální strom řádu k (značíme Bk) je uspořádaný (t.j. záleží na pořadí potomků) zakořeněný strom, pro který platí:
- B0 je tvořen pouze kořenem.
- Pro k≥1 získáme Bk ze stromů B0, B1, ... , Bk-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.
Vlastnosti
Věta:
Počet hladin stromu Bk je roven k+1, stupeň kořene je k, a počet vrcholů Bk je roven 2k.
Důkaz
Indukcí podle k.
- Strom B0 má jistě 1 hladinu 20 = 1 vrchol.
- Z indukčního předpokladu vyplývá, že hloubka Bk-1 je k a počet vrcholů je 2k-1.
- Užitím předchozí věty dostáváme, že strom Bk je složenýze dvou stromů Bk, z nichž jeden je o hladinu níže než druhý, což dává počet hladin k + 1 stromu Bk.
- Složením dvou stromů Bk-1 dostáváme 2·2k-1= 2k vrcholů.
Důsledek
Binomiální strom s n vrcholy má hloubku logn a počet synů kořene také logn.