Binomsko drevo

Iz MaFiRaWiki

Vsebina

Opis

Binomsko drevo je rekurzivna podatkovna struktura, kjer velja:

  • koren je najmanjši element v drevesu (urejenost);
  • posamezen element je binomsko drevo B0;
  • binomsko drevo Bk sestoji iz dveh poddreves Bk-1, pri čemer je:
    • manjši od korenov poddreves tudi koren celotnega drevesa in
    • poddrevo z večjim korenom prvi naslednik celotnega drevesa Bk

Rekurzivna definicija binomskega drevesa: image:RekurzijaBinomskoDrevo.jpg

Opomba:
Binomska drevesa niso binarna (dvojiška) drevesa. Tako binomska kot binarna drevesa imajo lahko poljubno število otrok. Razlika je v tem, da ima binarno drevo le dva sinova (kazalec na levega in desnega sina), binomsko drevo pa ima lahko poljubno število sinov, vendar je tu kazalec le na skrajno levega sina, ta pa kaže na desne brate, kot prikazuje spodnja slikica.

image:BinomskoDrevo2.jpg

Lastnosti

  • koren je najmanjši element v drevesu,
  • koren ima k naslednikov, pri čemer je prvo poddrevo Bk-1, drugi Bk-2 in tako naprej do k-tega, ki je B0 (z indukcijo po k);
  • v drevesu je n = 2k elementov,
  • višina drevesa je k,
  • število vozlišč na globini i je image:BinomskiSimbolBD.jpg (glej primer).

Primer:
image:GlobinaBinomskegaDrevesa.jpg

Primeri

image:BinomskaDrevesa.jpg

Glej tudi

Viri

Literatura

  • Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introductions to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 19: Binomial Heaps, pp. 455-475.
Osebna orodja