AVL-träd: Rotationer, infogning, radering med C++ Exempelvis

By: Sarah Chen Sarah Chen
Hours Uppdaterad

⚡ Smart sammanfattning

AVL-träd är självbalanserande binära sökträd där höjdskillnaden mellan vänster och höger delträd för varje nod håller sig inom -1, 0 eller +1, vilket garanterar O(log n) sökprestanda.

  • 🌲 Definition: Ett binärt sökträd där balansfaktorn för varje nod ligger i {-1, 0, +1}, uppkallat efter uppfinnarna Adelson-Velsky och Landis.
  • ⚖️ Balansfaktor: Beräknas som height(left) − height(right); värden utanför {-1, 0, +1} utlöser en rotation för att återställa balansen.
  • 🔄 Rotationer: Fyra fall — LL, RR, LR och RL — justerar om noder efter obalanserade infogningar eller borttagningar för att hålla trädet logaritmiskt i höjd.
  • ➕ Införande: Standard BST-insättning följt av en uppåtgående gång som omberäknar balansfaktorer och utför högst en enkel- eller dubbelrotation.
  • ➖ Radering: Samma som BST-borttagning men kan kaskada flera rotationer uppåt i trädet eftersom underträdets höjd kan krympa vid varje förfader.
  • 🚀 Program: Databaser, minnesindex, filsystemsmetadata och AI-sökstrukturer använder AVL-träd för snabba ordnade sökningar.
Läs mer

AVL-träd

Vad är AVL-träd?

AVL-träd är binära sökträd där höjdskillnaden mellan vänster och höger delträd för varje nod är -1, 0 eller +1. De är självbalanserande BST:er som upprätthåller logaritmisk söktid, uppkallade efter uppfinnarna Adelson-Velsky och Landis (AVL).

Hur fungerar AVL Tree?

För att förstå varför AVL-träd finns, titta på vad som går fel med en slätt Binärt sökträdBetrakta dessa nycklar som infogade i den givna ordningen:

AVL Trädarbete

AVL-trädvisualisering

Trädet växer linjärt när nycklar anländer i ökande ordning, vilket degenererar sökningen till O(n). Det motverkar syftet med en BST – endast ett balanserat träd håller sökningen logaritmisk. Titta nu på samma nycklar som infogas i en annan ordning.

AVL Trädarbete

Samma nycklar, olika insättningsordning ger en grundare form, så varje sökning körs i O(log n). AVL-träd framtvingar den formen genom att observera höjden vid varje insättning och korrigera obalans utan att bryta BST-ordningen.

Balansfaktor i AVL-träd

Balansfaktorn (BF) tracks varje nods höjd så att trädet kan självbalansera under tiden.

Balansfaktorns egenskaper

Balansfaktor i AVL-träd

Balansfaktor AVL-träd

  • Balansfaktorn är skillnaden mellan höjden på det vänstra delträdet och höjden på det högra delträdet.
  • Balance factor(node) = height(node->left) − height(node->right)
  • De enda tillåtna värdena är −1, 0 och +1.
  • Ett värde på −1 betyder att det högra underträdet innehåller en extra nivå — noden är högertung.
  • Ett värde på +1 betyder att det vänstra underträdet innehåller en extra nivå — noden är vänstertung.
  • Värdet 0 betyder att båda sidorna har samma höjd – noden är perfekt balanserad.

AVL-rotationer

Rotationer körs närhelst en insättning eller borttagning bryter mot balansfaktorregeln. De fyra fallen är LL, RR, LR och RL.

Vänster – Vänsterrotation

Denna rotation utförs när en ny nod infogas vid det vänstra underordnade underträdet i det vänstra underträdet.

AVL-träd vänster – vänsterrotation

AVL-träd vänster – vänsterrotation

En enda högerrotation utförs. Detta fall utlöses när en nod har BF +2 och dess vänstra barn har BF +1.

Höger – Höger rotation

Denna rotation utförs när en ny nod infogas vid det högra underordnade underträdet i det högra underträdet.

AVL-träd höger – högerrotation

En enda vänsterrotation utförs. Detta fall utlöses när en nod har BF −2 och dess högra barn har BF −1.

Höger – Vänsterrotation

Denna rotation utförs när en ny nod infogas vid det vänstra barnet i det högra underträdet.

AVL-träd höger – vänsterrotation

Utlöses när BF(nod) = −2 och BF(höger-barn) = +1. Rotera det högra barnet åt höger och rotera sedan noden åt vänster.

Vänster – höger rotation

Denna rotation utförs när en ny nod infogas vid det högra underordnade underträdet i det vänstra underträdet.

AVL-träd vänster – högerrotation

Utlöses när BF(nod) = +2 och BF(vänster-barn) = −1. Rotera vänster-barnet och sedan noden till höger.

Insättning i AVL Trees

