AVL stabla: rotacije, umetanje, brisanje sa C++ Primjer

⚡ Pametni sažetak

AVL stabla su samobalansirajuća binarna stabla pretraživanja gdje razlika visine između lijevog i desnog podstabla svakog čvora ostaje unutar -1, 0 ili +1, što jamči performanse pretraživanja O(log n).

🌲 Definicija: Binarno stablo pretraživanja u kojem faktor ravnoteže svakog čvora leži u {-1, 0, +1}, nazvano po izumiteljima Adelson-Velskyju i Landisu.
⚖️ Faktor ravnoteže: Izračunava se kao visina(lijevo) − visina(desno); vrijednosti izvan {-1, 0, +1} pokreću rotaciju radi vraćanja ravnoteže.
🔄 Rotacije: Četiri slučaja - LL, RR, LR i RL - preusmjeravaju čvorove nakon neuravnoteženih umetanja ili brisanja kako bi se stablo održalo logaritamskom visinom.
➕ Umetanje: Standardni BST umetnuti postupak nakon kojeg slijedi uzlazni hod koji ponovno izračunava faktore ravnoteže i izvodi najviše jednu jednostruku ili dvostruku rotaciju.
➖ Brisanje: Isto kao i BST brisanje, ali može kaskadno proširiti više rotacija uz stablo jer se visina podstabla može smanjiti kod svakog pretka.
🚀 Primjena: Baze podataka, indeksi u memoriji, metapodaci datotečnog sustava i strukture umjetne inteligencije za pretraživanje koriste AVL stabla za brzo uređeno pretraživanje.

Pročitaj više

Što su AVL stabla?

AVL stabla su binarna stabla pretraživanja u kojima je razlika visine između lijevog i desnog podstabla svakog čvora -1, 0 ili +1. To su samobalansirajuća BST-a koja održavaju logaritamsko vrijeme pretraživanja, nazvana po izumiteljima Adelson-Velskyju i Landisu (AVL).

Kako radi AVL stablo?

Da biste razumjeli zašto AVL stabla postoje, pogledajte što ne ide po zlu s ravnicom Stablo binarnog pretraživanjaRazmotrite ove ključeve umetnute zadanim redoslijedom:

Vizualizacija AVL stabla

Stablo raste linearno kada ključevi stižu u rastućem redoslijedu, degenerirajući pretragu na O(n). To poništava svrhu BST-a - samo uravnoteženo stablo održava pretragu logaritamskom. Sada pogledajte iste ključeve umetnute u drugom redoslijedu.

Isti ključevi, različiti redoslijed umetanja proizvode plići oblik, pa se svako pretraživanje izvršava u O(log n). AVL stabla provode taj oblik promatrajući visinu pri svakom umetanju i ispravljajući neravnotežu bez narušavanja BST redoslijeda.

Faktor ravnoteže u AVL stablima

Faktor ravnoteže (BF) tracks visinu svakog čvora kako bi se stablo moglo samouravnotežiti u hodu.

Svojstva faktora ravnoteže

Faktor ravnoteže AVL stablo

Faktor ravnoteže je razlika između visine lijevog podstabla i visine desnog podstabla.
Balance factor(node) = height(node->left) − height(node->right)
Jedine dopuštene vrijednosti su −1, 0 i +1.
Vrijednost -1 znači da desno podstablo sadrži jednu dodatnu razinu - čvor ima pretežak desni dio.
Vrijednost +1 znači da lijevo podstablo sadrži jednu dodatnu razinu - čvor je pretežak s lijeve strane.
Vrijednost 0 znači da obje strane imaju jednaku visinu - čvor je savršeno uravnotežen.

AVL rotacije

Rotacije se izvode kad god umetanje ili brisanje prekrši pravilo faktora ravnoteže. Četiri slučaja su LL, RR, LR i RL.

Lijevo – Lijeva rotacija

Ova rotacija se izvodi kada se novi čvor umetne u lijevo dijete lijevog podstabla.

AVL stablo lijevo – rotacija lijevo

Izvodi se jedna rotacija udesno. Ovaj slučaj se aktivira kada čvor ima BF +2, a njegov lijevi podređeni čvor ima BF +1.

Desno – Desna rotacija

Ova rotacija se izvodi kada se novi čvor umetne u desno dijete desnog podstabla.

Izvodi se jedna rotacija ulijevo. Ovaj slučaj se aktivira kada čvor ima BF −2, a njegov desni potomak ima BF −1.

Rotacija desno – lijevo

Ova rotacija se izvodi kada se novi čvor umetne u lijevo dijete desnog podstabla.

Okida se kada je BF(čvor) = −2 i BF(desno-dijete) = +1. Rotirajte desno desno dijete, a zatim rotirajte čvor lijevo.

Rotacija lijevo – desno

Ova rotacija se izvodi kada se novi čvor umetne u desno dijete lijevog podstabla.

Okida se kada je BF(čvor) = +2 i BF(lijevo-dijete) = −1. Rotirajte lijevo dijete, a zatim čvor desno.

Umetanje u AVL stabla

Umetanje je gotovo identično običnom BST umetanju. Nakon svakog umetanja, stablo se podiže i ponovno uravnotežuje. Umetanje se izvršava u najgorem slučaju za O(log n).

Implementacija umetanja AVL stabla

Korak 1: Umetnite čvor koristeći standardni BST algoritam. U gornjem primjeru umetnite 160.

Korak 2: Ažurirajte faktor ravnoteže svakog pretka duž putanje umetanja.

Korak 3: Ako bilo koji predak prekrši raspon faktora ravnoteže, izvršite rotaciju podudaranja. U primjeru, faktor ravnoteže čvora 350 je prekršen, pa rotacija LL vraća ravnotežu.

