05 — Les arbres équilibrés (AVL, rouge-noir)

Ce que tu vas apprendre

• Pourquoi équilibrer un arbre garantit le O(log n)
• La rotation, l'opération qui rééquilibre
• La différence entre arbres AVL et rouge-noir
• Où ces arbres sont utilisés dans le vrai monde

Prérequis

• 04 — Les arbres binaires de recherche

L'article précédent a montré le talon d'Achille du BST : sur une insertion triée, il dégénère en liste et la recherche tombe à O(n). Les arbres équilibrés résolvent ce problème en réorganisant leur structure à chaque modification, pour garder la hauteur proche de log n quoi qu'il arrive. C'est ce qui transforme la promesse théorique du BST en garantie pratique, et c'est ce qui fait tourner les maps ordonnées et les index de bases de données.

L'idée : garder la hauteur basse

Toutes les opérations d'un arbre de recherche sont en O(hauteur). Pour garantir O(log n), il suffit de garantir que la hauteur reste de l'ordre de log n, même dans le pire ordre d'insertion. Un arbre équilibré maintient un invariant supplémentaire, en plus de l'ordre des valeurs : aucune branche ne peut devenir beaucoup plus longue que les autres. Quand une insertion ou une suppression menace cet équilibre, l'arbre se réorganise.

L'opération de réorganisation est la rotation.

La rotation

Une rotation réarrange localement trois nœuds pour réduire la hauteur d'un côté, sans casser l'ordre des valeurs. C'est une transformation en O(1) qui change quel nœud est « au-dessus ».

Rotation gauche autour de A :

    A                  B
     \                / \
      B      →       A   C
       \              \
        C              (sous-arbre)

Avant, la branche A→B→C a une hauteur de 3. Après la rotation gauche, B remonte, A et C deviennent ses enfants, hauteur 2. L'invariant d'ordre du BST est préservé : tout ce qui était à gauche de chaque nœud le reste. Les rotations (gauche et droite, et leurs combinaisons) sont les briques de tous les rééquilibrages.

Les arbres AVL

L'arbre AVL (du nom de ses inventeurs, Adelson-Velsky et Landis, 1962) est le premier arbre auto-équilibré. Son invariant est strict : pour chaque nœud, les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1. À chaque insertion ou suppression, on vérifie ce facteur d'équilibre en remontant vers la racine, et on applique des rotations dès qu'il est violé.

Conséquence de cet invariant strict : l'arbre AVL est très bien équilibré, donc les recherches sont rapides. Le prix est que les insertions et suppressions peuvent déclencher plus de rotations pour maintenir l'équilibre serré.

Les arbres rouge-noir

L'arbre rouge-noir relâche l'invariant. Chaque nœud porte une couleur (rouge ou noir), et un jeu de règles sur les couleurs garantit qu'aucune branche n'est plus de deux fois plus longue qu'une autre. L'équilibre est donc moins parfait que l'AVL, mais toujours suffisant pour O(log n).

L'intérêt du compromis : l'arbre rouge-noir fait moins de rotations lors des modifications, ce qui le rend plus rapide en écriture, au prix de recherches très légèrement plus lentes. C'est pourquoi il est le choix par défaut des bibliothèques généralistes.

Où on les rencontre

On n'implémente quasiment jamais ces arbres à la main : ils sont fournis et cachés dans les outils du quotidien.

• Les maps et sets ordonnés : le std::map et std::set du C++, le TreeMap de Java sont des arbres rouge-noir. Ils gardent les clés triées, contrairement à une hashmap.
• Les index de bases de données : la plupart des index reposent sur des B-arbres (B-tree), une généralisation des arbres équilibrés où chaque nœud a beaucoup d'enfants, adaptée au stockage sur disque. C'est ce qui rend une requête WHERE x BETWEEN a AND b rapide sur une colonne indexée.
• Les ordonnanceurs : le scheduler CFS du noyau Linux a longtemps utilisé un arbre rouge-noir pour ordonner les tâches.

Ni JavaScript ni Python n'ont d'arbre équilibré dans leur bibliothèque standard. En Python, la bibliothèque sortedcontainers offre l'équivalent (par une autre technique). Quand tu as besoin de clés triées avec recherche, insertion et requêtes de plage toutes rapides, c'est cette famille de structures qu'il te faut, directement ou via ta base de données.

L'article suivant change de famille d'arbres pour une structure spécialisée dans les chaînes de caractères : le trie, ou arbre préfixe.

Sources

• Adelson-Velsky, G., & Landis, E. (1962). An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences. (Arbre AVL)
• Bayer, R. (1972). Symmetric binary B-Trees. Acta Informatica, 1(4). (Origine des arbres rouge-noir)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 13 "Red-Black Trees" et 18 "B-Trees". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 3.3 "Balanced Search Trees". Addison-Wesley.