B fa az adatszerkezetben: Keresés, beszúrás, törlés

Mi az a B fa?

B Fa egy önkiegyensúlyozó adatstruktúra, amely egy meghatározott szabályokon alapul, amelyek lehetővé teszik az adatok gyorsabb és memóriahatékonyabb keresését, beszúrását és törlését. Ennek eléréséhez a következő szabályokat kell követni egy B fa létrehozásához.

A B-fa egy speciális fafajta az adatstruktúrákban. Ezt a módszert először McCreight és Bayer vezette be 1972-ben, akik magasságkiegyenlített m-utas keresőfának nevezték el. Segít az adatok rendezett állapotban tartásában, és lehetővé teszi a különféle műveletek, például a beszúrás, a keresés és a törlés rövidebb idő alatt történő elvégzését.

A B-Tree szabályai

Íme a B-fa létrehozásának fontos szabályai:

• Minden levél ugyanazon a szinten lesz létrehozva.
• Egy B-fát egy fokszámok száma határoz meg, amelyet „sorrendnek” is nevezünk (egy külső szereplő, például egy programozó határozza meg), amelyet a következőképpen emlegetnek: m tovább. Az értéke m a blokk méretétől függ azon a lemezen, amelyen elsősorban az adatok találhatók.
• A csomópont bal oldali részfájának értéke kisebb, mint a részfa jobb oldalának. Ez azt jelenti, hogy a csomópontok is növekvő sorrendben vannak rendezve balról jobbra.
• A gyökércsomópont, valamint a gyermekcsomópontok által tartalmazható kulcsok maximális számát a következő képlettel számítjuk ki: m − 1. Például:

  m = 4
  max keys: 4 − 1 = 3

• Minden csomópontnak, kivéve a gyökeret, legalább egy bizonyos számú kulcsot kell tartalmaznia: [m/2] − 1. Például:

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

• Egy csomópont gyermekcsomópontjainak maximális száma megegyezik a fokával, ami az m.
• Egy csomópont minimális gyermekei a sorrend fele, ami m/2 (a plafonértéket veszik).
• A csomópont összes kulcsa növekvő sorrendben van rendezve.

Miért használja a B-tree-t?

Íme néhány ok a B-fa használatára:

• Csökkenti a lemezen végzett olvasások számát.
• A B-fák könnyen optimalizálhatók úgy, hogy méretüket (azaz a gyermekcsomópontok számát) a lemez méretének megfelelően módosítsák.
• Ez egy speciálisan nagy mennyiségű adat kezelésére tervezett technika.
• Ez egy hasznos algoritmus adatbázisokhoz és fájlrendszerekhez.
• Jó választás nagy adatblokkok olvasása és írása esetén.

A B fa története

• Az adatokat a lemezen blokkokban tároljuk. Ezeket az adatokat, amikor a főmemóriába (vagy RAM-ba) bevitelre kerülnek, adatstruktúrának nevezzük.
• Hatalmas adatmennyiség esetén egyetlen rekord keresése a lemezen a teljes lemez beolvasását igényli; ez növeli az időt és a főmemória-fogyasztást a magas lemezhozzáférési gyakoriság és az adatméret miatt.
• Ennek kiküszöbölésére indextáblákat hoznak létre, amelyek a rekordok rekordhivatkozását a blokkok alapján mentik el, amelyekben találhatók. Ez drasztikusan csökkenti az idő- és memóriafogyasztást.
• Mivel hatalmas adatokkal rendelkezünk, többszintű indextáblákat is készíthetünk.
• Többszintű indexet egy B fa használatával lehet tervezni a kee számáraping az adatok önkiegyensúlyozó módon vannak rendezve.

Keresés OperaCIÓ

A keresési művelet a legegyszerűbb művelet egy B fán. A következő algoritmust alkalmazzuk:

