B-drevo

Iz MaFiRaWiki

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

← Prejšnja različica
Različica od 08:38, 7 maj 2006
AleksandraVujasin (Pogovor | prispevki)

Naslednja različica →
Vrstica 5: Vrstica 5:
# B-drevesa, kjer so vsi elementi shranjeni v notranjih vozliščih; v tem primeru so vsi listi prazna poddrevesa # B-drevesa, kjer so vsi elementi shranjeni v notranjih vozliščih; v tem primeru so vsi listi prazna poddrevesa
-VSTAVLJANJE ELEMENTA:+==VSTAVLJANJE ELEMENTA:==
<br/> <br/>
Element vedno dodajamo v ustrezno notranje vozlišče največje globine. Element vedno dodajamo v ustrezno notranje vozlišče največje globine.
Vrstica 16: Vrstica 16:
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.
-BRISANJE ELEMENTA:+==BRISANJE ELEMENTA:==
<br/> <br/>
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. 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.

Različica od 08:38, 7 maj 2006

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.

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