AVL fák: elforgatások, beszúrás, törlés C++ Példa

By: Sarah Chen Sarah Chen
Hours korszerűsített

⚡ Okos összefoglaló

Az AVL fák önkiegyensúlyozó bináris keresőfák, ahol az egyes csomópontok bal és jobb oldali részfái közötti magasságkülönbség -1, 0 vagy +1 értéken belül marad, garantálva az O(log n) keresési teljesítményt.

  • ???? Meghatározás: Egy bináris keresőfa, amelyben minden csomópont egyensúlyi tényezője {-1, 0, +1} tartományban van, Adelson-Velsky és Landis feltalálókról elnevezve.
  • 🇧🇷 Egyensúlyi tényező: A következőképpen számítható ki: height(left) − height(right); a {-1, 0, +1}-en kívüli értékek egy forgatást indítanak el az egyensúly helyreállítása érdekében.
  • 🔄 Forgatások: Négy eset – LL, RR, LR és RL – a csomópontokat kiegyensúlyozatlan beszúrások vagy törlések után újra igazítja, hogy a fa magassága logaritmikus maradjon.
  • ➕ Beillesztés: Standard BST lapka, majd egy felfelé tartó séta, amely újraszámítja az egyensúlyi tényezőket, és legfeljebb egy egyszeres vagy kétszeres forgást hajt végre.
  • ➖ Törlés: Ugyanaz, mint a BST deléció, de több rotációt is kaszkádszerűen követhet a fában felfelé, mivel az alfa magassága minden ősnél csökkenhet.
  • 🚀 Alkalmazások: Az adatbázisok, a memórián belüli indexek, a fájlrendszer metaadatai és a mesterséges intelligencia által létrehozott keresési struktúrák AVL fákat használnak a gyors, rendezett keresésekhez.
További információk

AVL fák

Mik azok az AVL fák?

AVL fák olyan bináris keresőfák, amelyekben minden csomópont bal és jobb részfája közötti magasságkülönbség -1, 0 vagy +1. Ezek önkiegyensúlyozó BST-k, amelyek logaritmikus keresési időt tartanak fenn, és Adelson-Velsky és Landis (AVL) feltalálókról kapták a nevüket.

Hogyan működik az AVL Tree?

Az AVL fák létezésének okának megértéséhez nézzük meg, mi a baj egy sima fával. Bináris keresési faTekintsük ezeket a kulcsokat a megadott sorrendben beillesztve:

AVL Fa munka

AVL fa vizualizáció

A fa lineárisan növekszik, amikor a kulcsok növekvő sorrendben érkeznek, O(n)-re degenerálva a keresést. Ez ellentétes a BST céljával – csak egy kiegyensúlyozott fa tartja fenn a keresés logaritmikus jellegét. Most vizsgáljuk meg ugyanazokat a kulcsokat más sorrendben beillesztve.

AVL Fa munka

Ugyanazok a kulcsok, eltérő beszúrási sorrend sekélyebb alakzatot eredményez, így minden keresés O(log n)-ben fut. Az AVL fák ezt az alakzatot úgy érvényesítik, hogy minden beszúráskor figyelik a magasságot, és korrigálják az egyensúlyhiányt a BST sorrend megsértése nélkül.

Balance Factor az AVL fákban

Az egyensúlyi tényező (BF) tracks minden csomópont magasságát, hogy a fa menet közben önmagát egyensúlyba hozhassa.

Az egyensúlytényező tulajdonságai

Balance Factor az AVL fákban

Egyensúlytényező AVL fa

  • Az egyensúlyi tényező a bal oldali és a jobb oldali részfa magassága közötti különbség.
  • Balance factor(node) = height(node->left) − height(node->right)
  • Az egyetlen megengedett érték a −1, a 0 és a +1.
  • Az −1 érték azt jelenti, hogy a jobb oldali részfa egy plusz szintet tartalmaz – a csomópont jobboldali nehézkességű.
  • A +1 érték azt jelenti, hogy a bal oldali részfa egy extra szintet tartalmaz – a csomópont baloldali-nehézkességű.
  • A 0 érték azt jelenti, hogy mindkét oldal azonos magasságú – a csomópont tökéletesen kiegyensúlyozott.

AVL forgások

