Cette différence se traduit concrètement lors des insertions et suppressions : un arbre AVL peut nécessiter plusieurs rotations successives pour restaurer son invariant, tandis qu’un ARN limite généralement le nombre de rotations à une ou deux par opération, grâce à un mécanisme de recoloration combiné à des rotations ciblées. Ainsi, dans un scénario où les recherches dominent largement (par exemple, une base de données en lecture seule), un arbre AVL offre une meilleure performance théorique. En revanche, lorsque les opérations d’insertion, suppression et recherche sont fréquentes et relativement équilibrées, l’ARN fournit un compromis optimal entre complexité amortie et stabilité de la hauteur.

Prérequis : arbre binaire de recherche (ABR)

L’ARN repose fondamentalement sur la structure d’un arbre binaire de recherche. Un ABR est défini récursivement comme suit :

• Un arbre vide, ou
• Un arbre tel que, pour tout nœud n :
  • Tous les nœuds du sous-arbre gauche ont une clé strictement inférieure à celle de n ;
  • Tous les nœuds du sous-arbre droit ont une clé strictement supérieure à celle de n ;
  • Les sous-arbres gauche et droit sont eux-mêmes des ABR ;
  • Aucune clé n’est dupliquée.

Dans le cas moyen (arbre construit aléatoirement), la hauteur d’un ABR à n nœuds est en Θ(log n), rendant les opérations de recherche, insertion et suppression efficaces en temps logarithmique. Toutefois, dans le pire cas — par exemple, lors d’une insertion séquentielle de clés triées — l’arbre dégénère en une liste chaînée de hauteur n, dégradant toutes ces opérations à O(n). C’est précisément pour éviter ce scénario que les arbres auto-équilibrés, comme l’ARN, introduisent des contraintes supplémentaires.

Structure et invariants de l’arbre rouge-noir

Un arbre rouge-noir est un ABR enrichi de deux éléments : une couleur attribuée à chaque nœud (rouge ou noir), et cinq propriétés invariantes qui garantissent que la hauteur de l’arbre reste toujours inférieure ou égale à 2 log2(n + 1). Ces règles sont les suivantes :

1. Chaque nœud est soit rouge, soit noir.
2. La racine est noire.
3. Toutes les feuilles (représentées par des pointeurs NIL) sont noires.
4. Si un nœud est rouge, alors ses deux enfants sont noirs (aucun lien rouge-rouge).
5. Pour tout nœud, tous les chemins menant aux feuilles NIL contiennent exactemant le même nombre de nœuds noirs (propriété de « noir-équilibre »).

Ces propriétés assurent que le chemin le plus long depuis la racine jusqu’à une feuille ne dépasse jamais le double de la longueur du chemin le plus court — ce qui suffit à borner la hauteur globale et donc à garantir une complexité en O(log n) pour les opérations fondamentales.

Rotations : outils de rééquilibrage

Lorsqu’une opération modifie la structure de l’arbre (insertion ou suppression), elle peut temporairement violer un ou plusieurs invariants. Pour restaurer la validité de l’ARN, on applique deux types d’opérations élémentaires : la rotation gauche et la rotation droite. Ces transformations préservent la propriété de recherche (ordre relatif des clés), mais modifient localement la forme de l’arbre — ce qui permet de déplacer des nœuds vers des positions où leur couleur ne pose plus de conflit.

Rotation gauche autour d’un nœud p : soit p un nœud non-feuille dont le fils droit r existe. La rotation gauche fait de r le nouveau parenet de p, place le sous-arbre gauche de r comme fils droit de p, puis met p comme fils gauche de r.

void leftRotate(Node*& root, Node* p) {
    Node* r = p->right;
    p->right = r->left;
    if (r->left != nullptr) r->left->parent = p;
    r->parent = p->parent;

    if (p->parent == nullptr) {
        root = r;
    } else if (p == p->parent->left) {
        p->parent->left = r;
    } else {
        p->parent->right = r;
    }

    r->left = p;
    p->parent = r;
}

La rotation droite est symétrique et s’implémente de manière analogue.

Insertion dans un arbre rouge-noir

L’insertion commence comme dans un ABR classique : on localise la position d’insertion, puis on ajoute le nouveau nœud comme feuille. Pour minimiser les violations immédiates, le nœud inséré est systématiquement coloré en rouge. Cette décision évite de rompre la propriété 5 (noir-équilibre) immédiatement, mais peut violer la règle 4 (pas de deux rouges consécutifs) si le parent est aussi rouge.

La correction post-insertion, implémentée dans fixAfterInsertion, traite trois cas principaux selon la configuration locale (parent, oncle, grand-parenet). Chaque cas utilise une combinaison de recoloration et/ou de rotation pour remonter progressivement la violation vers la racine, jusqu’à ce que l’arbre retrouve tous ses invariants — y compris la contrainte que la racine soit noire.

void fixAfterInsertion(Node* z) {
    while (z != root && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node* uncle = z->parent->parent->right;
            if (uncle != nullptr && uncle->color == RED) {
                // Cas 1 : oncle rouge → recoloration uniquement
                z->parent->color = BLACK;
                uncle->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    // Cas 2 : zig → rotation gauche sur le parent
                    z = z->parent;
                    leftRotate(root, z);
                }
                // Cas 3 : zig-zag → rotation droite sur le grand-parent
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else {
            // Symétrique pour le côté droit
            Node* uncle = z->parent->parent->left;
            if (uncle != nullptr && uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

Suppression dans un arbre rouge-noir

La suppression suit d’abord l’algorithme standard d’un ABR : si le nœud à supprimer a deux fils non vides, on remplace sa clé par celle de son successeur (le plus petit élément du sous-arbre droit), puis on supprime effectivement ce successeur — qui, par définition, possède au plus un fils.

Le défi spécifique à l’ARN apparaît lorsqu’on supprime un nœud noir : cela réduit le nombre de nœuds noirs sur certains chemins, violant la propriété 5. Pour y remédier, l’algorithme introduit une notion abstraite de « double noir », attribuée temporairement au fils qui remplace le nœud supprimé. Ce « double noir » symbolise un déséquilibre local qu’il faut remonter vers la racine via une série de recolorations et rotations, organisées en quatre cas selon la couleur du frère et de ses enfants.

Chaque cas transforme la situation actuelle en une autre plus simple, jusqu’à ce que le « double noir » soit absorbé (soit par un nœud rouge qui devient noir, soit par la racine elle-même), ou qu’il disparaisse complètement.