Arbore AVL: rotații, inserare, ștergere cu C++ Exemplu

prin: Sarah Chen Sarah Chen
Hours Actualizat

⚡ Rezumat inteligent

Arborii AVL sunt arbori binari de căutare auto-echilibrați, în care diferența de înălțime dintre subarborii stânga și dreapta ai fiecărui nod rămâne între -1, 0 sau +1, garantând performanța de căutare O(log n).

  • 🌲 Definiție: Un arbore binar de căutare în care factorul de echilibru al fiecărui nod se află în {-1, 0, +1}, numit după inventatorii Adelson-Velsky și Landis.
  • 🇧🇷 Factor de echilibru: Calculat ca înălțime(stânga) − înălțime(dreapta); valorile în afara {-1, 0, +1} declanșează o rotație pentru a restabili echilibrul.
  • 🔄 Rotații: Patru cazuri — LL, RR, LR și RL — realiniază nodurile după inserții sau ștergeri dezechilibrate pentru a menține arborele logaritmic în înălțime.
  • ➕ Inserare: Inserție BST standard urmată de o mers ascendent care recalculează factorii de echilibru și efectuează cel mult o rotație simplă sau dublă.
  • ➖ Eliminarea: La fel ca ștergerea BST, dar poate produce cascade de rotații multiple în sus în arbore, deoarece înălțimea subarborelui se poate micșora la fiecare strămoș.
  • 🚀 Aplicații: Bazele de date, indexurile în memorie, metadatele sistemului de fișiere și structurile de căutare AI utilizează arbori AVL pentru căutări ordonate rapide.
Citește mai mult

Copaci AVL

Ce sunt arborii AVL?

Copaci AVL sunt arbori binari de căutare în care diferența de înălțime dintre subarborele stâng și drept al fiecărui nod este -1, 0 sau +1. Sunt BST-uri autoechilibrate care mențin timpul de căutare logaritmic, numite după inventatorii Adelson-Velsky și Landis (AVL).

Cum funcționează arborele AVL?

Pentru a înțelege de ce există arbori AVL, uitați-vă la ce nu merge bine cu o imagine simplă Arborele de căutare binarLuați în considerare aceste chei introduse în ordinea dată:

Lucru în arborele AVL

Vizualizare arbore AVL

Arborele crește liniar atunci când cheile sosesc în ordine crescătoare, degenerând căutarea la O(n). Aceasta anulează scopul unui BST - doar un arbore echilibrat menține căutarea logaritmică. Acum, uitați-vă la aceleași chei inserate într-o ordine diferită.

Lucru în arborele AVL

Aceleași chei, ordine de inserare diferită produc o formă mai superficială, astfel încât fiecare căutare se execută în O(log n). Arborii AVL impun această formă prin monitorizarea înălțimii la fiecare inserare și corectarea dezechilibrului fără a încălca ordinea BST.

Factorul de echilibru în arbori AVL

Factorul de echilibru (BF) tracks înălțimea fiecărui nod, astfel încât arborele să se poată autoechilibra din mers.

Proprietățile factorului de echilibru

Factorul de echilibru în arbori AVL

Arborele AVL factor de echilibru

  • Factorul de echilibru este diferența dintre înălțimea subarborelelui din stânga și înălțimea subarborelelui din dreapta.
  • Balance factor(node) = height(node->left) − height(node->right)
  • Singurele valori permise sunt -1, 0 și +1.
  • O valoare de -1 înseamnă că subarborele din dreapta conține un nivel suplimentar - nodul are o densitate mare în dreapta.
  • O valoare de +1 înseamnă că subarborele din stânga conține un nivel suplimentar - nodul are o densitate mare în stânga.
  • O valoare de 0 înseamnă că ambele părți au înălțime egală — nodul este perfect echilibrat.

Rotații AVL

Rotațiile se execută ori de câte ori o inserție sau o ștergere încalcă regula factorului de echilibru. Cele patru cazuri sunt LL, RR, LR și RL.

Stânga – Rotire stânga

Această rotație este efectuată atunci când un nou nod este inserat la copilul din stânga subarborele din stânga.

AVL Tree Left – Left Rotation

AVL Tree Left – Left Rotation

Se efectuează o singură rotație spre dreapta. Acest caz se declanșează atunci când un nod are BF +2, iar fiul său stâng are BF +1.

Rotație dreapta – dreapta

Această rotație este efectuată atunci când un nou nod este inserat în copilul din dreapta al subarborelui din dreapta.

AVL Tree Right – Rotire la dreapta

Se efectuează o singură rotație la stânga. Acest caz se declanșează atunci când un nod are BF −2, iar fiul său din dreapta are BF −1.

Rotație dreapta – stânga

Această rotație este efectuată atunci când un nou nod este inserat la copilul din stânga subarborelui din dreapta.

AVL Tree Dreapta – Rotire Stânga

Se declanșează când BF(nod) = −2 și BF(copil-dreapta) = +1. Rotește copilul drept la dreapta, apoi rotește nodul la stânga.

Rotire stânga – dreapta

Această rotație este efectuată atunci când un nou nod este inserat în copilul din dreapta al subarborelui din stânga.

AVL Tree Stânga – Rotire Dreapta

Se declanșează când BF(nod) = +2 și BF(copil-stâng) = −1. Rotește copilul stâng la stânga, apoi rotește nodul la dreapta.

Inserarea în arbori AVL