A forgatások akkor futnak le, amikor egy beszúrás vagy törlés megsérti az egyensúlyi tényező szabályát. A négy eset a következő: LL, RR, LR és RL.

Balra – Balra forgatás

Ez a forgatás akkor történik meg, amikor egy új csomópontot szúrnak be a bal oldali részfa bal oldali gyermekéhez.

AVL fa balra – balra forgatás

AVL fa balra – balra forgatás

Egyetlen jobbra forgatás történik. Ez az eset akkor aktiválódik, amikor egy csomópont BF +2-vel, a bal oldali gyermekének pedig BF +1-gyel rendelkezik.

Jobbra – Jobbra forgás

Ezt a forgatást akkor hajtják végre, ha egy új csomópontot szúrnak be a jobb oldali részfa jobb gyermekéhez.

AVL fa jobbra – jobbra forgás

Egyetlen balra forgatás történik. Ez az eset akkor aktiválódik, ha egy csomópont BF −2 értékkel, jobb oldali gyermekének pedig BF −1 értékkel rendelkezik.

Jobbra – Balra forgatás

Ezt a forgatást akkor hajtják végre, amikor egy új csomópontot szúrnak be a jobb oldali részfa bal oldali gyermekéhez.

AVL fa jobbra – balra forgatás

Akkor aktiválódik, ha BF(csomópont) = −2 és BF(jobboldali gyermek) = +1. Jobbra forgatja a jobb oldali gyermeket, majd balra forgatja a csomópontot.

Balra – Jobbra Forgatás

Ez a forgatás akkor történik meg, amikor egy új csomópontot szúrnak be a bal oldali részfa jobb oldali gyermekéhez.

AVL fa balra – jobbra forgatás

Akkor aktiválódik, ha BF(csomópont) = +2 és BF(bal oldali gyermek) = −1. Balra forgatja a bal gyermeket, majd jobbra forgatja a csomópontot.

Beillesztés az AVL fákba

A beszúrás majdnem megegyezik egy sima BST beszúrással. Minden beszúrás után a fa újra egyensúlyoz. A beszúrás a legrosszabb esetre vetítve O(log n) idő alatt fut le.

Beillesztés az AVL fákba

AVL fa beillesztési megvalósítás

Lépés 1: Szúrja be a csomópontot a standard BST algoritmussal. A fenti példában illessze be a 160-at.

Lépés 2: Frissítse az összes ős egyensúlyi tényezőjét a beszúrási útvonal mentén.

Lépés 3: Ha bármelyik ős megsérti az egyensúlyi tényező tartományát, akkor végezze el az egyeztető forgatást. A példában a 350-es csomópont egyensúlyi tényezője sérül, így az LL forgatás visszaállítja az egyensúlyt.

  1. If BF(node) = +2 és a BF(left-child) = +1, hajtson végre LL forgatást.
  2. If BF(node) = −2 és a BF(right-child) = −1, végezzen RR forgatást.
  3. If BF(node) = −2 és a BF(right-child) = +1, hajtsa végre az RL forgatást.
  4. If BF(node) = +2 és a BF(left-child) = −1, hajtson végre LR forgatást.

KAPCSOLÓDÓ CIKKEK

Törlés az AVL-fákban

A törlés ugyanazt a logikát követi, mint egy sima BST, és utána újra kiegyensúlyozódik.

Lépés 1: Keresse meg az elemet a fában.

Lépés 2: Törölje a csomópontot a szabványos BST törléssel.

Lépés 3: Két eset lehetséges.

Case 1: Törlés a jobb oldali részfáról.

  • 1A. If BF(node) = +2 és a BF(left-child) = +1, hajtson végre LL forgatást.
  • 1B. If BF(node) = +2 és a BF(left-child) = −1, hajtson végre LR forgatást.
  • 1C. If BF(node) = +2 és a BF(left-child) = 0, hajtson végre LL forgatást.

Törlés az AVL-fákban

Case 2: Törlés a bal oldali részfából.

  • 2A. If BF(node) = −2 és a BF(right-child) = −1, végezzen RR forgatást.
  • 2B. If BF(node) = −2 és a BF(right-child) = +1, hajtsa végre az RL forgatást.
  • 2C. If BF(node) = −2 és a BF(right-child) = 0, végezzen RR forgatást.

Törlés az AVL-fákban

