Binomsko drevo
Iz MaFiRaWiki
(Razlika med različicami)
Različica od 11:01, 15 maj 2007
[spremeni]
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
- manjši od korenov poddreves tudi koren celotnega drevesa in
Rekurzivna definicija binomskega drevesa:
Primer binomskih dreves:
[spremeni]
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
(glej primer).
Primer:
