B-drevo

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

B-drevo je posplošitev 2-3 drevesa. B-drevo reda m je m-smerno iskalno drevo, ki je ali prazno ali višine vsaj 2. 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 med 2 in m sinov. Vsi listi so na istem nivoju.

Dve različici 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

Vsebina

Časovna zahtevnost

  • vse operacije se v najslabšem možnem primeru izvedejo v času reda O(log n). Pri tem je m konstanten (preiskovanje elementov znotraj enega vozlišča lahko izvedemo v konstantnem času);
  • če je m velik: elemente v enem vozlišču preiskujemo z bisekcijo, v času reda O(log m).

Iskanje elementa

To je v bistvu posplošitev iskanja v navadnih iskalnih drevesih. Tukaj namesto, da bi primerjali iskani element z enim elementom v vozlišču je potrebno iskani element primerjati z elementi v vozlišču, dokler:

  • na naletimo na iskani element,
  • ne naletimo na večji element in se zato iskanje rekurzivno nadaljuje v poddrevesu z istim indeksom,
  • ne pregledamo zadnjega elementa in se iskanje rekurzivno nadaljuje v zadnjem poddrevesu.

Primer

Radi bi poiskali črko I.

image:13bdrevo.JPG

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šče imelo m elementov, se vozlišče razbije na tri dele:
    1. vozlišče s prvimi 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 dve vozlišči 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. Rekurzija se ustavi bodisi pri 1. ali 2.a 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č več. Zato si sposodimo M, ki ga premaknemo v koren in J združimo s F. Vendar ne pozabimo na vozlišče [K L], ki se prestavi na desno pod J.

image:12bdrevo.JPG

Glej tudi

Zunanje povezave

Osebna orodja