AVL Træer: Rotationer, Indsættelse, Sletning med C++ Eksempel

⚡ Smart opsummering

AVL-træer er selvbalancerende binære søgetræer, hvor højdeforskellen mellem venstre og højre undertræ for hver node forbliver inden for -1, 0 eller +1, hvilket garanterer O(log n) søgeydelse.

🌲 Definition: Et binært søgetræ, hvor balancefaktoren for hver node ligger i {-1, 0, +1}, opkaldt efter opfinderne Adelson-Velsky og Landis.
⚖️ Balancefaktor: Beregnet som height(venstre) − height(højre); værdier uden for {-1, 0, +1} udløser en rotation for at genoprette balancen.
🔄 Rotationer: Fire tilfælde — LL, RR, LR og RL — justerer noder efter ubalancerede indsættelser eller sletninger for at holde træet logaritmisk i højden.
➕ Indskud: Standard BST-indsats efterfulgt af en opadgående bevægelse, der genberegner balancefaktorer og udfører højst én enkelt eller dobbelt rotation.
➖ Sletning: Samme som BST-sletning, men kan kaskadere flere rotationer op i træet, fordi undertræets højde kan krympe ved hver forfader.
🚀 Applikationer: Databaser, in-memory-indekser, filsystemmetadata og AI-søgestrukturer bruger AVL-træer til hurtige, ordnede opslag.

Læs mere

Hvad er AVL-træer?

AVL træer er binære søgetræer, hvor højdeforskellen mellem venstre og højre undertræ for hver node er -1, 0 eller +1. De er selvbalancerende BST'er, der opretholder logaritmisk søgetid, opkaldt efter opfinderne Adelson-Velsky og Landis (AVL).

Hvordan virker AVL Tree?

For at forstå hvorfor AVL-træer findes, se på hvad der går galt med en slette Binært søgetræOvervej disse nøgler indsat i den givne rækkefølge:

AVL træ visualisering

Træet vokser lineært, når nøgler ankommer i stigende rækkefølge, hvilket degenererer søgning til O(n). Det modbeviser formålet med en BST - kun et balanceret træ holder søgningen logaritmisk. Se nu på de samme nøgler, der er indsat i en anden rækkefølge.

Samme nøgler, forskellig indsættelsesrækkefølge giver en lavere form, så hver søgning kører i O(log n). AVL-træer håndhæver denne form ved at overvåge højden ved hver indsættelse og korrigere ubalance uden at bryde BST-rækkefølgen.

Balancefaktor i AVL-træer

Balancefaktoren (BF) tracbestemmer hver nodes højde, så træet kan selvbalancere undervejs.

Balancefaktorens egenskaber

Balancefaktor AVL træ

Balancefaktoren er forskellen mellem højden af det venstre undertræ og højden af det højre undertræ.
Balance factor(node) = height(node->left) − height(node->right)
De eneste tilladte værdier er −1, 0 og +1.
En værdi på -1 betyder, at det højre undertræ indeholder ét ekstra niveau — noden er højretung.
En værdi på +1 betyder, at det venstre undertræ indeholder ét ekstra niveau — noden er venstretung.
En værdi på 0 betyder, at begge sider har samme højde — noden er perfekt afbalanceret.

AVL rotationer

Rotationer kører, når en indsættelse eller sletning bryder balancefaktorreglen. De fire tilfælde er LL, RR, LR og RL.

Venstre – Venstre rotation

Denne rotation udføres, når en ny node indsættes i venstre underordnede undertræ.

AVL træ til venstre – venstre rotation

En enkelt højrerotation udføres. Dette tilfælde udløses, når en node har BF +2, og dens venstre barn har BF +1.

Højre – Højre rotation

Denne rotation udføres, når en ny node indsættes ved det højre underordnede af det højre undertræ.

En enkelt venstrerotation udføres. Dette tilfælde aktiveres, når en node har BF −2, og dens højre barn har BF −1.

Højre – Venstre rotation

Denne rotation udføres, når en ny node indsættes ved det venstre underordnede underordnede undertræ.

Udløses når BF(node) = −2 og BF(højre-barn) = +1. Højreroter det højre barn, og derefter venstreroter noden.

Venstre – Højre rotation

Denne rotation udføres, når en ny node indsættes ved højre underordnede af det venstre undertræ.

Udløses når BF(node) = +2 og BF(venstre-barn) = −1. Roter det venstre barn mod venstre, og roter derefter noden mod højre.

Indsættelse i AVL Træer

Indsættelsen er næsten identisk med en almindelig BST-indsættelse. Efter hver indsættelse går træet op og balancerer igen. Indsættelsen kører i O(log n) worst-case tid.

Implementering af AVL træindsættelse

Trin 1: Indsæt noden ved hjælp af standard BST-algoritmen. I eksemplet ovenfor indsættes 160.

Trin 2: Opdater balancefaktoren for hver forfader langs indsættelsesstien.

Trin 3: Hvis en af forfædrene overskrider balancefaktorområdet, skal den matchende rotation udføres. I eksemplet er node 350's balancefaktor overtrådt, så en LL-rotation genopretter balancen.

