Arbres AVL : rotations, insertion, suppression avec C++ Exemple

Que sont les arbres AVL ?

Arbres AVL Ce sont des arbres binaires de recherche dans lesquels la différence de hauteur entre le sous-arbre gauche et le sous-arbre droit de chaque nœud est de -1, 0 ou +1. Ce sont des arbres binaires de recherche auto-équilibrés qui maintiennent un temps de recherche logarithmique, nommés d'après leurs inventeurs Adelson-Velsky et Landis (AVL).

Comment fonctionne l’arbre AVL ?

Pour comprendre l'utilité des arbres AVL, il faut examiner les problèmes rencontrés avec un arbre simple. Arbre de recherche binaireConsidérons ces clés insérées dans l'ordre indiqué :

Visualisation de l'arborescence AVL

L'arbre croît linéairement lorsque les clés arrivent par ordre croissant, ce qui réduit la complexité de la recherche à O(n). Cela va à l'encontre du principe d'un arbre binaire de recherche (ABR) : seul un arbre équilibré garantit une complexité logarithmique. Considérons maintenant les mêmes clés insérées dans un ordre différent.

L'utilisation de clés identiques dans un ordre d'insertion différent produit une structure moins profonde, ce qui réduit la complexité temporelle de chaque recherche (O(log n)). Les arbres AVL garantissent cette structure en contrôlant la hauteur à chaque insertion et en corrigeant les déséquilibres sans enfreindre l'ordre des arbres binaires de recherche.

Facteur d’équilibre dans les arbres AVL

Le facteur d'équilibre (BF) tracks la hauteur de chaque nœud afin que l'arbre puisse s'auto-équilibrer à la volée.

Propriétés du facteur d'équilibre

Arbre AVL du facteur d'équilibre

• Le facteur d'équilibre est la différence entre la hauteur du sous-arbre gauche et la hauteur du sous-arbre droit.
• Balance factor(node) = height(node->left) − height(node->right)
• Les seules valeurs autorisées sont −1, 0 et +1.
• Une valeur de −1 signifie que le sous-arbre droit contient un niveau supplémentaire — le nœud est lourd à droite.
• Une valeur de +1 signifie que le sous-arbre gauche contient un niveau supplémentaire — le nœud est lourd à gauche.
• Une valeur de 0 signifie que les deux côtés ont la même hauteur — le nœud est parfaitement équilibré.

Rotations AVL

Les rotations sont déclenchées chaque fois qu'une insertion ou une suppression enfreint la règle du facteur d'équilibre. Les quatre cas sont LL, RR, LR et RL.

Gauche – Rotation à gauche

Cette rotation est effectuée lorsqu'un nouveau nœud est inséré au niveau de l'enfant gauche du sous-arbre gauche.

Arbre AVL gauche – Rotation gauche

Une seule rotation à droite est effectuée. Ce cas se produit lorsqu'un nœud a BF +2 et que son enfant gauche a BF +1.

Droite – Rotation à droite

Cette rotation est effectuée lorsqu'un nouveau nœud est inséré au niveau de l'enfant droit du sous-arbre droit.

Une seule rotation à gauche est effectuée. Ce cas se produit lorsqu'un nœud a BF −2 et que son enfant droit a BF −1.

Rotation droite – gauche

Cette rotation est effectuée lorsqu'un nouveau nœud est inséré au niveau de l'enfant gauche du sous-arbre droit.

Se déclenche lorsque BF(nœud) = −2 et BF(enfant-droit) = +1. Faites pivoter l'enfant-droit vers la droite, puis faites pivoter le nœud vers la gauche.

Rotation gauche – droite

Cette rotation est effectuée lorsqu'un nouveau nœud est inséré au niveau de l'enfant droit du sous-arbre gauche.

Se déclenche lorsque BF(nœud) = +2 et BF(enfant-gauche) = −1. Faites pivoter l'enfant-gauche vers la gauche, puis faites pivoter le nœud vers la droite.

Insertion dans les arbres AVL

L'insertion est quasiment identique à une insertion classique dans un arbre binaire de recherche. Après chaque insertion, l'arbre remonte et se rééquilibre. L'insertion s'effectue en O(log n) dans le pire des cas.

Implémentation de l'insertion d'arborescence AVL

Étape 1 : Insérez le nœud en utilisant l'algorithme BST standard. Dans l'exemple ci-dessus, insérez 160.

Étape 2 : Mettre à jour le facteur d'équilibre de chaque ancêtre le long du chemin d'insertion.

Étape 3 : Si un ancêtre quelconque dépasse la plage du facteur d'équilibre, effectuez la rotation correspondante. Dans l'exemple, le facteur d'équilibre du nœud 350 est dépassé ; une rotation LL rétablit donc l'équilibre.

1. If BF(node) = +2 et BF(left-child) = +1, effectuer une rotation LL.
2. If BF(node) = −2 et BF(right-child) = −1, effectuer une rotation RR.
3. If BF(node) = −2 et BF(right-child) = +1, effectuer une rotation RL.
4. If BF(node) = +2 et BF(left-child) = −1, effectuez une rotation LR.

Suppression dans les arborescences AVL

La suppression suit la même logique qu'un arbre binaire de recherche classique et se rééquilibre ensuite.

Étape 1 : Trouvez l'élément dans l'arborescence.

Étape 2 : Supprimez le nœud en utilisant la suppression standard d'un arbre binaire de recherche.

Étape 3 : Deux cas sont possibles.

1 cas: Suppression du sous-arbre droit.

• 1A. If BF(node) = +2 et BF(left-child) = +1, effectuer une rotation LL.
• 1B. If BF(node) = +2 et BF(left-child) = −1, effectuez une rotation LR.
• 1C. If BF(node) = +2 et BF(left-child) = 0, effectuer une rotation LL.

2 cas: Suppression dans le sous-arbre gauche.

• 2A. If BF(node) = −2 et BF(right-child) = −1, effectuer une rotation RR.
• 2B. If BF(node) = −2 et BF(right-child) = +1, effectuer une rotation RL.
• 2C. If BF(node) = −2 et BF(right-child) = 0, effectuer une rotation RR.

C++ Exemple d'arbres AVL

Voici une C++ programme implémentant les arbres 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);
}

Exemple d'exécution du code ci-dessus :

1. Copiez le code ci-dessus et enregistrez-le dans un fichier nommé avl.cpp.
2. Compilez le code :

g++ avl.cpp -o run

3. Exécutez le code.

./run

Avantages des arbres AVL

• La hauteur de l'arbre AVL est toujours équilibrée et ne dépasse jamais la bûche N.
• La recherche est plus rapide qu'avec un arbre binaire de recherche classique car l'arbre ne peut pas dégénérer.
• L'équilibrage automatique est intégré ; aucune étape de reconstruction n'est nécessaire.
• Les performances déterministes conviennent aux systèmes temps réel et aux index en mémoire.

FAQ