Binomiální strom řádu k (značíme B_k) je uspořádaný (t.j. záleží na pořadí potomků) zakořeněný strom, pro který platí:

• B₀ je tvořen pouze kořenem.
• Pro k≥1 získáme B_k ze stromů B₀, B₁, ... , 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.

Vlastnosti

Věta:

Počet hladin stromu B_k je roven k+1, stupeň kořene je k, a počet vrcholů B_k je roven 2^k.

Důkaz

Indukcí podle k.

• Strom B₀ má jistě 1 hladinu 2⁰ = 1 vrchol.
• Z indukčního předpokladu vyplývá, že hloubka B_k-1 je k a počet vrcholů je 2^k-1.
• Užitím předchozí věty dostáváme, že strom B_k je složenýze dvou stromů B_k, z nichž jeden je o hladinu níže než druhý, což dává počet hladin k + 1 stromu B_k.
• Složením dvou stromů B_k-1 dostáváme 2·2^k-1= 2^k vrcholů.

Důsledek

Binomiální strom s n vrcholy má hloubku logn a počet synů kořene také logn.