backend / algorithmes-structures-donnees
Arbres équilibrés : AVL et rouge-noir
Explication
Ce que vous allez apprendre
- Expliquer pourquoi un BST classique ne garantit pas O(log n) et ce qu'ajoute un arbre équilibré
- Formuler la règle d'équilibre d'un AVL (différence de hauteur ≤ 1) et celle, plus souple, d'un arbre rouge-noir
- Décrire ce qu'est une rotation et pourquoi elle rééquilibre l'arbre sans le retrier entièrement
- Comparer AVL et rouge-noir selon le compromis lecture rapide / écriture rapide
- Relier ces structures à leur usage réel (
TreeMapen Java,std::mapen C++, index de bases de données)
Dans quel contexte ?
Une base de données doit maintenir un index trié qui reste rapide à interroger même après des millions d'insertions et de suppressions dans un ordre imprévisible. Un BST naïf finirait par se déséquilibrer et dégrader les performances de l'index vers O(n). C'est exactement pour cette raison que la plupart des implémentations de TreeMap (Java) ou std::map (C++) utilisent en interne un arbre rouge-noir : il garantit une hauteur en O(log n) quel que soit l'historique des opérations, sans jamais nécessiter de reconstruction complète.
D'abord, le problème laissé ouvert par la leçon précédente
Un BST classique n'offre O(log n) que "si on a de la chance" sur l'ordre d'insertion : dans le pire cas, il dégénère en liste chaînée. Les arbres équilibrés suppriment cette dépendance au hasard en imposant activement une contrainte de forme après chaque modification.
Prérequis
Cette leçon prolonge directement la précédente sur les BST : assurez-vous de bien comprendre pourquoi un BST peut dégénérer en O(n) avant d'aborder les rotations ci-dessous.
Étape 1 : la règle imposée par l'AVL
Un AVL exige qu'à chaque noeud, la différence de hauteur entre le sous-arbre gauche et le sous-arbre droit ne dépasse jamais 1. C'est une contrainte stricte, vérifiée partout dans l'arbre, pas seulement à la racine.
Étape 2 : comment cette règle est maintenue après chaque insertion
Après chaque ajout, on remonte le chemin parcouru et on vérifie ce facteur d'équilibre à chaque noeud traversé. Dès qu'il est violé quelque part, une opération appelée rotation corrige le déséquilibre localement.
Ce qu'est réellement une rotation
Une rotation réorganise seulement trois noeuds et leurs sous-arbres, en préservant scrupuleusement l'ordre relatif de toutes les valeurs impliquées. C'est ce qui permet de rééquilibrer l'arbre sans jamais avoir à le retrier ou à le reconstruire entièrement.
Un détail à connaître, sans s'y noyer
Il existe quatre configurations de déséquilibre possibles (gauche-gauche, droite-droite, et deux variantes en zigzag), chacune se résolvant par une ou deux rotations combinées.
Étape 3 : une alternative plus souple, l'arbre rouge-noir
Un arbre rouge-noir tolère un déséquilibre plus lâche, encodé par une coloration rouge ou noir de chaque noeud et quatre règles précises à respecter. Cela demande moins de rotations lors des insertions et suppressions, au prix d'une hauteur légèrement plus grande qu'un AVL.
Pourquoi ce compromis existe
Un AVL, plus strictement équilibré, favorise des recherches très rapides. Un rouge-noir, moins strict, favorise des écritures plus rapides. C'est ce compromis qui explique pourquoi les bases de données et les bibliothèques standard préfèrent souvent le rouge-noir.
| Critère | AVL | Rouge-noir |
|---|---|---|
| Contrainte d'équilibre | Stricte (différence de hauteur ≤ 1) | Plus souple (coloration + 4 règles) |
| Recherche | Très rapide (arbre plus "plat") | Rapide |
| Insertion / suppression | Plus de rotations | Moins de rotations |
| Usage typique | Lectures dominantes | Écritures fréquentes (bases de données, bibliothèques standard) |
Astuce
Retenez le compromis en une phrase : l'AVL est optimisé pour lire, le rouge-noir est optimisé pour écrire. En cas de doute sur votre cas d'usage, le rouge-noir reste le choix par défaut le plus répandu dans les bibliothèques standard.
Vers la suite
Ces arbres garantissent un ordre total sur toutes les valeurs. La prochaine leçon présente une structure qui, elle, se contente délibérément d'une garantie plus faible mais suffisante : le tas, pour connaître rapidement seulement le minimum ou le maximum.
Commandes & code
Arbres équilibrés : AVL et rouge-noir
# --- Arbre AVL : maintient |hauteur(gauche) - hauteur(droite)| <= 1 à CHAQUE noeud ---
class NoeudAVL:
def __init__(self, valeur):
self.valeur = valeur
self.gauche: "NoeudAVL | None" = None
self.droite: "NoeudAVL | None" = None
self.hauteur = 1 # hauteur d'une feuille seule = 1 dans cette convention
def _hauteur(noeud: NoeudAVL | None) -> int:
return noeud.hauteur if noeud else 0
def _facteur_equilibre(noeud: NoeudAVL | None) -> int:
return _hauteur(noeud.gauche) - _hauteur(noeud.droite) if noeud else 0
def _maj_hauteur(noeud: NoeudAVL) -> None:
noeud.hauteur = 1 + max(_hauteur(noeud.gauche), _hauteur(noeud.droite))
def _rotation_droite(y: NoeudAVL) -> NoeudAVL:
# Rotation qui corrige un déséquilibre gauche-gauche
x = y.gauche
t2 = x.droite
x.droite = y
y.gauche = t2
_maj_hauteur(y)
_maj_hauteur(x)
return x # x devient la nouvelle racine de ce sous-arbre
def _rotation_gauche(x: NoeudAVL) -> NoeudAVL:
# Rotation qui corrige un déséquilibre droite-droite
y = x.droite
t2 = y.gauche
y.gauche = x
x.droite = t2
_maj_hauteur(x)
_maj_hauteur(y)
return y
def inserer_avl(noeud: NoeudAVL | None, valeur) -> NoeudAVL:
# 1. Insertion BST classique
if noeud is None:
return NoeudAVL(valeur)
if valeur < noeud.valeur:
noeud.gauche = inserer_avl(noeud.gauche, valeur)
elif valeur > noeud.valeur:
noeud.droite = inserer_avl(noeud.droite, valeur)
else:
return noeud # doublon ignoré
# 2. Mise à jour de la hauteur du noeud courant
_maj_hauteur(noeud)
# 3. Calcul du facteur d'équilibre et rééquilibrage si nécessaire (4 cas classiques)
equilibre = _facteur_equilibre(noeud)
if equilibre > 1 and valeur < noeud.gauche.valeur: # cas Gauche-Gauche
return _rotation_droite(noeud)
if equilibre < -1 and valeur > noeud.droite.valeur: # cas Droite-Droite
return _rotation_gauche(noeud)
if equilibre > 1 and valeur > noeud.gauche.valeur: # cas Gauche-Droite
noeud.gauche = _rotation_gauche(noeud.gauche)
return _rotation_droite(noeud)
if equilibre < -1 and valeur < noeud.droite.valeur: # cas Droite-Gauche
noeud.droite = _rotation_droite(noeud.droite)
return _rotation_gauche(noeud)
return noeud # déjà équilibré
def parcours_infixe_avl(noeud: NoeudAVL | None, resultat: list | None = None) -> list:
if resultat is None:
resultat = []
if noeud is not None:
parcours_infixe_avl(noeud.gauche, resultat)
resultat.append(noeud.valeur)
parcours_infixe_avl(noeud.droite, resultat)
return resultat
# Démonstration : insérer dans l'ordre 10, 20, 30 déclenche une rotation gauche automatique
racine_avl = None
for v in [10, 20, 30, 40, 50, 25]:
racine_avl = inserer_avl(racine_avl, v)
assert parcours_infixe_avl(racine_avl) == [10, 20, 25, 30, 40, 50]
assert _hauteur(racine_avl) <= 1.45 * 2.9 # reste proche de log2(6) grâce au rééquilibrage
# --- Arbre rouge-noir : concepts (implémentation complète très longue, principes clés) ---
# Invariants d'un arbre rouge-noir :
# 1. Chaque noeud est ROUGE ou NOIR.
# 2. La racine est toujours NOIRE.
# 3. Un noeud ROUGE ne peut pas avoir d'enfant ROUGE (pas de rouge-rouge consécutif).
# 4. Tout chemin d'un noeud vers ses feuilles NIL contient le MÊME nombre de noeuds NOIRS.
# 5. Ces règles garantissent une hauteur <= 2*log2(n+1) -- rééquilibrage par recoloration + rotations.
#
# Différence pratique AVL vs rouge-noir :
# - AVL : plus strictement équilibré -> recherches plus rapides, mais plus de rotations à l'insertion.
# - Rouge-noir : moins strict -> insertions/suppressions plus rapides, recherche légèrement moins rapide.
# - En pratique : TreeMap (Java), std::map (C++), et de nombreuses bases de données utilisent rouge-noir
# pour son meilleur compromis en écriture ; les BST équilibrés de bibliothèques scientifiques utilisent AVL
# quand la lecture domine largement l'écriture.Résumé
- Un AVL rééquilibre après CHAQUE insertion via des rotations simples ou doubles, garantissant O(log n) strict.
- Le facteur d'équilibre (différence de hauteur gauche/droite) déclenche 4 cas de rotation : Gauche-Gauche, Droite-Droite, Gauche-Droite, Droite-Gauche.
- Un arbre rouge-noir tolère un déséquilibre plus lâche (règles de coloration) pour un coût de rééquilibrage moindre en écriture.
- Ces structures existent car un BST naïf peut dégénérer en O(n) : elles garantissent O(log n) dans tous les cas.
Exercices pratiques
Mission : choisir la bonne structure d'index pour une base de données
Objectif : Tracer une rotation AVL et argumenter le choix entre AVL et rouge-noir selon le profil de charge.
Contexte
L'équipe infrastructure doit choisir la structure d'arbre équilibré pour un nouvel index de base de données qui subira beaucoup plus d'écritures (insertions de commandes) que de lectures (recherches ponctuelles). Un stagiaire propose un AVL "parce que c'est le plus strict, donc le meilleur". Tu dois vérifier ce raisonnement à la main puis trancher.