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

By: Sarah Chen Sarah Chen
Hours Ažurirano

⚡ 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

AVL stabla

Š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:

AVL rad na stablu

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.

AVL rad na stablu

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 u AVL stablima

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

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.

AVL stablo desno – desna rotacija

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.

Rotacija AVL stabla desno – lijevo

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.

Rotacija AVL stabla lijevo – desno

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).

Umetanje u AVL stabla

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.

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

POVEZANI ČLANCI

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.

Brisanje u AVL stablima

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.

Brisanje u AVL stablima

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:

  1. Kopirajte gornji kod i spremite ga u datoteku pod nazivom avl.cpp.
  2. Sastavite kod:
g++ avl.cpp -o run
  1. Pokrenite kod.
./run

C++ Primjer AVL stabala

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.

Sažmite ovu objavu uz: