BINOMSKO DREVO

Da bi razumeli pojem binomske kopice, si najprej poglejmo kaj je binomsko drevo.
Binomsko drevo je rekurzivna podatkovna struktura. Mora veljati:

• binomsko drevo reda 0 je eno samo vozlišče
• najmanjši ključ (podatek) v drevesu se nahaja v korenu

• binomsko drevo je sestavljeno iz dveh poddreves kjer velja:

  • manjši kjuč v korenu obeh poddreves, je tudi koren drevesa
  • binomsko drevo , ki je imelo večji ključ v korenu, pa postane levo poddrevo drevesa
    

V binomskem drevesu imamo elementov, višina drevesa pa je .

Primeri binomskih dreves:

Binomska drevesa

Primer kako sestavimo B4. Ključa v korenu poddreves B3 sta 11 in 19. Ker je 11<19, bo 11 tudi v korenu drevesa B4.

Binomska drevesa

BINOMSKA KOPICA

Binomska kopica je podatkovna struktura. Sestavljena je iz binomskih dreves, ki izpolnjujejo naslednje lastnosti:

• Vsako binomsko drevo v binomski kopici ima lastnost minimalnih kopic. Ključ vsakega vozlišča mora biti vedno večji ali enak ključu svojega starša. Iz tega sledi, da ima koren najmanjši ključ v binomskem drevesu.
• V binomski kopici obstaja kvečjemu eno binomsko drevo za vsak red, vključno z ničtim redom.
  

Druga lastnost pove, da je binomska kopica z n vozlišči sestavljena iz največ log n + 1 binomskih dreves.
Binomska drevesa v binomski kopici so razvrščena naraščajoče glede na stopnje dreves

Kako je število povezano z binomsko kopico?
Število predstavlja število vseh elementov binomske kopice.
Število lahko zapišemo v binarnem oz. dvojiškem zapisu.
Število dreves in njihov red je določeno s številom . Za lažjo predstavo bomo za izbrali število 10 ( v desetiškem zapisu). Pretvorimo v binarni zapis: = 11001.
Če pogledamo izraz . Ta izraz nam pove, da bomo imeli binomsko drevo reda 4 (eksponent nam določa stopnjo binomskega drevesa) z vozlišči. Izraz pa na pove, da ne bomo imeli drevesa stopnje 2, saj smo množili s številom 0. Torej končni rezultat je: binomska kopica je sestavljena iz binomskih dreves reda 4,3 in 0.

Osnovni način:

S tabelo :

UNIJA DVEH BINOMSKIH KOPIC

Imamo dve binomski kopici H1 in H2. Unija bo binomska kopica H. Dve binomski kopici združimo na sledeči način:

• Binomska drevesa iz H1 in H2 razvrstimo glede na stopnje oz. red dreves (od najmanjše stopnje do največje).
• Če H1 in H2 vsebujeta binomski drevesi reda , ju združimo v binomsko drevo H reda +1. Koren združenega binomskega drevesa, bo tisti izmed korenov iz H1 ali H2, ki je imel manjši ključ. Binomsko drevo z večjim ključem v korenu, pa postane levo poddrevo združenega binomskega drevesa H.
  Ker H1 ali H2 lahko vsebujeta binomsko drevo reda +1, ga bomo združili z H' na podoben način.
  Če H1 IN H2 vsebujeta binomsko drevo reda +1, združimo ti dve drevesi, H' pa pustimo pri miru.
• Postopek združevanja ponavljamo, dokler vsa binomska drevesa v združeni kopici niso različnih stopenj.
  
  
  

Primer unije :

1. korak:
Razvrstimo binomska drevesa iz H1 in H2 glede na stopnje dreves.

2. korak:
Prvo in drugo binomsko drevo sta istega reda, zato ju združimo. Koren združenega binomskega drevesa bo tisti izmed korenov obeh dreves, ki je imel manjši ključ. To je ključ 3. Drevo, ki edino vsebuje vozlišče s ključem 8, pa postane poddrevo združenega binomskega drevesa.

Ker nimamo več binomskih dreves enakih stopenj, je to končna rešitev.

Primer unije (malo težji):

H1:

H2:

1. korak:
Razvrstimo binomska drevesa iz H1 in H2 glede na stopnje dreves.

2. korak:
Združimo binomska drevesa istih stopenj. V tem primeru združimo prvo in drugo binomsko drevo, saj sta reda 0, ter tretjo in četrto binomsko drevo, saj sta reda 1.

Koren združenega binomskega drevesa, bo tisti izmed korenov dveh binomskih dreves, ki je imel manjši ključ.

Pri združitvi moramo upoštevati lastnost minimalne kopice. V našem primeru, ko bomo združili prvi dve drevesi, bo koren združenega drevesa postalo vozlišče s ključem 10, saj je 10<15. V primeru, ko združimo tretje in četrto binomsko drevo, pogledamo njuna korena, ki sta 8 in 5. Ker je 5<8, bo vozlišče s ključem 5 koren združenega binomskega drevesa. Binomsko drevo s ključem 8 v korenu, pa bo postalo njegovo levo poddrevo.

