Arbres rouge-noir
Un arbre rouge-noir est un arbre binaire de recherche qui se rééquilibre tout seul. Grâce à quelques règles de couleur, sa hauteur reste toujours en O(log n), peu importe l'ordre d'insertion.
Pourquoi un arbre auto-équilibré ?
Dans un arbre binaire de recherche (ABR) ordinaire, insérer 1, 2, 3, 4, 5 dans cet ordre donne une « liste chaînée » : chaque noeud n'a qu'un enfant à droite. La recherche devient alors O(n). L'arbre rouge-noir empêche ce cas en corrigeant la forme de l'arbre après chaque insertion et chaque suppression.
Les propriétés
- C'est un arbre binaire de recherche.
- Chaque noeud est rouge ou noir.
- La racine est toujours noire.
- Les pointeurs NULL (les feuilles vides) comptent comme des noeuds noirs.
- Un noeud rouge a forcément deux enfants noirs : il n'y a jamais deux rouges de suite.
- Depuis n'importe quel noeud, tous les chemins vers un NULL contiennent le même nombre de noeuds noirs (la hauteur noire).
Ensemble, ces règles garantissent que la hauteur ne dépasse jamais 2 · log₂(n + 1). Le chemin le plus long (rouge, noir, rouge, noir…) fait au plus le double du plus court (tout noir).
Les rotations
Une rotation réorganise trois noeuds sans briser l'ordre de l'ABR. Elle fait monter un enfant et descendre son parent.
Une rotation ne touche que trois pointeurs : elle s'exécute en O(1).
Insertion
On insère d'abord comme dans un ABR, puis on colore le nouveau noeud en rouge. Un noeud rouge ne change pas la hauteur noire ; le seul problème possible est d'avoir deux rouges de suite. On regarde alors le parent et l'oncle (le frère du parent).
| Situation | Correction |
|---|---|
| Cas #1 : parent noir | Rien à faire. |
| Cas #2 : parent rouge, oncle noir, en ligne droite | Parent → noir, grand-parent → rouge, puis rotation du grand-parent vers le côté opposé à la ligne. Terminé. |
| Cas #2b : parent rouge, oncle noir, en zig-zag | Rotation du parent pour obtenir une ligne droite ; l'ancien parent devient le nouveau noeud, puis on applique le cas #2. |
| Cas #3 : parent rouge, oncle rouge | Parent et oncle → noirs, grand-parent → rouge. On recommence à partir du grand-parent. |
Si la racine devient rouge à la fin (après un cas #3), on la recolore en noir.
Exemple : insérer 10, 20, 30, 15, 12
- 10 devient la racine, noire.
- 20 : son parent 10 est noir → cas #1.
- 30 : parent 20 rouge, oncle NULL (noir), et 10 → 20 → 30 forme une ligne vers la droite → cas #2. 20 devient noir, 10 devient rouge, rotation gauche sur 10. Résultat : 20 (noir) avec 10 et 30 (rouges).
- 15 : parent 10 rouge, oncle 30 rouge → cas #3. 10 et 30 deviennent noirs, 20 devient rouge, puis 20 redevient noir puisque c'est la racine.
- 12 : parent 15 rouge, oncle NULL noir, et 10 → droite → gauche forme un zig-zag → cas #2b. Rotation droite sur 15, puis cas #2 : 12 devient noir, 10 devient rouge, rotation gauche sur 10.
Un NULL compte comme un noeud noir. Un oncle absent signifie donc toujours un cas #2 ou #2b.
Suppression
Supprimer un noeud rouge ne pose jamais problème. Supprimer un noeud noir retire un noir d'un chemin : on marque alors l'endroit comme double noir, un noeud qui « compte pour deux », puis on élimine ce double noir.
Règles de base
- Règle #1 : le noeud est une feuille rouge → on l'enlève.
- Règle #2 : le noeud a un seul enfant → l'enfant (forcément rouge) prend sa place et devient noir.
- Règle #3 : le noeud a deux enfants → on copie la valeur de son prédécesseur (le maximum du sous-arbre gauche), puis on supprime le prédécesseur avec la règle qui s'applique à lui.
- Règle #4 : le noeud est une feuille noire → on le remplace par un NULL double noir.
Éliminer le double noir
On regarde le frère du double noir, puis les enfants du frère. Pour ne pas se tromper de côté, on parle de l'enfant éloigné (du côté opposé au double noir) et de l'enfant proche.
| Cas | Situation | Correction |
|---|---|---|
| 4.1 | Frère rouge | Frère → noir, parent → rouge, rotation du parent vers le double noir. Ne termine pas : on revérifie avec le nouveau frère. |
| 4.2 | Frère noir, ses deux enfants noirs | Frère → rouge. Si le parent était rouge, il devient noir et c'est fini ; sinon il devient double noir et on continue à partir de lui. |
| 4.3 | Frère noir, enfant proche rouge, enfant éloigné noir | Frère → rouge, enfant proche → noir, rotation du frère vers l'extérieur. Ne termine pas : mène au cas 4.4. |
| 4.4 | Frère noir, enfant éloigné rouge | Enfant éloigné → noir, frère → couleur du parent, parent → noir, rotation du parent vers le double noir. Terminé. |
Pièges fréquents
Successeur ou prédécesseur ? Plusieurs cours utilisent le successeur pour la règle #3. Ici, on prend le prédécesseur. Les deux sont valides, mais ils mènent à des cas différents : vérifie la convention de ton cours.
Les cas 4.1 et 4.3 ne terminent jamais. Après eux, il faut obligatoirement appliquer un autre cas.
Ordre des opérations. Dans un cas avec rotation, on change d'abord les couleurs, puis on fait la rotation. Faire l'inverse donne le même arbre final, mais rend le raisonnement plus difficile à suivre.
Si l'enfant éloigné est rouge, c'est le cas 4.4, même si l'enfant proche est rouge lui aussi.
Complexité
| Opération | Pire cas |
|---|---|
| Recherche | O(log n) |
| Insertion | O(log n), au plus 2 rotations |
| Suppression | O(log n), au plus 3 rotations |
En Java, TreeMap et TreeSet sont implémentés avec un arbre rouge-noir ; en C++, c'est le cas de std::map dans la plupart des bibliothèques.