B-drevo

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 08:39, 7 maj 2006
AleksandraVujasin (Pogovor | prispevki)

← Prejšnja različica
Različica od 09:36, 7 maj 2006
AleksandraVujasin (Pogovor | prispevki)
VSTAVLJANJE ELEMENTA:
Naslednja različica →
Vrstica 15: Vrstica 15:
## m/2 -ti element ## m/2 -ti element
## vozlišče s preostalimi m - m/2 elementi ## 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. +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]]
==BRISANJE ELEMENTA:== ==BRISANJE ELEMENTA:==

Različica od 09:36, 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

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.
Osebna orodja