title: Binomiální strom Import: [Strom] alias: strom

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

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.

Důsledek

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