B-drevo

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 10:02, 7 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Primer
← Prejšnja različica
Različica od 10:10, 7 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Primer
Naslednja različica →
Vrstica 52: Vrstica 52:
Nadaljujemo tako, da najdemo takojšnjega naslednika, v naše primeru je to črka D, in ga premaknemo, da nadomestimo črko C. Ampak s tem smo dobili vozlišče s premalo ključi. Nadaljujemo tako, da najdemo takojšnjega naslednika, v naše primeru je to črka D, in ga premaknemo, da nadomestimo črko C. Ampak s tem smo dobili vozlišče s premalo ključi.
::[[image:10bdrevo.JPG]] ::[[image:10bdrevo.JPG]]
- +Ker sosednja vozlišča od E nimata preveč ključev, moramo vozlišče E združiti z enim od njiju. Združimo ga recimo z vozliščem [A B].
 +::[[image:11bdrevo.JPG]]
 +Ampak sedaj vozlišče F nima dovolj ključev. Vendar ima njegov sosed en ključ "ekstra". Zato si sposodimo M, ki ga premaknemo v koren in J združimo z F. Vendar ne pozabimo na vozlišče [K L], ki se prestavi na desno pod J.
 +::[[image:12bdrevo.JPG]]

Različica od 10:10, 7 maj 2006

Vsebina

Lastnosti B-dreves

B-drevesa so posplošitev 2-3 dreves. Vsako notranje vozlišče reda m ima lahko od m/2 do m sinov ter en ključ (element) manj kot ima sinov. Torej ima vsako vozlišče vsaj m/2-1 in največ m-1 elementov. Tako ima vsak ključ levo in desno poddrevo, kjer je desno poddrevo i-tega ključa enako levemu poddrevesu i+1-vega ključa. Izjema je koren drevesa. Če je koren notranje vozlišče, ima lahko 2 do m sinov. Vsi listi so na istem nivoju.
Dve varianti B-dreves:

  1. B-drevesa, kjer so vsi elementi shranjeni v listih; vsak list vsebuje en element
  2. B-drevesa, kjer so vsi elementi shranjeni v notranjih vozliščih; v tem primeru so vsi listi prazna poddrevesa

VSTAVLJANJE ELEMENTA:


Element vedno dodajamo v ustrezno notranje vozlišče največje globine. Možna sta 2 primera:

  1. Če je v notranjem vozlišču največje globine prostor (če je tam manj kot m-1 elementov) element na ustrezno mesto dodamo in postopek je končan.
  2. Če ni prostora, kar pomeni, da bi z dodajanjem vozlišča imelo m elementov, se vozlišče razbije na tri dele;
    1. vozlišče s prvim m/2 -1 elementi
    2. m/2 -ti element
    3. vozlišče s preostalimi m - m/2 elementi

Na ta način dobimo nov m/2 - ti element z ustreznima dvema poddrevesoma, ki ga rekurzivno dodamo očetu prejšnjega vozlišča. Rekurzija se izteče bodisi pri 1. točki, bodisi smo v korenu drevesa (vozlišče nima očeta). V tem primeru dobimo nov koren drevesa, ki vsebuje m/2-ti element ter ustrezni poddrevesi, torej se nivo drevesa poveča za 1.

Primer

Vstavimo naslednje črke: C N G A H E K Q M F W L T Z D P R X Y S v prazno B-drevo reda 5. Red 5 pomeni, da ima vozlišče največ 5 otrok in 4 ključe. Vsa vozlišča, razen očeta morajo imeti vsaj 2 ključa. Torej začnemo tako, da vstavimo prve štiri črke kot je prikazano na sliki:

image:1bdrevo.JPG

Ko poskušamo vstaviti črko H, vidimo da v vozlišču ni več prostora, zato ga moramo razdeliti v dva vozlišča, tako da premaknemo črko G v koren.

image:2bdrevo.JPG

Ko vstavimo naslednje črke E,K in Q nam ni treba razcepiti vozlišč, saj je dovolj prostora.

image:3bdrevo.JPG

Pri vstavljanju črke M vidimo, da bo potreben razcep. Ker je M srednji ključ, ga postavimo v koren.

image:4bdrevo.JPG

Naslednje črke F,W,L in T lahko vstavimo brez razcepov.

image:5bdrevo.JPG

Ko vstavimo Z je potreben razcep tretjega vozlišča. Srednji element T premaknemo v koren. S tem ko premaknemo srednji element, ohranjamo drevo v ravnovesju.

image:6bdrevo.JPG

Pri vstavljanju črke D v drevo je potreben razcep najbolj levega vozlišča. D je srednji element, zato ga premaknemo v koren. Naslednje črke P,R,X in Y lahko vstavimo brez razcepa.

image:7bdrevo.JPG

Ko vstavimo naslednjo črko S, se razcepi vozlišče [N,P,Q,R]. Ker je že polno pošljemo srednji element v koren. Ker je tudi koren poln, se razcepi na dva dela, tako da pošlje srednji element M v nov koren.

image:8bdrevo.JPG

BRISANJE ELEMENTA:


Pri brisanju elementa iz drevesa se element, če ni v vozlišču na zadnjem nivoju, nadomesti s predhodnikom, maksimalnim elementom ustreznega levega poddrevesa. Na ta način se element briše vedno iz vozlišča na zadnjem nivoju. Možna sta 2 primera:

  1. Če je v vozlišču kjer smo element zbrisali, še vedno vsaj m/2 - 1 elementov, potem je postopek končan. Če je vozlišče koren, potem zadošča že en element.
  2. Če je v vozlišču sedaj m/2 - 2 elementov, potem:
    1. Eden izmed sosednjih bratov (levi ali desni) vsebuje m/2 ali več elementov. V tem primeru se iz ustreznega brata lahko vzame en ali več elementov skupaj z ustreznimi poddrevesi in zamenjavo ustreznega elementa pri očetu, tako da imata obe vozlišči vsaj m/2 - 1 elementov.
    2. Če nobeden od bratov nima vsaj m/2 elementov, potem imamo dva brata, ki imata skupaj z ustreznim elementom v očetu naslednje število elementov, ki jih lahko združimo v eno vozlišče: m/2 - 2 + m/2 - 1 + 1 <= m - 1
Sedaj ima oče enega sina manj in se celoten postopek rekurzivno ponovi pri očetu. (zgled) Rekurzija se ustavi bodisi pri 1 ali 2a točki ali pa pri korenu, ki nima nobenega elementa več in eno samo poddrevo. V slednjem primeru lahko koren zbrišemo in edino poddrevo postane novo drevo. Torej se v tem primeru nivo drevesa zmanjša za 1.

Primer

Imamo podano B-drevo reda 5. Radi bi izbrisali črko C.

image:9bdrevo.JPG

Nadaljujemo tako, da najdemo takojšnjega naslednika, v naše primeru je to črka D, in ga premaknemo, da nadomestimo črko C. Ampak s tem smo dobili vozlišče s premalo ključi.

image:10bdrevo.JPG

Ker sosednja vozlišča od E nimata preveč ključev, moramo vozlišče E združiti z enim od njiju. Združimo ga recimo z vozliščem [A B].

image:11bdrevo.JPG

Ampak sedaj vozlišče F nima dovolj ključev. Vendar ima njegov sosed en ključ "ekstra". Zato si sposodimo M, ki ga premaknemo v koren in J združimo z F. Vendar ne pozabimo na vozlišče [K L], ki se prestavi na desno pod J.

image:12bdrevo.JPG
Osebna orodja