Naučte se

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.

Související