3. korak:
Kot vidimo, sta sedaj drugo in tretje binomsko drevo istega reda, zato ju združimo na podoben način kot pri prejšnjem koraku.

Ta slika predstavlja unijo binomskih dreves H1 in H2, saj nimamo več binomskih dreves enake stopnje oz. reda.

BRISANJE VOZLIŠČA Z MINIMALNIM KLJUČEM

Iz binomske kopice želimo izbrisati najmanjši ključ (podatek) x. Kot vemo, se najmanjši ključ nahaja v korenu v enem izmed binomskih dreves, ki sestavljajo binomsko kopico.
Nato ustvarimo novo binomsko kopico H, ki bo vsebovala zaporedje poddreves (otrok) vozlišča x v obratnem vrstnem redu kot prej ( torej na prvem mestu bo poddrevo z najnižjo stopnjo).
H pa naj bo prvotna binomska kopica, ki v zaporedju binomskih dreves, ne vsebuje binomskega drevesa, ki je vseboval minimalni ključ x.
V nadaljevanju združimo H in H s pomočjo operacije UNIJA DVEH BINOMSKIH DREVES in dobimo novo binomsko kopico, ki ne vsebuje vozlišča x.

Primer :

Minimum te binomske kopice je vozlišče s ključem 5, ki je obarvan vijolično.

1. korak:
Sedaj bomo ustvarili novo binomsko kopico H, ki bo vsebovala zaporedje poddreves (otrok) vozlišča s ključem 5, začenši s poddrevesom z najmanjšo stopnjo.

H pa naj bo prvotna binomska kopica, ki v zaporedju binomskih dreves, ne vsebuje binomskega drevesa, ki je vseboval vozlišče z minimalnim ključem 5.

2. korak:
Združimo H in H s pomočjo operacije UNIJA DVEH BINOMSKIH DREVES. Dobimo novo binomsko kopico brez minimalnega elementa.

Primer (malo težji):

1. korak:
Sedaj bomo ustvarili novo binomsko kopico H , ki bo vsebovala zaporedje poddreves (otrok) vozlišča s ključem 4, začenši s poddrevesom z najmanjšo stopnjo.

2. korak:
H pa naj bo prvotna binomska kopica, ki v zaporedju binomskih dreves, ne vsebuje binomskega drevesa, ki je vseboval vozlišče z minimalnim ključem 4.

3. korak:
H in H bomo združili s pomočjo operacije UNIJA DVEH BINOMSKIH DREVES. Prvo bomo binomska drevesa iz H in H razvrstili glede na stopnje dreves.

4. korak:
Kot vidimo imamo sedaj več binomskih dreves iste stopnje. Zato moramo drevesa iste stopnje združit s pomočjo operacije UNIJA DVEH BINOMSKIH DREVES.

Slika predstavlja končno rešitev.

VSTAVLJANJE NOVEGA VOZLIŠČA

• imamo podano binomsko kopico H
• ustvarimo novo binomsko kopico H, ki vsebuje novo vozlišče
• združimo H in H s pomočjo operacije UNIJA DVEH BINOMSKIH DREVES

Primer 1:

Slika H in H predstavlja končno rešitev.

Primer 2:

Tretja slika še ni vredu, saj imamo dve binomski drevesi enake stopnje, zato ju moramo še združiti.
Slika H in H predstavlja končno rešitev.

ZMANJŠANJE KLJUČA VOZLIŠČA

Preden pogledamo operacijo ZMANJAŠNJE KLJUČA VOZLIŠČA, si poglejmo, kako poiščemo določen ključ v binomski kopici:
Iskanje ključa (podatka) v binomski kopici je bolj zahteven proces kot pri navadni kopici. Naj bo ključ, ki ga iščemo y.
Najprej bomo pogledali korene vseh binomskih dreves, ki sestavljajo binomsko kopico.
Če je v katerem binomskem drevesu, ključ v korenu večji od y, potem ključa y v tem binomskem drevesu zagotovi ni.
V nasprotnem primeru pogledamo vse sinove korena. Upoštevamo le tiste sinove, katerih je ključ manjši od y.
Postopek nadaljujemo dokler ne naletimo na iskalni ključ y. V primeru, ko postopek nadaljujemo in pridemo do ključev v listih binomskega drevesa in tam ne najdemo kljč y, začnemo postopek od začetka na drugih binomskih drevesih.
V primeru pa, ko pregledamo vsa binomska drevesa v binomski kopici in ključa y nismo našli, potem ta ključ v binomski kopici ne obstaja.

OPERACIJA ZMANJŠANJE KLJUČA
Prvotni ključ nadomestimo z novim ključem (z manjšo vrednostjo). Ker hočemo ohraniti lastnost minimalne kopice, moramo pogledati očeta novega ključa. Če je ključ očeta manjši od novega ključa potem končamo. V nasprotnem primeru, vozlišče z novim ključem zamenjamo z vozliščem njegovega očeta. Postopek nadaljujemo, dokler je novi ključ večji od očetovega ali je novi ključ v korenu.

Primer 1:
Ključ 38 hočemo nadomestiti s ključem 10.

1. korak:
Ključ 38 nadomestimo z novim ključem 10.

2. korak:
Pogledamo ključ njegovega očeta. Ker je 26>10, vozlišči zamenjamo.

3. korak:
Pogledamo očeta, ključa 10. Ker je 14>10, vozlišči zamenjamo.

Ker smo prišli do korena binomskega drevesa, postopek končamo.

Primer 2:

1. korak:
Ključ 41 nadomestimo z novim ključem 10.

2. korak:
Pogledamo ključ njegovega očeta. Ker je 23>10, vozlišči zamenjamo.

3. korak:
Pogledamo očeta, vozlišča s ključem 10. Ker je 19>10, vozlišči zamenjamo.

4. korak:
Ključ očeta je sedaj 11, kar je večje od 10, zato vozlišči zamenjamo.

Ker smo prišli do korena binomskega drevesa, postopek končamo.

Primer 3:
Ključ 40 hočemo nadomestiti s ključem 18.

1. korak:
Vozlišče s ključem 40 zamenjamo z novim ključem 18.

2. korak:
Pogledamo ključ očeta od vozlišča z novim ključem. Ker je ključ očeta 22, večji od novega ključa, vozlišči zamenjamo.

3. korak:
Pogledamo ključ očeta od vozlišča s ključem 18. Ker je 17<18, je lastnost minimalne kopice izpolnjena, zato je zgornja slika končna rešitev.

Zakaj bo po vseh teh operacijah zadeva še vedno binomska kopica?
Kot vidimo pri zgornjem primeru vozlišče z novim ključem zamenjamo z vedno novim očetom, dokler ne izpolnimo lastnost minimalnih kopic v tem binomskem drevesu.
Za ostala poddrevesa v tem binomskem drevesu, ki niso vsebovala novega vozlišča, lastnost minimalnih kopic ne potrebujemo preverjat, saj smo morali preveriti že na začetku.
Za ostala binomska drevesa, ki niso vsebovala vozlišča z novim ključem, tudi ne potrebujemo preverjati, če je lastnost minimalnih kopic izpoljena, saj smo tudi to morali preveriti že na začetku.
Zato tudi po operaciji ZMANJAŠANJE KLJUČA VOZLIŠČA, binomska kopica ustreza njeni definiciji.

BRISANJE VOZLIŠČA

Zagotoviti moramo, da prvotna binomska kopica ( pred operacijo BRISANJE VOZLIŠČA) ne vsebuje ključa -. Ko hočemo določeno vozlišče izbrisati, vrednost njegovega ključa nadomestimo z -. S tem zagotovimo, da bo ta ključ minimalen v binomski kopici. Če je vozlišče s ključem - v korenu binomskega drevesa, vozlišče izbrišemo, kjer uporabimo operacijo BRISANJE MINIMALNEGA VOZLIŠČA. V nasprotnem primeru vozlišče s ključem - prepeljemo do korena (glej operacijo ZMANJŠANJE KLJUČA VOZLIŠČA) in ga nato odstranimo, kjer uporabimo operacijo BRISANJE MINIMALNEGA VOZLIŠČA.

Primer :

Binomska kopica je predstavljena kot niz ...

V binomski kopici je ključ očeta večji/manjši ali enak od ključa njegovega sina?

Vozlišče z minimalnim ključem, se v kopici nahaja ...

Preveri

Ko hočemo določeno vozlišče v binomski kopici izbrisati, vrednost njegovega ključa nadomestimo z ...

• Časovna zahtevnost za vse operacije ni velika.
• Uporabno v programih, kjer moramo podatke urediti po velikosti.
• Hitro lahko poiščemo minimalen element ( pogledati moramo samo korene binomskih dreves). Tukaj je časovna zahtevnost majhna.

1. //www.cs.princeton.edu/~wayne/cs423/lectures/heaps-4up.pdf
2. //www.cs.rochester.edu/~gildea/csc282/slides/C19-binomial.pdf
3. //wiki.fmf.uni-lj.si/wiki/Binomska_kopica
4. //en.wikipedia.org/wiki/Binomial_heap
5. //wiki.fmf.uni-lj.si/wiki/Binomsko_drevo
   PowerPoint datoteki:

1. www.cs.unc.edu/~plaisted/comp750/05-binheaps.ppt
2. //www.google.com/search?q=Tan+Van+Binomial+Heap+Presentation+site:caveshadow.com

Ključne besede:
ključ - podatek