• Legyen a keresendő kulcs (az érték) „k”.
• Kezdje el a keresést a gyökértől, és rekurzívan haladjon lefelé.
• Ha k kisebb, mint a gyökérérték, akkor a bal oldali részfában keresünk; ha k nagyobb, mint a gyökérérték, akkor a jobb oldali részfában.
• Ha a csomópont rendelkezik a talált k értékkel, egyszerűen adja vissza a csomópontot.
• Ha a k nem található a csomópontban, lépjen le a gyermekhez egy nagyobb kulccsal.
• Ha k nem található a fában, akkor NULL-t adunk vissza.

betétlap OperaCIÓ

Mivel egy B fa egy önkiegyensúlyozó fa, nem lehet egy kulcsot csak úgy beilleszteni egy tetszőleges csomópontba. A következő algoritmus érvényesül:

• Futtassa a keresési műveletet, és keresse meg a megfelelő beszúrási helyet.
• Illessze be az új kulcsot a megfelelő helyre, de ha a csomópontnak már van maximális számú kulcsa:
• A csomópont az újonnan beillesztett kulccsal együtt kiválik a középső elemből.
• A középső elem lesz a másik két gyermek csomópont szülője.
• A csomópontoknak újra kell rendezniük a kulcsokat növekvő sorrendben.

A fenti példában:

• Keresd meg a kulcsot a csomópont megfelelő pozíciójában.
• Helyezze be a kulcsot a célcsomópontba, és ellenőrizze a szabályokat.
• Beszúrás után a csomópontnak több vagy egyenlő a minimális kulcsszámmal, ami 1? Ebben az esetben igen, van. Ellenőrizd a következő szabályt.
• Beszúrás után a csomópontnak több kulcsa van-e, mint a maximális 3? Ebben az esetben nem, nincs. Ez azt jelenti, hogy a B fa nem sért semmilyen szabályt, és a beszúrás befejeződött.

A fenti példában:

• A csomópont elérte a kulcsok maximális számát.
• A csomópont kettéválik, é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 balra vagy jobbra eltolás választja ki.

A fenti példában:

• A csomópontnak kevesebb mint a maximális kulcsa van.
• Az 1-es szám a 3-as mellé kerül, de a növekvő sorrend szabálya megsérül.
• Ennek kijavítása érdekében a kulcsokat rendezik.

Hasonlóképpen, a 13 és a 2 könnyen beilleszthető a csomópontba, mivel teljesítik a csomópontokra vonatkozó „kevesebb, mint a max kulcs” szabályt.

A fenti példában:

• A csomópont kulcsai megegyeznek a maximális kulcsokkal.
• A kulcs bekerül a célcsomópontba, de megsérti a kulcsok maximális számának szabályát.
• A célcsomópont fel van osztva, és a bal oldali torzítású középső kulcs mostantól az új gyermek csomó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.

Törölni OperaCIÓ

A törlés műveletnek több szabálya van, mint a beszúrás és keresés műveleteknek. A következő algoritmus érvényesül:

• Futtassa a keresési műveletet, és keresse meg a célkulcsot a csomópontokban.
• A célkulcs helye alapján három feltétel érvényesül, a következő szakaszokban ismertetettek szerint.

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

• Target a levélcsomópontban van, több mint minimális kulcs. Ennek törlése nem sérti a B fa tulajdonságát.
• Target a levélcsomópontban található, és minimális kulcscsomópontjai vannak. Ennek törlése sérti a B fa tulajdonságát.
• A célcsomópont kölcsönkérhet egy kulcsot a közvetlenül balra vagy a közvetlenül jobbra lévő csomóponttól (testvércsomópont).
• A testvér azt fogja mondani Igen ha a minimálisnál több kulcsa van.
• A kulcsot a szülőcsomóponttól kölcsönzik, a maximális érték átkerül a szülőcsomópontra, a szülőcsomópont maximális értéke átkerül a célcsomópontra, majd a célérték eltávolításra kerül.
• Target a levélcsomópontban van, de egyetlen testvércsomópontnak sincs több kulcsa a minimális értéknél: keresse meg a kulcsot, egyesítse a testvércsomópontokkal és a minimális számú szülőcsomóponttal, a teljes kulcsszám mostantól meghaladja a minimális értéket, és a célkulcs a szülőcsomópont minimális kulcsára lesz cserélve.

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

• Vagy egy sorrendben elődöt, vagy egy sorrendben utódot válassz.
• Egy sorrendben lévő előd esetében a bal oldali részfájából a maximális kulcs lesz kiválasztva.
• Egy sorrendben következő utód esetén a jobb oldali részfájából a minimális kulcs lesz kiválasztva.
• Ha a célkulcs sorrendbeli elődjének több kulcsa van, mint a minimális kulcs, akkor csak akkor cserélheti le a célkulcsot a sorrendbeli előd maximális kulcsára.
• Ha a célkulcs sorrendbeli elődjének nincs több mint minimális kulcsa, akkor keresse meg a sorrendbeli utód minimális kulcsát.
• Ha a célkulcs sorrendi elődjének és utódjának egyaránt kevesebb, mint min kulcsa van, akkor egyesítse az elődöt és az utódot.

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

• Cserélje le az előző részfa sorrendben lévő maximális elemére.
• Ha a törlés után a célcsomópontnak kevesebb, mint a minimális kulcs száma van, akkor a célcsomópont a maximális értéket kölcsönzi a testvérétől a szülőjén keresztül.
• A szülő maximális értékét a cél veszi át, de a testvér maximális értékének csomópontjaival.

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

A fenti ábra a B-fában végrehajtott törlési művelet különböző eseteit mutatja be. Ez a B-fa 5. rendű, ami azt jelenti, hogy egy csomópontban legalább 3, legfeljebb 5 gyermekcsomópont lehet. Ezzel szemben egy csomópont minimális kulcsszáma 2, maximális kulcsszáma 4.

A fenti példában:

• A célcsomópont rendelkezik a törlendő célkulccsal.
• A célcsomópontnak több kulcsa van, mint a minimális kulcsszám.
• Egyszerűen töröld a kulcsot.

A fenti példában:

• A célcsomópont kulcsai megegyeznek a minimális kulcsszámmal, így nem törölhetjük közvetlenül, mert az megsértené a feltételeket.

Most a következő diagram leírja, hogyan törölheti ezt a kulcsot:

• A célcsomópont egy kulcsot fog kölcsönkérni egy közvetlen testvérétől, ebben az esetben a sorrendben lévő elődjétől (bal testvér), mivel annak nincs sorrendben lévő utódja (jobb testvér).
• A sorrendben lévő előd maximális értéke átkerül a szülőcsomópontra, a szülő pedig a maximális értéket viszi át a célcsomópontra (lásd az alábbi ábrát).

A következő példa bemutatja, hogyan lehet törölni egy kulcsot, amelynek értékre van szüksége a sorrendi utódából.

• A célcsomópont egy kulcsot fog kölcsönkérni egy közvetlen testvérétől, ebben az esetben a sorrendben következő utódtól (jobb testvér), mivel a sorrendben következő elődjének (bal testvér) kulcsai megegyeznek a minimális kulcsszámmal.
• A sorban álló utód minimális értéke átkerül a szülőre, a szülő pedig a maximális értéket a célcsomópontra.

Az alábbi példában a célcsomópontnak nincs olyan testvércsomópontja, amely átadhatná a kulcsát a célcsomópontnak. Ezért összevonásra van szükség. Lásd az ilyen kulcs törlésének eljárását:

• Egyesítse a célcsomópontot bármelyik közvetlen testvérével a szülőkulccsal együtt.
• A szülőcsomópont kulcsa kerül kiválasztásra, amely a két egyesülő csomópont között található.
• Töröld a célkulcsot az egyesített csomópontból.

Törölni Operació álnév Code

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

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

GYIK