Binomsko drevo

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 15:22, 15 maj 2007
TomazPisanski (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
AleksandraVujasin (Pogovor | prispevki)

Vrstica 1: Vrstica 1:
-==Binomsko drevo==+==Opis==
-Binomsko drevo je rekurzivna podatkovna struktura, kjer velja:+Binomsko drevo je rekurzivna [[Podatkovna struktura|podatkovna struktura]], kjer velja:
* koren je najmanjši element v drevesu (urejenost); * koren je najmanjši element v drevesu (urejenost);
* posamezen element je binomsko drevo B<sub>0</sub>; * posamezen element je binomsko drevo B<sub>0</sub>;
Vrstica 8: Vrstica 8:
**poddrevo z večjim korenom prvi naslednik celotnega drevesa B<sub>k</sub> **poddrevo z večjim korenom prvi naslednik celotnega drevesa B<sub>k</sub>
-'''Rekurzivna definicija binomskega drevesa:'''<br>+'''Rekurzivna definicija''' binomskega drevesa:
[[image:RekurzijaBinomskoDrevo.jpg]] [[image:RekurzijaBinomskoDrevo.jpg]]
-'''Primer binomskih dreves:'''<br>+'''Opomba:'''<br>
-[[image:BinomskaDrevesa.jpg]]+Binomska drevesa niso binarna (dvojiška) drevesa. Tako binomska kot binarna drevesa imajo lahko poljubno število otrok. Razlika je v tem, da ima [[Dvojiško drevo|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 binomskega drevesa==+==Lastnosti==
* koren je najmanjši element v drevesu, * koren je najmanjši element v drevesu,
* koren ima k naslednikov, pri čemer je prvo poddrevo B<sub>k-1</sub>, drugi B<sub>k-2</sub> in tako naprej do ''k''-tega, ki je B<sub>0</sub> (z indukcijo po ''k''); * koren ima k naslednikov, pri čemer je prvo poddrevo B<sub>k-1</sub>, drugi B<sub>k-2</sub> in tako naprej do ''k''-tega, ki je B<sub>0</sub> (z indukcijo po ''k'');
Vrstica 25: Vrstica 26:
[[image:GlobinaBinomskegaDrevesa.jpg]] [[image:GlobinaBinomskegaDrevesa.jpg]]
-== Glej tudi ==+==Primeri==
-[[Binomska kopica]]+<center>[[image:BinomskaDrevesa.jpg]]</center>
 + 
 +==Glej tudi==
 +* [[Dvojiško drevo]]
 +* [[Binomska kopica]]
 +* [http://demonstrations.wolfram.com/BinomialTree/ Binomial tree demonstration]
 + 
 +==Viri==
 +* [http://en.wikipedia.org/wiki/Binomial_heap Binomial heap (Wikipedia)]
 + 
 +==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.
[[Kategorija: Podatkovna struktura]] [[Kategorija: Podatkovna struktura]]
 +[[Kategorija:Računalništvo]]

Trenutna različica

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