If BF(node) = +2 i BF(left-child) = +1, izvršite LL rotaciju.
If BF(node) = −2 i BF(right-child) = −1, izvršite RR rotaciju.
If BF(node) = −2 i BF(right-child) = +1, izvršite RL rotaciju.
If BF(node) = +2 i BF(left-child) = −1, izvršite LR rotaciju.

Brisanje u AVL stablima

Brisanje slijedi istu logiku kao i obični BST i naknadno se ponovno uravnotežuje.

Korak 1: Pronađite element u stablu.

Korak 2: Izbrišite čvor standardnim BST brisanjem.

Korak 3: Moguća su dva slučaja.

Slučaj 1: Brisanje iz desnog podstabla.

1A. If BF(node) = +2 i BF(left-child) = +1, izvršite LL rotaciju.
1B. If BF(node) = +2 i BF(left-child) = −1, izvršite LR rotaciju.
1C. If BF(node) = +2 i BF(left-child) = 0, izvršite LL rotaciju.

Slučaj 2: Brisanje iz lijevog podstabla.

2A. If BF(node) = −2 i BF(right-child) = −1, izvršite RR rotaciju.
2B. If BF(node) = −2 i BF(right-child) = +1, izvršite RL rotaciju.
2C. If BF(node) = −2 i BF(right-child) = 0, izvršite RR rotaciju.

C++ Primjer AVL stabala

Ispod je a C++ program koji implementira AVL stabla:

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

Primjer izvođenja gornjeg koda:

Kopirajte gornji kod i spremite ga u datoteku pod nazivom avl.cpp.
Sastavite kod:

g++ avl.cpp -o run

Pokrenite kod.

./run

Prednosti AVL stabala

Visina AVL stabla je uvijek uravnotežena i nikada ne raste iznad log N.
Pretraživanje je brže od običnog binarnog stabla pretraživanja jer se stablo ne može degenerirati.
Samobalansiranje je automatsko - nije potreban korak ponovne izgradnje.
Determinističke performanse odgovaraju sustavima u stvarnom vremenu i indeksima u memoriji.

Pitanja i odgovori

AVL stablo je samobalansirajuće binarno stablo pretraživanja gdje faktor ravnoteže svakog čvora ostaje u {-1, 0, +1}. Rotacije vraćaju ovu invarijantu pri svakom umetanju ili brisanju, zadržavajućiping pretraživanje, umetanje i brisanje u O(log n).

Faktor ravnoteže čvora jednak je visini (lijevo podstablo) minus visini (desno podstablo). Vrijednosti moraju biti u rasponu {-1, 0, +1}. Faktor ravnoteže od +2 ili -2 signalizira da je umetanje ili brisanje poremetilo ravnotežu tog čvora i da je potrebna rotacija.

Četiri rotacije su LL, RR, LR i RL. LL koristi jednu desnu rotaciju, RR koristi jednu lijevu rotaciju, a LR i RL su dvostruke rotacije koje kombiniraju jednu rotaciju na podređenom čvoru sa suprotnom rotacijom na čvoru.

Umetanje slijedi standardno BST pravilo, a zatim se stablo vraća natrag prema gore ažurirajući visine. Ako bilo koji predak prekrši pravilo ravnoteže, jedna jednostruka ili dvostruka rotacija vraća ravnotežu. Potrebna je najviše jedna rotacija po umetanju.

AVL stabla su strogo uravnotežena s faktorom ravnoteže od najviše jedan, što omogućuje brže pretraživanje. Crveno-crna stabla omogućuju labaviji balans, što unos i brisanje čini jeftinijim, ali pretraživanje nešto sporijim. Baze podataka preferiraju crveno-crna stabla za opterećenja s velikim brojem zapisa.

AVL stabla pokreću indekse baza podataka u memoriji, metapodatke datotečnog sustava, redove prioriteta, pretraživanja telefonskog imenika, provjere pravopisa i bilo koje opterećenje koje zahtijeva determinističko O(log n) pretraživanje plus prolazak po redoslijedu za upite raspona.

Da. AI sustavi koriste AVL stabla za tablice simbola, uređene pohrane značajki, balansiranje kd stabla i pretraživanja najbližeg susjeda na strukturiranim podacima. Također podupiru rangirane indekse pretraživanja u inteligentnim cjevovodima pretraživanja.

Da. GitHub Copilot i slični AI asistenti scaffoldiraju rutine umetanja, brisanja i rotacije u C++, Java, ili Pythoni generirati jedinične testove koji provjeravaju invarijantnost faktora ravnoteže na svakoj operaciji.

AVL stabla: rotacije, umetanje, brisanje sa C++ Primjer

Što su AVL stabla?

Kako radi AVL stablo?

Faktor ravnoteže u AVL stablima

Svojstva faktora ravnoteže

AVL rotacije

Lijevo – Lijeva rotacija

Desno – Desna rotacija

Rotacija desno – lijevo

Rotacija lijevo – desno

Umetanje u AVL stabla

Brisanje u AVL stablima

C++ Primjer AVL stabala

Prednosti AVL stabala

Pitanja i odgovori

Sažmite ovu objavu uz:

Prijavite se za bilten

Što su AVL stabla?

Kako radi AVL stablo?

Faktor ravnoteže u AVL stablima

Svojstva faktora ravnoteže

AVL rotacije

Lijevo – Lijeva rotacija

Desno – Desna rotacija

Rotacija desno – lijevo

Rotacija lijevo – desno

Umetanje u AVL stabla

POVEZANI ČLANCI

Brisanje u AVL stablima

C++ Primjer AVL stabala

Prednosti AVL stabala

Pitanja i odgovori

Sažmite ovu objavu uz:

Prijavite se za bilten