C++ Példa az AVL fákra

Az alábbiakban a C++ AVL fákat megvalósító program:

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct node {
    struct node *left;
    int data;
    int height;
    struct node *right;
};

class AVL {
public:
    struct node *root;

    AVL() {
        this->root = NULL;
    }

    int calheight(struct node *p) {
        if (p->left && p->right) {
            if (p->left->height < p->right->height)
                return p->right->height + 1;
            else
                return p->left->height + 1;
        }
        else if (p->left && p->right == NULL) {
            return p->left->height + 1;
        }
        else if (p->left == NULL && p->right) {
            return p->right->height + 1;
        }
        return 0;
    }

    int bf(struct node *n) {
        if (n->left && n->right)
            return n->left->height - n->right->height;
        else if (n->left && n->right == NULL)
            return n->left->height;
        else if (n->left == NULL && n->right)
            return -n->right->height;
        return 0;
    }

    struct node *llrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        p->left = tp->right;
        tp->right = p;
        return tp;
    }

    struct node *rrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        p->right = tp->left;
        tp->left = p;
        return tp;
    }

    struct node *rlrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        struct node *tp2 = p->right->left;
        p->right = tp2->left;
        tp->left = tp2->right;
        tp2->left = p;
        tp2->right = tp;
        return tp2;
    }

    struct node *lrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        struct node *tp2 = p->left->right;
        p->left = tp2->right;
        tp->right = tp2->left;
        tp2->right = p;
        tp2->left = tp;
        return tp2;
    }

    struct node *insert(struct node *r, int data) {
        if (r == NULL) {
            r = new struct node;
            r->data = data;
            r->left = r->right = NULL;
            r->height = 1;
            return r;
        }
        if (data < r->data)
            r->left = insert(r->left, data);
        else
            r->right = insert(r->right, data);

        r->height = calheight(r);

        if (bf(r) == 2 && bf(r->left) == 1)       r = llrotation(r);
        else if (bf(r) == -2 && bf(r->right) == -1) r = rrrotation(r);
        else if (bf(r) == -2 && bf(r->right) == 1)  r = rlrotation(r);
        else if (bf(r) == 2 && bf(r->left) == -1)   r = lrrotation(r);

        return r;
    }

    void levelorder_newline() {
        if (this->root == NULL) {
            cout << "\nEmpty tree\n";
            return;
        }
        levelorder_newline(this->root);
    }

    void levelorder_newline(struct node *v) {
        queue<struct node *> q;
        struct node *cur;
        q.push(v);
        q.push(NULL);
        while (!q.empty()) {
            cur = q.front();
            q.pop();
            if (cur == NULL && q.size() != 0) {
                cout << "\n";
                q.push(NULL);
                continue;
            }
            if (cur != NULL) {
                cout << " " << cur->data;
                if (cur->left != NULL)  q.push(cur->left);
                if (cur->right != NULL) q.push(cur->right);
            }
        }
    }

    struct node *deleteNode(struct node *p, int data) {
        if (p->left == NULL && p->right == NULL) {
            if (p == this->root) this->root = NULL;
            delete p;
            return NULL;
        }
        struct node *q;
        if (p->data < data)      p->right = deleteNode(p->right, data);
        else if (p->data > data) p->left  = deleteNode(p->left, data);
        else {
            if (p->left != NULL) {
                q = inpre(p->left);
                p->data = q->data;
                p->left = deleteNode(p->left, q->data);
            } else {
                q = insuc(p->right);
                p->data = q->data;
                p->right = deleteNode(p->right, q->data);
            }
        }

        if (bf(p) == 2 && bf(p->left) == 1)         p = llrotation(p);
        else if (bf(p) == 2 && bf(p->left) == -1)    p = lrrotation(p);
        else if (bf(p) == 2 && bf(p->left) == 0)     p = llrotation(p);
        else if (bf(p) == -2 && bf(p->right) == -1)  p = rrrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 1)   p = rlrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 0)   p = rrrotation(p);

        return p;
    }

    struct node *inpre(struct node *p) {
        while (p->right != NULL) p = p->right;
        return p;
    }

    struct node *insuc(struct node *p) {
        while (p->left != NULL) p = p->left;
        return p;
    }

    ~AVL() {}
};