If BF(node) = +2 og BF(left-child) = +1, udfør LL-rotation.
If BF(node) = −2 og BF(right-child) = −1, udfør RR-rotation.
If BF(node) = −2 og BF(right-child) = +1, udfør RL-rotation.
If BF(node) = +2 og BF(left-child) = −1, udfør LR-rotation.

Sletning i AVL-træer

Sletning følger samme logik som en almindelig BST og genbalanceres bagefter.

Trin 1: Find elementet i træet.

Trin 2: Slet noden ved hjælp af standard BST-sletning.

Trin 3: To tilfælde er mulige.

Sag 1: Sletter fra højre undertræ.

1A. If BF(node) = +2 og BF(left-child) = +1, udfør LL-rotation.
1B. If BF(node) = +2 og BF(left-child) = −1, udfør LR-rotation.
1C. If BF(node) = +2 og BF(left-child) = 0, udfør LL-rotation.

Sag 2: Sletter fra venstre undertræ.

2A. If BF(node) = −2 og BF(right-child) = −1, udfør RR-rotation.
2B. If BF(node) = −2 og BF(right-child) = +1, udfør RL-rotation.
2C. If BF(node) = −2 og BF(right-child) = 0, udfør RR-rotation.

C++ Eksempel på AVL-træer

Nedenfor er en C++ program der implementerer AVL-træer:

#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ørselseksempel på ovenstående kode:

Kopier koden ovenfor og gem den i en fil med navnet avl.cpp.
Kompiler koden:

g++ avl.cpp -o run

Kør koden.

./run

Fordele ved AVL Træer

AVL-træets højde er altid afbalanceret og vokser aldrig ud over log N.
Søgning er hurtigere end et almindeligt binært søgetræ, fordi træet ikke kan degenerere.
Selvbalanceringen er automatisk – der kræves ingen genopbygning.
Deterministisk ydeevne passer til realtidssystemer og in-memory-indekser.

Ofte Stillede Spørgsmål

Et AVL-træ er et selvbalancerende binært søgetræ, hvor balancefaktoren for hver node forbliver i {-1, 0, +1}. Rotationer gendanner denne invariant ved hver indsættelse eller sletning.ping søg, indsæt og slet ved O(log n).

Balancefaktoren for en node er lig med højde (venstre undertræ) minus højde (højre undertræ). Værdierne skal ligge i {-1, 0, +1}. En balancefaktor på +2 eller -2 signalerer, at en indsættelse eller sletning har bragt noden ud af balance, og at en rotation er påkrævet.

De fire rotationer er LL, RR, LR og RL. LL bruger en enkelt højrerotation, RR bruger en enkelt venstrerotation, og LR og RL er dobbeltrotationer, der kombinerer én rotation på barnet med en modsat rotation på noden.

Indsættelse følger standard BST-reglen, hvorefter træet går tilbage opad og opdaterer højderne. Hvis en forfader bryder balancereglen, genopretter én enkelt eller dobbelt rotation balancen. Der er højst behov for én rotation pr. indsættelse.

AVL-træer er strengt afbalancerede med en balancefaktor på højst én, hvilket giver hurtigere opslag. Rød-sorte træer tillader løsere balance, hvilket gør indsættelse og sletning billigere, men søgning lidt langsommere. Databaser foretrækker rød-sort til skrivetunge belastninger.

AVL-træer driver databaseindekser i hukommelsen, filsystemmetadata, prioritetskøer, opslag i telefonbøger, stavekontrol og enhver arbejdsbelastning, der kræver deterministisk O(log n)-søgning plus gennemgang i rækkefølge for områdeforespørgsler.

Ja. AI-systemer bruger AVL-træer til symboltabeller, ordnede funktionslagre, kd-træbalancering og opslag af nærmeste naboer på strukturerede data. De understøtter også rangerede hentningsindekser i intelligente søgepipelines.

Ja. GitHub Copilot og lignende AI-assistenter scaffolder indsættelses-, sletnings- og rotationsrutiner i C++, Java eller Python, og generere enhedstests, der verificerer balancefaktoren, der er invariant på hver operation.

AVL Træer: Rotationer, Indsættelse, Sletning med C++ Eksempel

Hvad er AVL-træer?

Hvordan virker AVL Tree?

Balancefaktor i AVL-træer

Balancefaktorens egenskaber

AVL rotationer

Venstre – Venstre rotation

Højre – Højre rotation

Højre – Venstre rotation

Venstre – Højre rotation

Indsættelse i AVL Træer

Sletning i AVL-træer

C++ Eksempel på AVL-træer

Fordele ved AVL Træer

Ofte Stillede Spørgsmål

Opsummer dette indlæg med:

Tilmeld dig nyhedsbrevet

Hvad er AVL-træer?

Hvordan virker AVL Tree?

Balancefaktor i AVL-træer

Balancefaktorens egenskaber

AVL rotationer

Venstre – Venstre rotation

Højre – Højre rotation

Højre – Venstre rotation

Venstre – Højre rotation

Indsættelse i AVL Træer

RELATEREDE ARTIKLER

Sletning i AVL-træer

C++ Eksempel på AVL-træer

Fordele ved AVL Træer

Ofte Stillede Spørgsmål

Opsummer dette indlæg med:

Tilmeld dig nyhedsbrevet