Insättningen är nästan identisk med en vanlig BST-insättning. Efter varje insättning går trädet upp och balanserar om. Insättningen körs i värsta tänkbara tid O(log n).

Insättning i AVL Trees

Implementering av AVL-trädinsättning

Steg 1: Infoga noden med hjälp av standard BST-algoritmen. I exemplet ovan, infoga 160.

Steg 2: Uppdatera balansfaktorn för varje förfader längs insättningsvägen.

Steg 3: Om någon förfader bryter mot balansfaktorintervallet, utför matchningsrotationen. I exemplet bryts nod 350:s balansfaktor, så en LL-rotation återställer balansen.

  1. If BF(node) = +2 och BF(left-child) = +1, utför LL-rotation.
  2. If BF(node) = −2 och BF(right-child) = −1, utför RR-rotation.
  3. If BF(node) = −2 och BF(right-child) = +1, utför RL-rotation.
  4. If BF(node) = +2 och BF(left-child) = −1, utför LR-rotation.

RELATERADE ARTIKLAR

Radering i AVL-träd

Radering följer samma logik som en vanlig BST och ombalanseras efteråt.

Steg 1: Hitta elementet i trädet.

Steg 2: Ta bort noden med standard BST-borttagning.

Steg 3: Två fall är möjliga.

Fallet 1: Tar bort från höger underträd.

  • 1A. If BF(node) = +2 och BF(left-child) = +1, utför LL-rotation.
  • 1B. If BF(node) = +2 och BF(left-child) = −1, utför LR-rotation.
  • 1C. If BF(node) = +2 och BF(left-child) = 0, utför LL-rotation.

Radering i AVL-träd

Fallet 2: Tar bort från det vänstra underträdet.

  • 2A. If BF(node) = −2 och BF(right-child) = −1, utför RR-rotation.
  • 2B. If BF(node) = −2 och BF(right-child) = +1, utför RL-rotation.
  • 2C. If BF(node) = −2 och BF(right-child) = 0, utför RR-rotation.

Radering i AVL-träd

C++ Exempel på AVL-träd

Nedan följer en C++ program som implementerar AVL-träd:

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

Körningsexempel på koden ovan:

  1. Kopiera koden ovan och spara den i en fil med namnet avl.cpp.
  2. Kompilera koden:
g++ avl.cpp -o run
  1. Kör koden.
./run

C++ Exempel på AVL-träd

Fördelar med AVL-träd

  • AVL-trädets höjd är alltid balanserad och växer aldrig över log N.
  • Sökning är snabbare än ett vanligt binärt sökträd eftersom trädet inte kan degenerera.
  • Självbalanseringen är automatisk – inget ombyggnadssteg krävs.
  • Deterministisk prestanda passar realtidssystem och index i minnet.

Vanliga frågor

Ett AVL-träd är ett självbalanserande binärt sökträd där balansfaktorn för varje nod stannar i {-1, 0, +1}. Rotationer återställer denna invariant vid varje infogning eller borttagning, hållping sök, infoga och ta bort vid O(log n).

Balansfaktorn för en nod är lika med höjd (vänster delträd) minus höjd (höger delträd). Värdena måste ligga inom {-1, 0, +1}. En balansfaktor på +2 eller -2 signalerar att en insättning eller borttagning har obalanserat noden och att en rotation krävs.

De fyra rotationerna är LL, RR, LR och RL. LL använder en enda högerrotation, RR använder en enda vänsterrotation och LR och RL är dubbla rotationer som kombinerar en rotation på barnet med en motsatt rotation på noden.

Insättning följer standard BST-regeln, sedan går trädet tillbaka uppåt och uppdaterar höjderna. Om någon förfader bryter mot balansregeln återställer en enkel eller dubbel rotation balansen. Högst en rotation per insättning behövs någonsin.

AVL-träd är strikt balanserade med en balansfaktor på högst ett, vilket ger snabbare sökningar. Röd-svarta träd tillåter lösare balans, vilket gör infogning och borttagning billigare men sökning något långsammare. Databaser föredrar röd-svart för skrivtunga belastningar.

AVL-träd driver databasindex i minnet, filsystemsmetadata, prioritetsköer, telefonbokssökningar, stavningskontroll och alla arbetsbelastningar som behöver deterministisk O(log n)-sökning plus ordningsföljd för intervallfrågor.

Ja. AI-system använder AVL-träd för symboltabeller, ordnade funktionslager, balansering av kd-träd och sökningar efter närmaste granne på strukturerad data. De ligger också till grund för rangordnade hämtningsindex i intelligenta sökpipelines.

Ja. GitHub Copilot och liknande AI-assistenter hanterar rutiner för infogning, borttagning och rotation i C++, Java, eller Python, och generera enhetstester som verifierar balansfaktorns invarianta funktion för varje operation.

Sammanfatta detta inlägg med: