Un arbre AVL (Adelson-Velsky et Landis) est un arbre binaire de recherche auto-équilibré. Chaque nœud conserve une information appelée facteur d'équilibre, défini comme la différence de hauteur entre son sous-arbre droit et son sous-arbre gauche. Ce facteur doit toujours être compris entre -1 et 1, garantissant une hauteur logarithmique pour les opérations de rechreche, insertion et suppression.

Définition du nœud

Outre les pointeurs classiques vers les fils gauche et droit ainsi que la paire clé-valeur, un nœud AVL stocke un pointeur vers son parent (pour faciliter la remontée lors des mises à jour) et un entier représentant le facteur d'équilibre.

template <typename K, typename V>
struct NoeudAVL {
    NoeudAVL* droite;
    NoeudAVL* gauche;
    NoeudAVL* parent;
    std::pair<K, V> paire;
    int equilibre;

    NoeudAVL(const std::pair<K, V>& val)
        : droite(nullptr), gauche(nullptr), parent(nullptr),
          paire(val), equilibre(0) {}
};

Insertion dans un arbre AVL

L'insertion se décompose en trois phases : localisation de la position d'insertion, insertion effective du nœud, puis mise à jour des facteurs d'équilibre et rotations correctives si nécessaire.

Recherche et insertion du nœud

On parcourt l'arbre comme dans un arbre binaire de recherche classique, en conservant le parent du nœud courant. Une fois la feuille atteinte, on insère le nouveau nœud et on le rattache à son parent.

bool inserer(const std::pair<K, V>& element) {
    if (racine == nullptr) {
        racine = new NoeudAVL(element);
        return true;
    }

    NoeudAVL* parent = nullptr;
    NoeudAVL* courant = racine;

    // Localisation
    while (courant) {
        parent = courant;
        if (element.first < courant->paire.first)
            courant = courant->gauche;
        else if (element.first > courant->paire.first)
            courant = courant->droite;
        else
            return false; // clé existante
    }

    // Insertion
    courant = new NoeudAVL(element);
    if (element.first < parent->paire.first)
        parent->gauche = courant;
    else
        parent->droite = courant;
    courant->parent = parent;

Mise à jour des facteurs d'équilibre

Après insertion, seuls les ancêtres du nouveau nœud voient leur facteur d'équilibre changer. On remonte en partant du parent immédiat, en ajustant le facteur selon que le nœud est inséré à gauche (-1) ou à droite (+1). La mise à jour s'arrête dans deux cas :

• le facteur devient 0 (la hauteur de la branche n'a pas changé) ;
• on atteint la racine.

Rotations

Lorsqu'un facteur atteint +2 ou -2, il faut rééquilibrer la sous-branche par une ou deux rotations. Les quatre cas possibles dépendent du signe combiné du parent et du fils.

Rotation gauche (parent +2, fils +1)

void rotationGauche(NoeudAVL* pivot) {
    NoeudAVL* filsDroit = pivot->droite;
    NoeudAVL* sousArbreGauche = filsDroit->gauche;
    NoeudAVL* ancetre = pivot->parent;

    pivot->droite = sousArbreGauche;
    if (sousArbreGauche)
        sousArbreGauche->parent = pivot;

    filsDroit->gauche = pivot;
    pivot->parent = filsDroit;

    if (pivot == racine) {
        racine = filsDroit;
        racine->parent = nullptr;
    } else {
        if (ancetre->gauche == pivot)
            ancetre->gauche = filsDroit;
        else
            ancetre->droite = filsDroit;
        filsDroit->parent = ancetre;
    }
    pivot->equilibre = 0;
    filsDroit->equilibre = 0;
}

Rotation droite (parent -2, fils -1)

Symétrique : on élève le fils gauche.

Double rotation gauche‑droite (parent -2, fils +1)

On effectue d'abord une rotation gauche sur le fils, puis une rotation droite sur le parent. L'ajustement final des facteurs dépend du facteur initial du nœud central (celui qui descend puis monte).

void rotationGaucheDroite(NoeudAVL* pivot) {
    NoeudAVL* filsGauche = pivot->gauche;
    NoeudAVL* sousArbreInterne = filsGauche->droite;
    int facteurInitial = sousArbreInterne->equilibre;

    rotationGauche(pivot->gauche);
    rotationDroite(pivot);

    if (facteurInitial == 0) {
        sousArbreInterne->equilibre = 0;
        filsGauche->equilibre = 0;
        pivot->equilibre = 0;
    } else if (facteurInitial == -1) {
        filsGauche->equilibre = 0;
        pivot->equilibre = 1;
        sousArbreInterne->equilibre = 0;
    } else { // +1
        filsGauche->equilibre = -1;
        pivot->equilibre = 0;
        sousArbreInterne->equilibre = 0;
    }
}

Double rotation droite‑gauche (parent +2, fils -1)

Symétrique de la précédente : rotation droite sur le fils, puis gauche sur le parent.

Vérification de l'équilibre

Une fonction récursive peut parcourir l'arbre et confirmer que chaque nœud respecte la contrainte d'équilibre.

int hauteur(NoeudAVL* n) {
    if (!n) return 0;
    int hG = hauteur(n->gauche);
    int hD = hauteur(n->droite);
    return std::max(hG, hD) + 1;
}

bool estEquilibre() {
    return estEquilibreRec(racine);
}

bool estEquilibreRec(NoeudAVL* n) {
    if (!n) return true;
    int hG = hauteur(n->gauche);
    int hD = hauteur(n->droite);
    if ((hD - hG) != n->equilibre) {
        std::cerr << "Facteur incohérent : " << n->equilibre
                  << " (attendu " << (hD - hG) << ")\n";
        return false;
    }
    return std::abs(hD - hG) < 2
           && estEquilibreRec(n->gauche)
           && estEquilibreRec(n->droite);
}

Code complet et tests

La classe AVL contient les méthodes décrites, ainsi qu'un parcours infixe (InOrder) et une recherche. Les tests ci‑dessous vérifient les différentes rotations et l'équilibre global.