Inserarea este aproape identică cu o inserare BST simplă. După fiecare inserare, arborele se ridică și se reechilibrează. Inserarea se execută în timpul cel mai defavorabil O(log n).

Inserarea în arbori AVL

Implementarea inserției arborelui AVL

Pasul 1: Introduceți nodul folosind algoritmul BST standard. În exemplul de mai sus, introduceți 160.

Pasul 2: Actualizați factorul de echilibru al fiecărui strămoș de-a lungul căii de inserare.

Pasul 3: Dacă vreun strămoș încalcă intervalul factorului de echilibru, efectuați rotația corespunzătoare. În exemplu, factorul de echilibru al nodului 350 este încălcat, deci o rotație LL restabilește echilibrul.

  1. If BF(node) = +2 și BF(left-child) = +1, efectuați rotația LL.
  2. If BF(node) = −2 și BF(right-child) = −1, efectuați rotația RR.
  3. If BF(node) = −2 și BF(right-child) = +1, efectuați rotația RL.
  4. If BF(node) = +2 și BF(left-child) = −1, efectuați rotația LR.

ARTICOLE SIMILARE

Ștergerea în arbori AVL

Ștergerea urmează aceeași logică ca un BST simplu și se reechilibrează ulterior.

Pasul 1: Găsiți elementul din arbore.

Pasul 2: Ștergeți nodul folosind ștergerea BST standard.

Pasul 3: Două cazuri sunt posibile.

Caz 1: Ștergerea din subarborele din dreapta.

  • 1A. If BF(node) = +2 și BF(left-child) = +1, efectuați rotația LL.
  • 1B. If BF(node) = +2 și BF(left-child) = −1, efectuați rotația LR.
  • 1C. If BF(node) = +2 și BF(left-child) = 0, efectuați rotația LL.

Ștergerea în arbori AVL

Caz 2: Ștergerea din subarborele din stânga.

  • 2A. If BF(node) = −2 și BF(right-child) = −1, efectuați rotația RR.
  • 2B. If BF(node) = −2 și BF(right-child) = +1, efectuați rotația RL.
  • 2C. If BF(node) = −2 și BF(right-child) = 0, efectuați rotația RR.

Ștergerea în arbori AVL

C++ Exemplu de arbori AVL

Mai jos este a C++ program care implementează arbori AVL:

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

Exemplu de rulare a codului de mai sus:

  1. Copiați codul de mai sus și salvați-l într-un fișier numit avl.cpp.
  2. Compilați codul:
g++ avl.cpp -o run
  1. Rulați codul.
./run

C++ Exemplu de arbori AVL

Avantajele arborilor AVL

  • Înălțimea arborelui AVL este întotdeauna echilibrată și nu crește niciodată dincolo de log N.
  • Căutarea este mai rapidă decât într-un simplu arbore binar de căutare, deoarece arborele nu poate degenera.
  • Autoechilibrarea este automată — nu este necesară nicio etapă de reconstrucție.
  • Performanța deterministă se potrivește sistemelor în timp real și indexurilor în memorie.

Întrebări frecvente

Un arbore AVL este un arbore binar de căutare auto-echilibrat în care factorul de echilibru al fiecărui nod rămâne în {-1, 0, +1}. Rotațiile restabilesc acest invariant la fiecare inserare sau ștergere, păstrând...ping căutare, inserare și ștergere la O(log n).

Factorul de echilibrare al unui nod este egal cu înălțimea (subarborele stâng) minus înălțimea (subarborele drept). Valorile trebuie să se afle în {-1, 0, +1}. Un factor de echilibrare de +2 sau -2 semnalează că o inserare sau o ștergere a dezechilibrat nodul respectiv și este necesară o rotație.

Cele patru rotații sunt LL, RR, LR și RL. LL folosește o singură rotație la dreapta, RR folosește o singură rotație la stânga, iar LR și RL sunt rotații duble care combină o rotație pe copil cu o rotație opusă pe nod.

Inserarea respectă regula standard BST, apoi arborele revine în sus, actualizând înălțimile. Dacă vreun strămoș încalcă regula echilibrului, o rotație simplă sau dublă restabilește echilibrul. Este necesară cel mult o rotație per inserare.

Arborele AVL sunt strict echilibrate, cu un factor de echilibru de cel mult unu, oferind căutări mai rapide. Arborele Roșu-Negru permit un echilibru mai slab, ceea ce face ca inserarea și ștergerea să fie mai ieftine, dar căutarea puțin mai lentă. Bazele de date preferă roșu-negru pentru încărcările grele de scriere.

Arborele AVL alimentează indexurile bazelor de date în memorie, metadatele sistemului de fișiere, cozile de prioritate, căutările în agenda telefonică, verificatoarele ortografice și orice sarcină de lucru care necesită căutare deterministă O(log n) plus traversare în ordine pentru interogări de interval.

Da. Sistemele de inteligență artificială utilizează arbori AVL pentru tabele de simboluri, stocarea ordonată a caracteristicilor, echilibrarea arborilor kd și căutări de tip „cel mai apropiat vecin” în date structurate. De asemenea, acestea susțin indexurile de recuperare clasate în conductele inteligente de căutare.

Da. GitHub Copilot și asistenți AI similari creează rutine de inserare, ștergere și rotire în C++, Java, Pythonși generează teste unitare care verifică invariantul factorului de echilibrare la fiecare operație.

Rezumați această postare cu: