B TREE az adatszerkezetben: keresés, beszúrás, törlés műveleti példa

Mi az a B fa?

A B Tree egy önkiegyensúlyozó adatstruktúra, amely az adatok gyorsabb és memória-hatékonyabb keresésére, beillesztésére és törlésére szolgáló speciális szabályrendszeren alapul. Ennek eléréséhez a következő szabályokat kell betartani egy B fa létrehozásához.

A B-fa egy speciális fa az adatstruktúrában. 1972-ben ezt a módszert először McCreight vezette be, és Bayer elnevezte Height Balanced m-way Search Tree néven. Ez segít az adatok rendezésében és a különböző műveletek, például a beszúrás, a keresés és a törlés megőrzésében, kevesebb idő alatt.

Ebben a B-Tree oktatóanyagban megtudhatja:

• Mi az a B fa?
• Miért érdemes használni a B-Tree-t?
• B fa története
• Keresés művelet
• Helyezze be a műveletet
• Művelet törlése

A B-Tree szabályai

Itt vannak a B_Tree létrehozásának fontos szabályai

• Minden levél ugyanazon a szinten lesz létrehozva.
• A B-fát egy fokozat határozza meg, amelyet "rendnek" is neveznek (amelyet egy külső szereplő, például egy programozó határoz meg), amelyet

  m

  tovább. Az értéke

  m

  attól a blokk méretétől függ, amelyen az adatok elsősorban találhatók.
• A csomópont bal részfájának kisebb értékei lesznek, mint az alfa jobb oldalának. Ez azt jelenti, hogy a csomópontok is növekvő sorrendben vannak rendezve balról jobbra.
• A gyermekcsomópontok, egy gyökércsomópont, valamint annak gyermekcsomópontjai maximális számát a következő képlet alapján számíthatjuk ki:

  m - 1

  Például:

  m = 4max keys: 4 - 1 = 3

• A gyökér kivételével minden csomópontnak tartalmaznia kell a

  [m/2]-1

  Például:

  m = 4min keys: 4/2-1 = 1

• Egy csomópont rendelkezésére álló gyermekcsomópontok maximális száma megegyezik annak mértékével, ami

  m

• A csomóponton belüli legkisebb gyermekek száma a sorrend fele, amely m / 2 (a felső értéket vesszük).
• A csomópont összes kulcsa növekvő sorrendben van rendezve.

Miért érdemes használni a B-Tree-t?

Itt vannak a B-Tree használatának okai

• Csökkenti a lemezen végrehajtott olvasások számát
• A B fák könnyen optimalizálhatók a méretének (vagyis a gyermekcsomópontok számának) a lemez méretének megfelelő beállításához
• Ez egy speciálisan kialakított technika nagy mennyiségű adat kezelésére.
• Hasznos algoritmus az adatbázisok és fájlrendszerek számára.
• Jó választás nagy adatblokkok olvasása és írása esetén

B fa története

• Az adatokat blokkokban tárolják a lemezen, ezeket az adatokat, amikor a fő memóriába (vagy RAM-ba) kerülnek, adatszerkezetnek nevezzük.
• Hatalmas adatok esetén egy lemezen való kereséshez a teljes lemez elolvasása szükséges; ez megnöveli az idő és a fő memóriafelhasználást a nagy lemezelérési gyakoriság és az adatméret miatt.
• Ennek kiküszöbölésére indextáblák jönnek létre, amelyek mentik a rekordok referencia-referenciáját a blokkok alapján, amelyekben tartózkodnak. Ez drasztikusan csökkenti az idő- és memóriafelhasználást.
• Mivel hatalmas adataink vannak, többszintű indextáblákat hozhatunk létre.
• A többszintű index a B Tree használatával megtervezhető az adatok önkiegyensúlyozott rendezésében.

Keresés művelet

A keresési művelet a B Tree legegyszerűbb művelete.

A következő algoritmust alkalmazzák:

• Hagyja, hogy a kulcsot (értéket) "k" -vel keresse meg.
• Kezdje el keresni a gyökérből, és rekurzívan haladjon lefelé.
• Ha k kisebb, mint a gyökérérték, akkor keresse meg a bal alfát, ha k nagyobb, mint a gyökérérték, akkor keresse meg a jobb alfát.
• Ha a csomópont megtalálta a k-t, egyszerűen adja vissza a csomópontot.
• Ha a k nem található a csomópontban, akkor egy nagyobb kulccsal haladjon lefelé a gyermekhez.
• Ha k nem található a fában, akkor NULL-t adunk vissza.

Helyezze be a műveletet

Mivel a B Tree egy önkiegyensúlyozó fa, nem kényszeríthet kulcsot egyetlen csomópontba sem.

A következő algoritmus érvényes:

• Futtassa a keresési műveletet, és keresse meg a beillesztés megfelelő helyét.
• Helyezze be az új kulcsot a megfelelő helyre, de ha a csomópont már rendelkezik a kulcsok maximális számával:
• A csomópont egy újonnan behelyezett kulccsal együtt elválik a középső elemtől.
• A középső elem lesz a szülő a másik két gyermekcsomópont számára.
• A csomópontoknak újból el kell rendezniük a kulcsokat növekvő sorrendben.

TIPP	A következő nem igaz a beszúrási algoritmusra: Mivel a csomópont megtelt, ezért fel fog hasadni, majd egy új érték kerül beillesztésre

A fenti példában:

• Keresse meg a kulcs megfelelő pozícióját a csomópontban
• Helyezze be a kulcsot a célcsomópontba, és ellenőrizze, hogy vannak-e szabályok
• Beillesztés után a csomópontnak több van-e, mint egy minimális kulcsszám, ami 1? Ebben az esetben igen. Ellenőrizze a következő szabályt.
• Beillesztés után a csomópontnak több van-e a maximális száma, mint 3? Ebben az esetben nem, nem. Ez azt jelenti, hogy a B fa nem sért semmilyen szabályt, és a beillesztés befejeződött.

A fenti példában:

• A csomópont elérte a kulcsok maximális számát
• A csomópont fel fog osztódni, és a középső kulcs lesz a többi két csomópont gyökércsomópontja.
• Páros számú kulcs esetén a középső csomópontot bal vagy jobb torzítással választjuk ki.

A fenti példában:

• A csomópont kevesebb, mint max
• Az 1 be van illesztve a 3 mellé, de a növekvő sorrend szabálya sérül
• Ennek kijavítása érdekében a kulcsok rendezve vannak

Hasonlóképpen, a 13 és a 2 könnyen beilleszthető a csomópontba, mivel azok teljesítik a csomópontok max.

A fenti példában:

• A csomópont kulcsai megegyeznek a max kulcsokkal.
• A kulcs beillesztésre kerül a cél csomópontba, de megsérti a max kulcsok szabályát.
• A célcsomópont fel van osztva, és a középső kulcs a bal elfogultság alapján most az új gyermekcsomópontok szülője.
• Az új csomópontok növekvő sorrendben vannak elrendezve.

Hasonlóképpen, a fenti szabályok és esetek alapján a többi érték könnyen beilleszthető a B fába.

Művelet törlése

A törlési műveletnek több szabálya van, mint a beszúrási és keresési műveleteknél.

A következő algoritmus érvényes:

• Futtassa a keresési műveletet, és keresse meg a célkulcsot a csomópontokban
• Három feltétel érvényesült a célkulcs helye alapján, amint azt a következő szakaszokban ismertetjük

Ha a célkulcs a levélcsomópontban van

• A cél a levélcsomópontban van, több mint min kulcs.
  • Ennek törlése nem sérti a B Tree tulajdonságait
• A cél levél csomópontban van, min kulcs csomópontokkal rendelkezik
  • Ennek törlése sérti a B Tree tulajdonságait
  • A cél csomópont kölcsönözhet kulcsot a közvetlen bal csomópontból vagy a közvetlen jobb csomópontból (testvér)
  • A testvér akkor fog igent mondani, ha a minimálisnál több kulccsal rendelkezik
  • A kulcsot kölcsönadják a szülőcsomóponttól, a maximális értéket egy szülőhöz, a szülőcsomópont maximális értékét a célcsomóponthoz, és eltávolítja a célértéket
• A cél a levélcsomópontban van, de egyetlen testvérnek sincs minél több kulcsa
  • Kulcs keresése
  • Egyesülés testvérekkel és a szülő csomópontok minimumával
  • Az összes kulcs több mint min
  • A célkulcs kicserélődik a szülőcsomópont minimumára

Ha a célkulcs egy belső csomópontban van

• Vagy válasszon, rendben lévő elődöt vagy rendes utódot
• Rendben lévő előd esetén a bal alfából a maximális kulcs kerül kiválasztásra
• Rendezett utód esetén a jobb oldali alfából a minimális kulcs kerül kiválasztásra
• Ha a célkulcs rendezett elődjénél több van, mint a min kulcs, csak akkor helyettesítheti a célkulcsot a rendben lévő előd maximalisával
• Ha a célkulcs rendezett elődjénél nincs több, mint min kulcs, keresse meg a rendben lévő utód minimális kulcsát.
• Ha a célkulcs rendezett elődjének és utódjának mindkettője kevesebb, mint min kulcs, akkor egyesítse az elődöt és az utódot.

Ha a célkulcs egy gyökércsomópontban van

• Cserélje ki a rendben lévő előd részfa maximális elemére
• Ha a törlés után a célnak kevesebb mint min kulcsa van, akkor a cél csomópont maximális értéket kölcsönöz testvérétől a testvér szülőjén keresztül.
• A szülő maximális értékét egy cél fogja venni, de a testvér max értékének csomópontjaival együtt.

Most értsük meg egy példával a törlési műveletet.

A fenti ábra a B-fa törlési műveleteinek különböző eseteit jeleníti meg. Ez a B-fa 5-ös rendű, ami azt jelenti, hogy bármelyik csomópontban a gyermekcsomópontok minimális száma 3, a csomópontok maximális száma pedig 5 lehet. 2, illetve 4 lehet.

A fenti példában:

• A célcsomópont rendelkezik a törlendő célkulccsal
• A célcsomópont kulcsainak meghaladja a minimális kulcsokat
• Egyszerűen törölje a kulcsot

A fenti példában:

• A megcélzott csomópont kulcsai megegyeznek a minimum kulcsokkal, ezért nem törölheti közvetlenül, mert ez sérti a feltételeket

Az alábbi ábra elmagyarázza a kulcs törlését:

• A célcsomópont kölcsönvesz egy kulcsot azonnali testvértől, ebben az esetben a rendes elődtől (bal testvér), mert nincs rendben lévő utódja (jobb testvér)
• Az inorder előd maximális értéke átkerül a szülőhöz, a szülő pedig a maximális értéket a célcsomópontba (lásd az alábbi ábrát)

Az alábbi példa bemutatja, hogy miként lehet törölni egy kulcsot, amelynek szüksége van egy értékre a rend szerinti utódjából.

• A célcsomópont kölcsönad egy kulcsot azonnali testvértől, ebben az esetben a rendes utódtól (jobb testvér), mert rendben lévő elődjének (bal testvér) kulcsai megegyeznek a minimum kulcsokkal.
• A rendben lévő utód minimális értéke átkerül a szülőhöz, a szülő pedig a maximális értéket a célcsomópontba.

Az alábbi példában a célcsomópontnak nincs olyan testvére, amely megadná kulcsát a célcsomópontnak. Ezért egyesítésre van szükség.

Lásd az ilyen kulcs törlésének eljárását:

• Egyesítse a célcsomópontot bármely közvetlen testvérével a szülőkulccsal együtt
  • A szülőcsomópontból kiválasztják azt a kulcsot, amelyet testvérek tesznek a két egyesülő csomópont közé
• Törölje a célkulcsot az egyesített csomópontból

Az Operációs álkód törlése

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Kimenet :

A legnagyobb elem törlődik a B-fáról.

Összegzés:

• A B Tree egy önkiegyensúlyozó adatstruktúra az adatok jobb kereséséhez, beillesztéséhez és törléséhez a lemezről.
• A B fát a megadott fokozat szabályozza
• B A fa gombok és csomópontok növekvő sorrendbe vannak rendezve.
• A B Tree keresési művelete a legegyszerűbb, amely mindig a gyökérből indul ki, és elkezdi ellenőrizni, hogy a célkulcs nagyobb vagy kisebb-e, mint a csomópont értéke.
• A B Tree beillesztési művelete meglehetősen részletes, amely először megtalálja a célkulcs megfelelő beillesztési helyzetét, beilleszti, a B Tree érvényességét különböző esetek alapján értékeli, majd ennek megfelelően átalakítja a B Tree csomópontokat.
• A B Tree törlési művelete először a törlendő célkulcsot keresi, törli, több eset alapján értékeli az érvényességet, például a cél csomópont, testvérek és szülő minimum és maximum kulcsai alapján.