A következő oktatóanyagban megismerjük a B fa adatstruktúráját, és megfontoljuk annak megjelenítését.
Tehát kezdjük.
Mi az a B fa?
A B Fa egy speciális típusú többirányú keresőfa , közismert nevén a M-út fa, amely egyensúlyba hozza magát. Kiegyensúlyozott szerkezetük miatt ezeket a fákat általában hatalmas adatbázisok működtetésére és kezelésére, valamint a keresések egyszerűsítésére használják. Egy B fában minden csomópontnak legfeljebb n gyermekcsomópontja lehet. A B Tree egy példa a többszintű indexelésre egy adatbázis-kezelő rendszerben (DBMS). A levél és a belső csomópontok egyaránt rendelkeznek rekordhivatkozással. A B fa kiegyensúlyozott tárolt fa néven ismert, mivel az összes levél csomópontja azonos szinten van.
A következő diagram egy példa egy B fára:
1.ábra. A B 3-as rendű fa
A B fa szabályainak megértése
A B fa fontos tulajdonságai a következők:
- Az összes levél csomópontja azonos szinten van.
- A B fa adatszerkezetét a minimális 'd' fokozat határozza meg. A 'd' értéke a lemezblokk méretétől függ.
- Minden csomópontnak, a gyökér kivételével, legalább d-1 kulcsból kell állnia. A gyökércsomópont legalább 1 kulcsból állhat.
- Az összes csomópont (beleértve a gyökércsomópontot is) legfeljebb a következőkből állhat (2d-1) kulcsok.
- Egy csomópont gyermekeinek száma egyenlő a a benne lévő kulcsok számának hozzáadása és .
- Egy csomópont összes kulcsa növekvő sorrendben van rendezve. A két billentyű, a k1 és k2 közötti gyermek a k1 és k2 közötti összes billentyűből áll.
- A bináris keresőfától eltérően a B fa adatszerkezete a gyökértől kezdve nő és zsugorodik. Míg a bináris keresőfa lefelé nő, és lefelé zsugorodik.
- A többi önkiegyensúlyozott bináris keresőfához hasonlóan a B fa adatszerkezetének időbonyolultsága az olyan műveletekhez, mint a keresés, beillesztés és törlés O(log?n) .
- Egy csomópont beillesztése a B fába csak a levélcsomópontnál történik.
Tekintsük a következő példát egy 5-ös minimális rendű B fára.
2. ábra. A B Rendfa 5
Megjegyzés: A minimális rendelés értéke jóval több, mint 5 egy gyakorlati B fák esetében.
A fenti diagramon megfigyelhetjük, hogy az összes levélcsomópont azonos szinten van, és az összes nem levélcsomópontnak nincs üres részfája, és eggyel kevesebb kulcsból áll, mint a gyermekei száma.
A B fa szabályainak beállított megfogalmazása:
Minden B fa egy pozitív állandó egész számtól függ MINIMÁLIS , amelyet az egyetlen csomópontban tárolható adatelemek számának meghatározására használnak.
1. szabály: A gyökér csak egy adatelemet tartalmazhat (vagy akár semmilyen adatelemet sem, ha nem is gyermek); minden más csomópont rendelkezik legalább MINIMÁLIS adatelemek.
2. szabály: Az egy csomópontban tárolt adatelemek maximális száma kétszerese az értékének MINIMÁLIS .
3. szabály: A B fa egyes csomópontjainak adatelemei egy részben kitöltött tömbben tárolódnak, a legkisebb adatelemtől (indexnél) rendezve. 0 ) a legnagyobb adatelemhez (a tömb végső használt pozíciójában).
4. szabály: A nem levél csomópont alatti részfák teljes száma mindig eggyel több, mint az adott csomópontban lévő adatelemek száma.
- részfa 0, részfa 1,...
5. szabály: A nem leveles csomópontok tekintetében:
- Az indexben lévő adatelem nagyobb, mint a részfa számában szereplő összes adatelem én a csomópontról, és
- Az indexben lévő adatelem kisebb, mint a részfa számában szereplő összes adatelem i+1 a csomópontról.
6. szabály: A B fában minden levél ugyanolyan mélységű. Így biztosítja, hogy a B fa megakadályozza a kiegyensúlyozatlan fa problémáját.
Műveletek egy B fa adatstruktúrán
Annak érdekében, hogy a műveletek során a B fa adatstruktúra egyik tulajdonsága se sérüljön, a B fa felosztható vagy egyesíthető. Az alábbiakban felsorolunk néhány műveletet, amelyeket elvégezhetünk egy B fán:
- Adatelem keresése a B fában
- Adatelem beszúrása a B fába
- Adatelem törlése a B fában
Keresési művelet egy B fán
Egy elem keresése a B fában hasonló a bináris keresőfában végzett kereséshez. De ahelyett, hogy kétirányú döntést hozna (balra vagy jobbra), mint egy bináris keresőfa, egy B fa m-irányú döntést hoz minden csomóponton, ahol m a csomópont gyermekeinek száma.
A B fában lévő adatelemek keresésének lépései:
1. lépés: A keresés a gyökércsomóponttól kezdődik. Hasonlítsa össze a k keresőelemet a gyökérrel.
1.1. lépés: Ha a gyökércsomópont a k elemből áll, a keresés befejeződik.
1.2. lépés: Ha a k elem kisebb, mint a gyökér első értéke, akkor a bal szélső gyermekre lépünk, és rekurzívan keresünk a gyermekben.
1.3.1. lépés: Ha a gyökérnek csak két gyermeke van, akkor a jobb szélső gyermekre lépünk, és rekurzív módon keresünk a gyermek csomópontokban.
1.3.2. lépés: Ha a gyökérnek kettőnél több kulcsa van, akkor a többiben keresni fogunk.
2. lépés: Ha a k elemet nem találjuk a teljes fa bejárása után, akkor a keresőelem nincs jelen a B fában.
Vizualizáljuk a fenti lépéseket egy példa segítségével. Tegyük fel, hogy egy k=34 kulcsot akartunk keresni a következő B fában:
3.1. ábra. Adott B fa
- Először is ellenőrizzük, hogy a kulcs k = 34 a gyökér csomópontban van. Mivel a kulcs nem a gyökérben található, áttérünk a gyermek csomópontjaira. Azt is megfigyelhetjük, hogy a gyökércsomópontnak két gyermeke van; ezért összehasonlítjuk a szükséges értéket a két kulcs között.
3.2. ábra. A k kulcs nincs jelen a gyökérben - Most, hogy észrevesszük, hogy a k kulcs nagyobb, mint a gyökércsomópont, azaz 30, a gyökér megfelelő gyermekével folytatjuk.
3.3. ábra. A k > 30 kulcs, lépjen a jobb oldali gyermekre - Most összehasonlítjuk a k kulcsot a csomóponton lévő értékekkel, azaz a 40-nel és az 50-nel. Mivel a k kulcs kisebb, mint a bal kulcs, azaz 40, a csomópont bal gyermekére lépünk.
3.4. ábra. A kulcs k<40, move to left child< li> - Mivel a 40 bal oldali gyermekében lévő érték 34, ami a szükséges érték, megállapíthatjuk, hogy a kulcs megtalálható, és a keresési művelet befejeződött.
3.4. ábra. A k kulcs = 34, a 40 bal gyermeke
A kulcsot a fenti példában négy különböző értékkel hasonlítottuk össze, amíg meg nem találtuk. Így egy B fában a keresési művelethez szükséges időbonyolultság az O(log?n) .
Művelet beszúrása egy B fára
Amikor egy adatelemet beszúrunk egy B fába, először ellenőriznünk kell, hogy az elem már szerepel-e a fában vagy sem. Ha az adatelem megtalálható a B fában, akkor a beillesztési művelet nem történik meg. Ha azonban nem ez a helyzet, akkor folytatjuk a beillesztést. Két forgatókönyvre kell ügyelni, amikor egy elemet a levél csomópontjába szúr be:
Az adatelem B fába való beszúrásának lépései:
1. lépés: Kezdjük azzal, hogy a B fa sorrendje alapján kiszámoljuk a csomópontban lévő kulcsok maximális számát.
2. lépés: Ha a fa üres, akkor a rendszer kijelöl egy gyökércsomópontot, és beillesztjük a gyökércsomópontként funkcionáló kulcsot.
3. lépés: Most megkeressük a megfelelő csomópontot a beillesztéshez.
4. lépés: Ha a csomópont megtelt:
4.1. lépés: Az adatelemeket növekvő sorrendben illesztjük be.
4.2. lépés: Ha az adatelemek nagyobbak, mint a kulcsok maximális száma, akkor a teljes csomópontot felosztjuk a mediánnál.
4.3. lépés: A középső billentyűt felfelé toljuk, a bal és jobb billentyűket pedig bal és jobb gyermekként osztjuk szét.
5. lépés: Ha a csomópont nem tele van, akkor a csomópontot növekvő sorrendben illesztjük be.
Vizualizáljuk a fenti lépéseket egy példa segítségével. Tegyük fel, hogy létre kell hoznunk egy 4-es sorrendű B fát. A B fába beszúrandó adatelemek a következők: 5, 3, 21, 11, 1, 16, 8, 13, 4 és 9 .
- Mivel m egyenlő 3-mal, a kulcsok maximális száma egy csomóponthoz = m-1 = 3-1 = 2 .
- A beillesztéssel kezdjük 5 az üres fában.
4.1. ábra. Beillesztés 5 - Most beszúrunk 3-at a fába. Mivel a 3 kisebb, mint 5, a 3-at beszúrjuk az 5-től balra ugyanabba a csomópontba.
4.2. ábra. Beillesztés 3 - Most beszúrjuk a 21-et a fába, és mivel a 21 nagyobb, mint 5, az 5-től jobbra lesz beszúrva ugyanabban a csomópontban. Mivel azonban tudjuk, hogy a csomópontban a kulcsok maximális száma 2, az egyik kulcs átkerül a fenti csomópontba, hogy feloszthassa azt. Így az 5, a középső adatelem felfelé fog mozogni, a 3 és a 21 pedig ennek bal és jobb oldali csomópontja lesz.
4.3. ábra. Beillesztés 21 - Most itt az ideje beszúrni a következő adatelemet, azaz a 11-et, amely nagyobb, mint 5, de kisebb, mint 21. Ezért a 11 kulcsként kerül beszúrásra a 21-ből álló csomópont bal oldalán kulcsként.
4.4. ábra. Beillesztés 11 - Hasonlóképpen a következő 1-es adatelemet illesztjük be a fába, és mint láthatjuk, 1 kisebb, mint 3; ezért kulcsként a 3-ból álló csomópont bal oldalán lesz beszúrva kulcsként.
4.5. ábra. Beillesztés 1 - Most beillesztjük a fába a 16-os adatelemet, amely nagyobb, mint 11, de kisebb, mint 21. A csomópontban lévő kulcsok száma azonban meghaladja a kulcsok maximális számát. Ezért a csomópont kettéválik, és a középső kulcsot a gyökérbe mozgatja. Ezért a 16 az 5-től jobbra lesz beszúrva, és a 11-et és a 21-et két különálló csomópontra osztja.
4.6. ábra. Beillesztés 16 - A 8-as adatelem kulcsként kerül beillesztésre a 11-től balra.
4.7. ábra. Beillesztés 8 - A fába 13-at fogunk beszúrni, ami 16-nál kisebb és 11-nél nagyobb. Ezért a 13-as adatelemet a 8-as és 11-es csomóponttól jobbra kell beilleszteni. Mivel azonban a fában a kulcsok maximális száma Ha csak 2, akkor felosztás történik, és a középső 11 adatelem a fenti csomópontba kerül, a 8 és 13 pedig két különálló csomópontba. Most a fenti csomópont 5-ből, 11-ből és 16-ból fog állni, ami ismét meghaladja a maximális kulcsszámot. Ezért lesz egy másik felosztás, aminek következtében a 11 adatelem lesz a gyökércsomópont, amelynek gyermekei 5 és 16.
4.8. ábra. Beillesztés 13 - Mivel a 4. adatelem kisebb, mint 5, de nagyobb, mint 3, az 1-ből és 3-ból álló csomópont jobb oldalára kerül beillesztésre, ami ismét meghaladja a kulcsok maximális számát egy csomópontban. Ezért ismét kiömlés történik, és a 3-at az 5-ös melletti felső csomópontra helyezi.
4.9. ábra. Beillesztés 4 - Végül a 9-es adatelem, amely nagyobb, mint 8, de kisebb, mint 11, kulcsként bekerül a 8-as csomópont jobb oldalán.
4.10. ábra. Beillesztés 9
A fenti példában különböző összehasonlításokat végeztünk. Az első érték közvetlenül bekerült a fába; ezt követően minden értéket össze kellett hasonlítani a fában elérhető csomópontokkal. A beszúrási művelet időbonyolultsága egy B fában a csomópontok számától és a .
Művelet törlése egy B fán
Egy adatelem törlése egy B fán három elsődleges eseményt tartalmaz:
- Keresi azt a csomópontot, ahol a törölni kívánt kulcs található,
- A kulcs törlése, és
- Ha szükséges, kiegyensúlyozza a fát.
Amikor egy elemet töröl a fából, az Underflow néven ismert állapot léphet fel. Alulcsordulás akkor fordul elő, ha egy csomópont a minimális számú kulcsból áll; tartania kellene.
A törlési/eltávolítási művelet megjelenítése előtt meg kell érteni a következő kifejezéseket:
Az alábbiakban a törlési művelet három kiemelkedő esete látható egy B fában:
1. eset: A kulcs törlése/eltávolítása a Leaf csomópontban található - Ez az eset még két különböző esetre oszlik:
1. A kulcs törlése/eltávolítása nem sérti a kulcsok minimális számának tulajdonságát, amelyet egy csomópontnak tartalmaznia kell.
Vizualizáljuk ezt az esetet egy példa segítségével, ahol a következő B fából töröljük a 32-es kulcsot.
4.1. ábra: Egy levél csomópont kulcsának (32) törlése a B fából
Mint láthatjuk, a 32 törlése ebből a fából nem sérti a fenti tulajdonságot.
2. A kulcs törlése/eltávolítása sérti a csomópontban tárolt kulcsok minimális számának tulajdonságát. Ebben az esetben kölcsön kell kölcsönöznünk egy kulcsot annak közeli testvércsomópontjától, balról jobbra sorrendben.
ábécé számozott
Először is meglátogatjuk a közeli baloldali testvért. Ha a bal oldali testvér csomópontnak a minimálisnál több kulcsa van, akkor ettől a csomóponttól kölcsönöz egy kulcsot.
Ellenkező esetben ellenőrizni fogjuk, hogy a közeli jobb oldali testvér csomóponttól kérjünk kölcsönt.
Vizualizáljuk ezt az esetet egy példa segítségével, ahol a fenti B fából töröljük a 31-et. Ebben az esetben kölcsönkérünk egy kulcsot a bal oldali testvércsomóponttól.
4.2. ábra: Egy levél csomópont kulcsának (31) törlése a B fából
Ha mindkét közeli testvércsomópont már minimális számú kulcsból áll, akkor a csomópontot vagy a bal oldali testvércsomóponttal egyesítjük, vagy a jobb oldali testvércsomóponttal. Ez az egyesítési folyamat a szülőcsomóponton keresztül történik.
Vizualizáljuk újra úgy, hogy töröljük a 30-as kulcsot a fenti B fából.
4.3. ábra: Egy levél csomópont kulcsának (30) törlése a B fából
2. eset: A kulcs törlése/eltávolítása a nem Leaf csomópontban rejlik - Ez az eset további esetekre oszlik:
1. Az eltávolított nem levél/belső csomópont helyébe egy sorrendbeli előd lép, ha a bal oldali gyermekcsomópontnak több kulcsa van, mint a minimális számú kulcs.
Vizualizáljuk ezt az esetet egy példa segítségével, ahol a 33-as kulcsot töröljük a B fából.
4.4. ábra: Egy levél csomópont kulcsának (33) törlése a B fából
2. Az eltávolított nem Leaf/Belső csomópont helyébe egy sorrendi utód kerül, ha a jobb oldali gyermekcsomópontnak több kulcsa van, mint a minimális számú kulcs.
Ha bármelyik gyermeknek van minimális számú kulcsa, akkor összevonjuk a bal és a jobb gyermek csomópontokat.
Vizualizáljuk ezt az esetet úgy, hogy töröljük a 30-as kulcsot a B fából.
4.5. ábra: Egy levél csomópont kulcsának (30) törlése a B fából
Egyesítés után, ha a szülőcsomópontnak kevesebb kulcsa van, mint a minimális számú kulcs, meg lehet keresni a testvéreket, mint a 1. eset .
3. eset: A következő esetben a fa magassága csökken. Ha a célkulcs egy belső csomópontban található, és a kulcs eltávolítása kevesebb kulcsot eredményez a csomópontban (ami kevesebb, mint a minimálisan szükséges), akkor keresse meg a sorrendbeli elődöt és a sorrendi utódát. Ha mindkét gyereknek megvan a minimális számú kulcsa, akkor a kölcsönzés nem lehetséges. Ez ahhoz vezet 2. eset (3) , azaz a gyermek csomópontok összevonása.
Újra meg fogjuk keresni a testvért, hogy kulcsot kérjünk. Ha azonban a testvér is minimális számú kulcsból áll, akkor a csomópontot összevonjuk a testvérrel a szülőcsomóponttal együtt, és a gyermekcsomópontokat a követelmények szerint rendezzük el (növekvő sorrendben).
Vizualizáljuk ezt az esetet egy példa segítségével, ahol a 10-es adatelemet töröljük az adott B fából.
4.6. ábra: Egy levél csomópont kulcsának (10) törlése a B fából
A fenti példákban az idő bonyolultsága attól függően változik, hogy a kulcsot melyik helyről kell törölni. Így a törlési művelet időbeli összetettsége egy B fában az O(log?n) .
A következtetés
Ebben az oktatóanyagban megismerkedtünk a B fával, és különböző példákkal szemléltettük annak különböző műveleteit. Megértettük a B fa néhány alapvető tulajdonságát és szabályát is.