6.7. B-fa

A kiegyensúlyozott fák egy igen gyakran alkalmazott osztálya a Bayer-fa, röviden B-fa. A B-fa egyébként J. Hopcroft 2-3 fájának általánosítása. A B-fa nem bináris fa, egy n-edrendű B-fa minden belső csúcsa (az itt használatos terminológiában lap) maximum 2n + 1 mutatót és maximum 2n kulcsot tartalmazhat. Az adatok a fa külső csúcsaiban, a levelekben helyezkednek el. Minden belső csúcs a gyökeret kivéve legalább n kulcsot és n + 1 mutatót tartalmaz. A kulcsok egy lapon nagyság szerint rendezettek, és két szomszédos kulcs közötti mutató által jelölt részfa minden kulcsának értéke e két kulcs közé esik. (A soron következő ábrákon az egyszerűség kedvéért csak a belső csúcsokat jelöljük.)

B-fa műveletek

Keresésnél: ha a keresett kulcs – a belső csúcsban található első kulcsnál kisebb, akkor az első mutató által jelölt részfában kell folytatni a kutatást. – az utolsó, m-dik kulcsnál nagyobb, akkor az m + 1-dik mutató által jelölt részfában kell folytatni a kutatást. – az i-dik és i+1-dik kulcsok közé esik (vagy egyenlő a másodikkal), akkor az i + 1-dik mutató által jelölt részfában kell folytatni a kutatást. – Ha valamely mutató Nil, akkor a keresett elem nem szerepel a fában. Beszúrásnál: először megkeressük a beszúrandó elem helyét, a megfelelő levelet, azaz a külső csúcsokat közvetlenül megelőző belső csúcsot. – Ha ebben belső csúcsban még nincs 2n kulcs, akkor nagyság szerint beszúrjuk a kulcsot, és a kulcsot követő mutatót a beszúrt elemre állítjuk. – Ha az adott belső csúcs megtelt, de az egyik szomszédos levélen még van üres hely, akkor az első vagy utolsó kulcsot átmozgatjuk az apacsúcsra, míg az ott levő megfelelő kulcsot pedig a szomszédos levélre visszük. – Ha mind az adott csúcs, és a két szomszédos csúcs is megtelt, akkor a létrehozunk egy új levelet, az ideeső 2n+1 értékből az utolsó n-et átvisszük ide, az n + 1-diket pedig az apacsúcsba szúrjuk be.

Törlésnél: ha nem levélből törlünk, akkor a kulcsot a szabványnak megfelel ően, a nála kisebb kulcsok közül a maximálissal cseréljük ki, s azt a kulcsot töröljük valamely levélből. Levélből törlés esetén, ha n-nél kevesebb kulcs marad a levélben, a szomszédos levelekből kell kiegészíteni egy kulccsal. Ha azok mindegyikében csak n kulcs található, akkor a két szomszédos csúcsot össze kell vonni, és kiegészíteni az apacsúcsból egy elemmel. Ezek után meg kell vizsgálni az apaelemet is.

A [1] könyvben megtalálható a beszúrás programja pszeudónyelven, de a törlés programja már innen is kimaradt a mérete miatt. Épp ezért itt mi nem szerepeltetjük a programot, csak egy hosszabb példát beszúrásra és törlésre.

6.5. példa - 13. példa a B-fába beszúrásra

Sorra szúrjuk be egy B-fába sorra a N, D, W, K, B, A, P, R, X, G, Q, L, V, C, E, T, Y, U, F, Z, O kulcsokat, majd ugyanebben a sorrendben töröljük is a következő példában.

6.26. ábra - N, D, W, K beszúrása

N, D, W, K beszúrása


Az. ábrán a K beszúrása után betelt a 4 hely, ezért a következő elem beszúrásakor két új tárolót nyitunk. A középső érték marad az eredetiben, a többit szétdobáljuk.

6.27. ábra - B és A beszúrása

B és A beszúrása


6.28. ábra - P és R beszúrása

P és R beszúrása


Az X nem fér be az jobboldali levélbe, de a a baloldali levélben még van üres hely, ezért forgatunk.

6.29. ábra - X beszúrása átforgatással

X beszúrása átforgatással


(Más megvalósításokban a forgatás helyett újabb tárolókat alkalmaznak, tehát más könyvek, vagy más megvalósítások nem biztos, hogy ugyanezeket a fákat generálják.)

6.30. ábra - G beszúrása új levél nyitásával

G beszúrása új levél nyitásával


6.31. ábra - Q és L beszúrása

Q és L beszúrása


6.32. ábra - V beszúrása új levél nyitásával

V beszúrása új levél nyitásával


6.33. ábra - C beszúrása

C beszúrása


6.34. ábra - E beszúrása forgatással

E beszúrása forgatással


6.35. ábra - T beszúrása

T beszúrása


6.36. ábra - Y beszúrása

Y beszúrása


6.37. ábra - U beszúrása

U beszúrása


6.38. ábra - F beszúrása új levél nyitásával

F beszúrása új levél nyitásával


6.39. ábra - Z beszúrása

Z beszúrása


6.40. ábra - O beszúrása

O beszúrása



6.6. példa - 14. példa törlésre

6.41. ábra - N törlése

N törlése


6.42. ábra - D törlése

D törlése


6.43. ábra - W törlése

W törlése


Hogy a K kulcsot töröljük a felső tárolóból, helyére fel kell húzni a nála kisebb kulcsokból a maximálist, a G-t. Viszont a megfelelő tárolóban legalább két elemnek lennie kell, ezért valamely szomszédból pótoljuk a hiányt, azaz átforgatunk.

6.44. ábra - K törlése forgatással az első levélbő

K törlése forgatással az első levélbő


A B törlésekor az első tárolóban már nem marad két érték, a szomszédból sem lehet kölcsönkérni, ezért a két első tárolót összevonjuk, és a hozzájuk csapjuk a felső tároló első elemét.

6.45. ábra - B törlése levelek összevonásával

B törlése levelek összevonásával


6.46. ábra - A törlése

A törlése


A P törlésekor az O-t fel kell húzni, de a második tárolóban ezzel kevés kulcs marad, ezért a harmadikból forgatunk át egy elemet.

6.47. ábra - P törlése Q felhuzásával és Q átforgatásával

P törlése Q felhuzásával és Q átforgatásával


6.48. ábra - R törlése

R törlése


6.49. ábra - X törlése

X törlése


6.50. ábra - A G törlésekor az őt megelőző kulccsal helyettesítjük

A G törlésekor az őt megelőző kulccsal helyettesítjük


A Q törlésekor a lenti tárolókban már kevés kulcs maradt, ezért a második és harmadik tárolót összevonjuk.

6.51. ábra - Q törlése levelek összevonásával

Q törlése levelek összevonásával


6.52. ábra - L törlése

L törlése


6.53. ábra - V törlése

V törlése


6.54. ábra - C, E és T törlése

C, E és T törlése


6.55. ábra - Y törlése levelek összevonásával jár

Y törlése levelek összevonásával jár