Alberi AVL: rotazioni, inserimento, eliminazione con C++ Esempio

Cosa sono gli alberi AVL?

Alberi AVL Gli alberi di ricerca binaria (BST) sono alberi di ricerca binaria in cui la differenza di altezza tra il sottoalbero sinistro e quello destro di ogni nodo è -1, 0 o +1. Si tratta di BST autobilancianti che mantengono un tempo di ricerca logaritmico e prendono il nome dai loro inventori Adelson-Velsky e Landis (AVL).

Come funziona AVL Tree?

Per capire perché esistono gli alberi AVL, guarda cosa va storto con un semplice Albero di ricerca binarioConsidera questi tasti inseriti nell'ordine indicato:

Visualizzazione dell'albero AVL

L'albero cresce linearmente quando le chiavi arrivano in ordine crescente, degenerando la ricerca in O(n). Questo vanifica lo scopo di un BST: solo un albero bilanciato mantiene la ricerca logaritmica. Ora osserviamo le stesse chiavi inserite in un ordine diverso.

Le stesse chiavi, ma un diverso ordine di inserimento, producono una forma meno profonda, quindi ogni ricerca viene eseguita in O(log n). Gli alberi AVL impongono tale forma monitorando l'altezza ad ogni inserimento e correggendo lo squilibrio senza rompere l'ordinamento dell'albero di ricerca binario.

Fattore di equilibrio negli alberi AVL

Il fattore di bilanciamento (BF) traccalcola l'altezza di ciascun nodo in modo che l'albero possa autobilanciarsi al volo.

Proprietà del fattore di equilibrio

Albero del fattore di equilibrio AVL

• Il fattore di bilanciamento è la differenza tra l'altezza del sottoalbero sinistro e l'altezza del sottoalbero destro.
• Balance factor(node) = height(node->left) − height(node->right)
• Gli unici valori consentiti sono −1, 0 e +1.
• Un valore di -1 significa che il sottoalbero destro contiene un livello extra: il nodo è sbilanciato a destra.
• Un valore di +1 significa che il sottoalbero sinistro contiene un livello extra: il nodo è sbilanciato a sinistra.
• Un valore pari a 0 significa che entrambi i lati hanno la stessa altezza: il nodo è perfettamente bilanciato.

Rotazioni AVL

Le rotazioni vengono eseguite ogni volta che un inserimento o una cancellazione viola la regola del fattore di bilanciamento. I quattro casi sono LL, RR, LR e RL.

Sinistra – Rotazione sinistra

Questa rotazione viene eseguita quando un nuovo nodo viene inserito nel figlio sinistro del sottoalbero sinistro.

AVL Albero a sinistra – Rotazione a sinistra

Viene eseguita una singola rotazione a destra. Questo caso si verifica quando un nodo ha BF +2 e il suo figlio sinistro ha BF +1.

Destra – Rotazione a destra

Questa rotazione viene eseguita quando un nuovo nodo viene inserito nel figlio destro del sottoalbero destro.

Viene eseguita una singola rotazione a sinistra. Questo caso si verifica quando un nodo ha BF −2 e il suo figlio destro ha BF −1.

Rotazione destra – sinistra

Questa rotazione viene eseguita quando un nuovo nodo viene inserito nel figlio sinistro del sottoalbero destro.

Si attiva quando BF(nodo) = −2 e BF(figlio destro) = +1. Ruota a destra il figlio destro, quindi ruota a sinistra il nodo.

Rotazione sinistra-destra

Questa rotazione viene eseguita quando un nuovo nodo viene inserito nel figlio destro del sottoalbero sinistro.

Si attiva quando BF(nodo) = +2 e BF(figlio sinistro) = −1. Ruota a sinistra il figlio sinistro, quindi ruota a destra il nodo.

Inserimento negli alberi AVL

L'inserimento è quasi identico a un semplice inserimento in un albero di ricerca binario (BST). Dopo ogni inserimento, l'albero risale e si ribilancia. L'inserimento ha una complessità temporale di O(log n) nel caso peggiore.

Implementazione dell'inserimento dell'albero AVL

Passo 1: Inserisci il nodo utilizzando l'algoritmo BST standard. Nell'esempio precedente, inserisci 160.

Passo 2: Aggiorna il fattore di bilanciamento di ogni antenato lungo il percorso di inserimento.

Passo 3: Se un antenato viola l'intervallo del fattore di bilanciamento, esegui la rotazione corrispondente. Nell'esempio, il fattore di bilanciamento del nodo 350 viene violato, quindi una rotazione LL ripristina l'equilibrio.

1. If BF(node) = +2 and BF(left-child) = +1, eseguire la rotazione LL.
2. If BF(node) = −2 and BF(right-child) = −1, eseguire la rotazione RR.
3. If BF(node) = −2 and BF(right-child) = +1, eseguire la rotazione RL.
4. If BF(node) = +2 and BF(left-child) = −1, eseguire la rotazione LR.

Cancellazione negli alberi AVL

La cancellazione segue la stessa logica di un semplice albero di ricerca binario e il successivo ribilanciamento.

Passo 1: Trova l'elemento nell'albero.

Passo 2: Elimina il nodo utilizzando la procedura standard di eliminazione degli alberi di ricerca binaria (BST).

Passo 3: Sono possibili due casi.

Caso 1: Eliminazione dal sottoalbero destro.

• 1A. If BF(node) = +2 and BF(left-child) = +1, eseguire la rotazione LL.
• 1B. If BF(node) = +2 and BF(left-child) = −1, eseguire la rotazione LR.
• 1C. If BF(node) = +2 and BF(left-child) = 0, eseguire la rotazione LL.

Caso 2: Eliminazione dal sottoalbero sinistro.

• 2A. If BF(node) = −2 and BF(right-child) = −1, eseguire la rotazione RR.
• 2B. If BF(node) = −2 and BF(right-child) = +1, eseguire la rotazione RL.
• 2C. If BF(node) = −2 and BF(right-child) = 0, eseguire la rotazione RR.

C++ Esempio di alberi AVL

Di seguito è riportato un C++ Programma che implementa gli alberi 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);
}

Esempio pratico del codice sopra riportato:

1. Copia il codice sopra e salvalo in un file chiamato avl.cpp.
2. Compila il codice:

g++ avl.cpp -o run

3. Esegui il codice.

./run

Vantaggi degli alberi AVL

• L'altezza dell'albero AVL è sempre bilanciata e non cresce mai oltre log N.
• La ricerca è più veloce di un semplice albero di ricerca binario perché l'albero non può degenerare.
• Il bilanciamento automatico è automatico: non è necessario alcun passaggio di ricostruzione.
• Le prestazioni deterministiche sono adatte ai sistemi in tempo reale e agli indici in memoria.

DOMANDE FREQUENTI