Je rekurzivna podatkovna struktura, kjer velja:

Dobro vedeti :

• v binomskem drevesu je elementov ;
• - k nam pove koliko je višina (globina) drevesa ;
• Število vseh vozlišč D(k,i) na globini i je ;

Primer binomskega drevesa

Najprej smo si zelo na hitro pogledali kaj je binomsko drevo. Poznavanje le tega nam bo prišlo prav pri predstavitvi binomske kopice.

Definicija: Binomska kopica H (Vuillemin, 1978) je podatkovna struktura sestavljena iz več binomskih dreves in ima naslednje lastnosti:

• Binomska drevesa v kopici imajo lastnost minimalnih kopic (angl. min-heap-ordered trees). To pomeni, da je podatek v levem oziroma desnem poddrevesu vedno večji ali enak podatku v korenu drevesa.

• Za vsako nenegativno število k, obstaja največ eno binomsko drevo v kopici, katerega koren ima stopnjo k.

• Velja: V binomski kopici so binomska drevesa po redu razvrščena naraščujoče od leve proti desni.

Prva lastnost nam pove, da je koren drevesa vedno najmanjši element v drevesu.

Druga lastnost nam pove, da binomska kopica H z n-vozlišči vsebuje največ log n+1 binomskih dreves. Število binomskih dreves v binomski kopici je odvisno od števila vozlišč. Vsako binomsko drevo predstavlja števko 1 v binarnem zapisu števila n. Poglejmo si naslednji zgled.

Zgled :

Binomska kopica s 4 drevesi stopenj 0,1,2,3

Naša kopica ima 15 elementov (n). Naredimo binarni zapis števila 15:

15 : 2 = 7 + 1 ---> 1 * = 1

7 : 2 = 3 + 1 ---> 1 * = 2

3 : 2 = 1 + 1 ---> 1 * = 4

1 : 2 = 0 + 1 ---> 1 * = 8

15 v binarnem zapisu : 1 * + 1 *+ 1 * +1 *

Največji eksponent določa stopnjo binomskega drevesa.

Z pretvorbo smo dobili odgovor na vprašanje : koliko binomskih dreves sestavlja našo kopico in katerega reda je posamezno drevo ?

Odgovor : Imamo 4 binomska drevesa (pri vsakem deljenju je ostanek različen od 0)in imajo red 0, 1 , 2 , 3.

• Unija dveh kopic;
• Brisanje minimuma;
• Vstavljanje novega vozlišča;
• Zmanjšanje ključa;
• Brisanje vozlišča.

Ko združujemo dve binomski kopici H1 in H2 ven dobimo novo binomsko kopico H.

POSTOPEK ZDRUŽEVANJA :

• H1 in H2 združimo, tako da najprej binomska drevesa iz H1 in H2 razvrstimo glede na stopnje oziroma red dreves. Razvrstimo jih od najmanšega reda do največjega.

• Če imamo po prvem koraku v H več dreves iste stopnje, potem sledi, da moramo združiti tudi te med seboj. Za koren združenih dreves vzamemo tistega, ki ima manjši ključ. Binomsko drevo z večjim ključem v korenu pa postane levo poddrevo združenega binomskega drevesa H.

• Postopek združevanja se konča tedaj, ko so vsa binomska drevesa v novo nastali kopici različnih stopenj, in ko je izpolnjena lastnost minimalne kopice.

Zgled :

Imamo dve drevesi H1 IN H2, kateri bomo združili. Vidimo, da je H1 sestavljena iz enega binomskega drevesa reda . H2 je sestavljen iz dveh binomskih dreves reda in reda .

Unija dveh kopic

Naslednji korak v postopku je, da združimo med seboj drevesa istih stopenj. Stopnje so razporejene od najmanjše do največje. Ker velja pravilo, da se vsaka stopnja v binomski kopici pojavi samo enkrat, moramo upoštevati tudi to.

Unija dveh kopic

Pravilo pravi, da binomsko drevo, katero ima večji ključ v korenu postane levo podddrevo našega novega drevesa. Vemo tudi da sta število vozlišč in sestava binomske kopice močno povezani torej lahko preverimo naslednje: Vozlišč v H1 in H2 je skupno 9, v binomskem zapisu 1001 = 1* + 0* + 0 * + 1 * . Zapis nam pove, da je novo nastala binomska kopica H sestavljena iz binomskih dreves reda 0 in 3.

Nova binomska kopica

Do sedaj vemo, da se najmanjši podatek nahaja v korenu enega izmed binomskih dreves, ki sestavljajo binomsko kopico. Sledi, da moramo potem ponovno na novo sestaviti kopico.

POSTOPEK BRISANJA MINIMUMA :

• Izmed vseh dreves, ki sestavljajo binomsko kopico vzamemo tistega, ki ima najmanjši koren in ga odstranimo. Njegove sinove pa uporabimo v novi binomski kopici, in sicer v obratnem vrstnem redu, kot so bili v trenutni kopici.

• Po izbrisanem korenu se nam podre struktura drevesa in ne zadošča pogojem binomske kopice zato ga moramo popraviti.

Zgled : Znotraj binomske kopice na sliki pogledamo katero binomsko drevo ima najmanjšo vrednost v korenu. To je naš minimum.

***

Binomsko drevo, zapisan v obratnem vrstnem redu,kot je bil v trenutni kopici ter preostali del trenutne kopice.

***

Od tu naprej že znamo nadaljevati, imamo 2 binomski drevesi, ki ju med seboj združimo. Najprej poskrbimo za stopnje dreves (red dreves). .

***

Stopnje združimo.

***

Binomska kopica ima 12 vozlišč, binarni zapis: 1*+1*+0*+0*

Nova binomska kopica

POSTOPEK VSTAVLJANJA :

• H1- podana kopica;
• H2- kopica, ki vsebuje podatek, ki ga želimo vstaviti v podano kopico.

Sedaj ni več problem kako združiti dve kopici :). Glej postopek : unija.

:)

:)

:)

:)

:)

• Gre za to, da zamenjamo nek podatek v kopici z drugim manjšim podatkom. Takoj, ko posežemo v kopico se zna zgoditi, da ne zadošča več lastnostim binomske kopice.

• Sledi, da moramo vstavljeni podatek preveriti še s svojim očetom (korenom). Če je koren večji kot nov podatek ju zamenjamo (izpolnujemo lastnost o minimalni kopici).
• Ta postopek ponavljamo dokler ni koren manjši od vstavljenega podatka oziroma dokler ne pridemo do "glavnega" korena v binomskem drevesu.

POSTOPEK :

Deluje v treh korakih. Najprej poiščemo vozlišče s ključem, ki ga želimo zbrisati. Nato vrednost tega ključa zmanjšamo na . Potem uporabimo postopek za brisanje minimuma ter postopek združitev dveh kopic.

• binomske kopice so sestavljene iz binomskih dreves;
• za binomska drevesa znotraj binomske kopice velja lastnost minimalnih kopic;
• UPORABA: hitro iskanje podatkov;
• nad binomskimi kopicami izvajamo operacije : unija dveh kopic,brisanje minimuma, vstavljanje novega vozlišča, zmanjšanje ključa, brisanje vozlišča

• http://wiki.fmf.uni-lj.si/wiki/Binomsko_drevo

• http://wiki.fmf.uni-lj.si/wiki/Binomska_kopica

• http://www.nauk.si/materials/5048/out/#state=1

• www.cs.unc.edu/~plaisted/comp750/05-binheaps.ppt

• http://www.csc.uvic.ca/courses/csc326/201009/heaps-4up.pdf

Poglejte si še: naloge