Binomsko drevo

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 11:01, 15 maj 2007
AleksandraVujasin (Pogovor | prispevki)

← Prejšnja različica
Različica od 15:22, 15 maj 2007
TomazPisanski (Pogovor | prispevki)
Binomsko drevo
Naslednja različica →
Vrstica 13: Vrstica 13:
'''Primer binomskih dreves:'''<br> '''Primer binomskih dreves:'''<br>
[[image:BinomskaDrevesa.jpg]] [[image:BinomskaDrevesa.jpg]]
 +
 +== Glej tudi ==
 +[[Binomska kopica]]
 +
 +[[Kategorija: Podatkovna struktura]]
==Lastnosti binomskega drevesa== ==Lastnosti binomskega drevesa==

Različica od 15:22, 15 maj 2007

Binomsko drevo

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

Primer binomskih dreves:
image:BinomskaDrevesa.jpg

Glej tudi

Binomska kopica

Lastnosti binomskega drevesa

  • 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

Osebna orodja