AVL-bomen: rotaties, invoeging, verwijdering met C++ Voorbeeld

Wat zijn AVL-bomen?

AVL-bomen Binaire zoekbomen (BST's) zijn bomen waarin het hoogteverschil tussen de linker- en rechterdeelboom van elk knooppunt -1, 0 of +1 is. Het zijn zelfbalancerende BST's die een logaritmische zoektijd behouden, genoemd naar de uitvinders Adelson-Velsky en Landis (AVL).

Hoe werkt AVL Tree?

Om te begrijpen waarom AVL-bomen bestaan, moet je kijken naar wat er misgaat met een eenvoudige boomstructuur. Binaire zoekboomBeschouw de volgende sleutels in de gegeven volgorde:

AVL-boomvisualisatie

De boom groeit lineair wanneer sleutels in oplopende volgorde binnenkomen, waardoor de zoektijd reduceert tot O(n). Dat ondermijnt het doel van een binaire zoekboom (BST) — alleen een gebalanceerde boom houdt de zoektijd logaritmisch. Kijk nu naar dezelfde sleutels die in een andere volgorde worden ingevoegd.

Dezelfde sleutels, maar een andere invoegvolgorde resulteert in een minder diepe vorm, waardoor elke zoekopdracht in O(log n) tijd verloopt. AVL-bomen handhaven die vorm door de hoogte bij elke invoeging te controleren en onevenwichtigheden te corrigeren zonder de ordening van de binaire zoekboom te verstoren.

Balansfactor in AVL-bomen

De balansfactor (BF) tracks geeft de hoogte van elk knooppunt weer, zodat de boom zichzelf tijdens de uitvoering in evenwicht kan houden.

Eigenschappen van de balansfactor

Evenwichtsfactor AVL-boom

• De balansfactor is het verschil tussen de hoogte van de linker subboom en de hoogte van de rechter subboom.
• Balance factor(node) = height(node->left) − height(node->right)
• De enige toegestane waarden zijn -1, 0 en +1.
• Een waarde van -1 betekent dat de rechter subboom een ​​extra niveau bevat — het knooppunt is rechtszwaar.
• Een waarde van +1 betekent dat de linker subboom een ​​extra niveau bevat — het knooppunt is linkszwaar.
• Een waarde van 0 betekent dat beide zijden even hoog zijn — het knooppunt is perfect in balans.

AVL-rotaties

Rotaties vinden plaats wanneer een invoeging of verwijdering de balansregel verstoort. De vier gevallen zijn LL, RR, LR en RL.

Links – Links draaien

Deze rotatie wordt uitgevoerd wanneer een nieuw knooppunt wordt ingevoegd aan het linkerkind van de linker subboom.

AVL-boom links – linksom draaien

Er wordt een enkele rotatie naar rechts uitgevoerd. Dit geval treedt op wanneer een knooppunt een BF van +2 heeft en het linker kindknooppunt een BF van +1.

Rechts – Rechts draaien

Deze rotatie wordt uitgevoerd wanneer een nieuw knooppunt wordt ingevoegd bij het rechterkind van de rechter subboom.

Er wordt een enkele linkse rotatie uitgevoerd. Dit geval treedt op wanneer een knooppunt BF −2 heeft en het rechterkind BF −1.

Rechts-links rotatie

Deze rotatie wordt uitgevoerd wanneer een nieuw knooppunt wordt ingevoegd aan het linkerkind van de rechter subboom.

Wordt geactiveerd wanneer BF(node) = −2 en BF(right-child) = +1. Draai het rechter kind naar rechts en draai vervolgens de node naar links.

Links-rechts rotatie

Deze rotatie wordt uitgevoerd wanneer een nieuw knooppunt wordt ingevoegd aan het rechterkind van de linker subboom.

Wordt geactiveerd wanneer BF(knooppunt) = +2 en BF(linkerkind) = −1. Draai het linkerkind naar links en draai vervolgens het knooppunt naar rechts.

Invoeging in AVL-bomen

Het invoegen is vrijwel identiek aan het invoegen in een gewone binaire zoekboom. Na elke invoeging doorloopt de boom een ​​opwaartse beweging en wordt deze opnieuw gebalanceerd. Invoegen duurt in het slechtste geval O(log n) tijd.

Implementatie van AVL-boominvoeging

Stap 1: Voeg het knooppunt in met behulp van het standaard BST-algoritme. In het bovenstaande voorbeeld voeg je 160 in.

Stap 2: Werk de balansfactor van elke voorouder langs het invoegpad bij.

Stap 3: Als een voorouder de balansfactor overschrijdt, voer dan de bijbehorende rotatie uit. In het voorbeeld wordt de balansfactor van knooppunt 350 overschreden, dus een LL-rotatie herstelt de balans.

1. If BF(node) = +2 en BF(left-child) = +1Voer een LL-rotatie uit.
2. If BF(node) = −2 en BF(right-child) = −1Voer een RR-rotatie uit.
3. If BF(node) = −2 en BF(right-child) = +1Voer een RL-rotatie uit.
4. If BF(node) = +2 en BF(left-child) = −1Voer een LR-rotatie uit.

Verwijdering in AVL-bomen

Verwijdering volgt dezelfde logica als een gewone binaire zoekboom en zorgt daarna voor herbalancering.

Stap 1: Zoek het element in de boom.

Stap 2: Verwijder het knooppunt met behulp van de standaard BST-verwijderingsmethode.

Stap 3: Er zijn twee mogelijke scenario's.

Zaak 1: Verwijderen uit de rechter subboom.

• 1A. If BF(node) = +2 en BF(left-child) = +1Voer een LL-rotatie uit.
• 1B. If BF(node) = +2 en BF(left-child) = −1Voer een LR-rotatie uit.
• 1C. If BF(node) = +2 en BF(left-child) = 0Voer een LL-rotatie uit.

Zaak 2: Verwijderen uit de linker subboom.

• 2A. If BF(node) = −2 en BF(right-child) = −1Voer een RR-rotatie uit.
• 2B. If BF(node) = −2 en BF(right-child) = +1Voer een RL-rotatie uit.
• 2C. If BF(node) = −2 en BF(right-child) = 0Voer een RR-rotatie uit.

C++ Voorbeeld van AVL-bomen

Hieronder is een C++ programma dat AVL-bomen implementeert:

#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);
}

Een werkend voorbeeld van de bovenstaande code:

1. Kopieer de bovenstaande code en sla deze op in een bestand met de naam avl.cpp.
2. Compileer de code:

g++ avl.cpp -o run

3. Voer de code uit.

./run

Voordelen van AVL Bomen

• De hoogte van de AVL-boom is altijd in evenwicht en groeit nooit boven log N uit.
• Zoeken is sneller dan met een gewone binaire zoekboom, omdat de boom niet kan degenereren.
• Het systeem balanceert zichzelf automatisch — er is geen heropbouwstap nodig.
• Deterministische prestaties zijn geschikt voor realtime systemen en in-memory indexen.

Veelgestelde vragen