int main() {
    AVL b;
    int c, x;
    do {
        cout << "\n1.Display levelorder on newline";
        cout << "\n2.Insert";
        cout << "\n3.Delete\n";
        cout << "\n0.Exit\n";
        cout << "\nChoice: ";
        cin >> c;
        switch (c) {
        case 1: b.levelorder_newline(); break;
        case 2:
            cout << "\nEnter no. "; cin >> x;
            b.root = b.insert(b.root, x);
            break;
        case 3:
            cout << "\nWhat to delete? "; cin >> x;
            b.root = b.deleteNode(b.root, x);
            break;
        case 0: break;
        }
    } while (c != 0);
}

A fenti kód futtatásának példája:

  1. Másold ki a fenti kódot, és mentsd el egy fájlba, melynek neve: avl.cpp.
  2. Állítsd össze a kódot:
g++ avl.cpp -o run
  1. Futtassa a kódot.
./run

C++ Példa az AVL fákra

Az AVL fák előnyei

  • Az AVL fa magassága mindig kiegyensúlyozott, és soha nem nő a log N fölé.
  • A keresés gyorsabb, mint egy sima bináris keresőfa, mivel a fa nem degenerálódik.
  • Az önkiegyensúlyozás automatikus – nincs szükség újjáépítésre.
  • A determinisztikus teljesítmény valós idejű rendszerekhez és memórián belüli indexekhez illik.

GYIK

Az AVL fa egy önkiegyensúlyozó bináris keresőfa, ahol minden csomópont egyensúlyi tényezője {-1, 0, +1} között marad. A forgatások minden beszúrásnál vagy törlésnél visszaállítják ezt az invariánst, azazping keresés, beszúrás és törlés O(log n) helyén.

Egy csomópont kiegyensúlyozási tényezője egyenlő a magasság(bal részfa) mínusz a magasság(jobb részfa) értékével. Az értékeknek {-1, 0, +1} tartományban kell lenniük. A +2 vagy -2 kiegyensúlyozási tényező azt jelzi, hogy egy beszúrás vagy törlés kiegyensúlyozatlanná tette a csomópontot, és forgatásra van szükség.

A négy forgatás az LL, RR, LR és RL. Az LL egyetlen jobbra forgatást, az RR egyetlen balra forgatást használ, az LR és RL pedig kettős forgatások, amelyek egy forgatást a gyermeken egy ellentétes forgatással kombinálnak a csomóponton.

A beszúrás a standard BST szabályt követi, majd a fa visszasétál felfelé a magasságok frissítésével. Ha bármelyik ős megszegi az egyensúly szabályát, egyetlen vagy kétszeri forgatás helyreállítja az egyensúlyt. Beszúrásonként legfeljebb egy forgatásra van szükség.

Az AVL fák szigorúan kiegyensúlyozottak, legfeljebb egy kiegyensúlyozási tényezővel, ami gyorsabb keresést tesz lehetővé. A vörös-fekete fák lazább kiegyensúlyozást tesznek lehetővé, ami olcsóbbá teszi a beszúrást és a törlést, de valamivel lassabbá teszi a keresést. Az adatbázisok a vörös-fekete elrendezést részesítik előnyben az írási igényes terhelések esetén.

Az AVL fák memórián belüli adatbázis-indexeket, fájlrendszer-metaadatokat, prioritási sorokat, telefonkönyv-kereséseket, helyesírás-ellenőrzőket és minden olyan munkaterhelést kezelnek, amely determinisztikus O(log n) keresést, valamint sorrenden belüli bejárást igényel a tartománylekérdezésekhez.

Igen. A mesterséges intelligencia rendszerek AVL-fákat használnak szimbólumtáblákhoz, rendezett jellemzőtároláshoz, kd-fa kiegyensúlyozáshoz és strukturált adatok legközelebbi szomszédjának kereséséhez. Ezek az intelligens keresési folyamatok rangsorolt ​​visszakeresési indexeinek alapját is képezik.

Igen. A GitHub Copilot és hasonló mesterséges intelligencia asszisztensek beszúrási, törlési és forgatási rutinokat dolgoznak ki. C++, Javavagy Python, és egységteszteket generál, amelyek minden műveletnél ellenőrzik az egyensúlyi tényező invarianciáját.

Foglald össze ezt a bejegyzést a következőképpen: