Arbres binaires de recherche équilibrés
Arbres binaires de recherche équilibrés
Programmation, Mathématiques, Informatique · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente les arbres binaires de recherche équilibrés, une structure de données fondamentale en informatique. Il s’adresse aux étudiants en informatique ou mathématiques souhaitant comprendre les principes, propriétés et performances des arbres AVL et des arbres rouge-noir, deux variantes courantes d’arbres binaires équilibrés.
Les arbres binaires de recherche ont été découverts vers la fin des années 1950. Ils sont définis comme suit :
La hauteur h d’un arbre binaire non vide avec n nœuds satisfait la propriété :
log2(n + 1) - 1 ≤ h ≤ n - 1
Ces bornes sont optimales.
Les rotations sont des opérations qui permettent de modifier la structure d’un arbre binaire de recherche tout en préservant sa propriété d’ordre. Il existe deux types de rotations :
Ces rotations sont essentielles pour rééquilibrer les arbres binaires de recherche.
Les arbres AVL ont été introduits en 1962 par Adel’son-Vel’ski˘ı et Landis. Ce sont des arbres binaires de recherche équilibrés selon la définition suivante :
Soit un arbre AVL de hauteur h et possédant n nœuds. Alors :
h ≤ (3/2) log2(n + 1)
Cette inégalité est démontrée en considérant la suite uh, le nombre minimal de nœuds d’un arbre AVL de hauteur h, définie par :
u0 = 1, u1 = 2, et ∀h ∈ ℕ, uh+2 = uh + uh+1 + 1.
Après résolution, on obtient :
uh = A α^h + B β^h - 1,
avec :
On en déduit :
h < logα(n + 1) ≈ (3/2) log2(n + 1).
Le rééquilibrage se fait par des rotations simples ou doubles, appliquées lors des insertions ou suppressions pour maintenir la propriété d’équilibre. Par exemple, lors de l’insertion des clés 18, 98, 51, 70 et 62 dans un arbre vide, des rotations sont effectuées pour préserver l’équilibre AVL.
Les arbres rouge-noir ont été inventés par Bayer en 1972 et étudiés en détail par Guibas et Sedgewick en 1978. Ce sont des arbres binaires de recherche avec une coloration des nœuds et des propriétés spécifiques :
Soit un arbre rouge-noir de hauteur h avec n nœuds. On a :
h ≤ 2 log2(n + 1)
La démonstration repose sur un lemme indiquant qu’un sous-arbre de hauteur h et de hauteur noire ω possède au moins 2^ω - 1 nœuds. En appliquant ce lemme, on obtient :
n > 2^(h/2) - 1, d’où h ≤ 2 log2(n + 1).
Les opérations d’insertion et de suppression dans un arbre rouge-noir nécessitent des ajustements de couleur et des rotations pour maintenir les propriétés de l’arbre. Ces opérations sont plus complexes que pour les arbres AVL mais garantissent un bon équilibre.
Par exemple, l’insertion des clés 18, 98, 51, 70 et 62 dans un arbre rouge-noir vide implique plusieurs étapes de recoloration et de rotations pour préserver les propriétés rouge-noir.
Des tests ont été réalisés pour comparer les performances des arbres naïfs, AVL et rouge-noir sur des constructions aléatoires et des cas pires.
| Test | n (nœuds) | h (hauteur) Naïf | h AVL | h Rouge-Noir | τ0 (s) insertion/recherche | τ1 (s) suppression p clés | τ2 (s) insertion p clés | τ3 (s) suppression n clés croissant |
|---|---|---|---|---|---|---|---|---|
| Test 1 | 64 000 | 41 | 18 | 19 | 19,73 / 19,71 / 20,09 | 0,08 / 0,08 / 0,08 | 0,04 / 0,05 / 0,05 | 0,04 / 0,08 / 0,06 |
| Test 2 | 128 000 | 45 | 19 | 20 | 47,02 / 46,03 / 47,05 | 0,20 / 0,20 / 0,20 | 0,13 / 0,14 / 0,14 | 0,07 / 0,17 / 0,13 |
| Test 3 | 256 000 | 42 | 20 | 21 | 109,81 / 107,30 / 108,79 | 0,44 / 0,47 / 0,49 | 0,36 / 0,26 / 0,33 | 0,15 / 0,38 / 0,27 |
Les tests montrent que les arbres AVL et rouge-noir maintiennent une hauteur beaucoup plus faible que les arbres naïfs, ce qui améliore les performances des opérations.
| Algorithme | h | τ0 (s) insertion croissante | τ0 / n log2 n (µs) |
|---|---|---|---|
| Naïf | 31 999 | 614 | 0,9 |
| AVL (1) | 14 | 0,06 | 0,13 |
| AVL (2) | 18 | 1,31 | 0,14 |
| AVL (3) | 20 | 5,51 | 0,14 |
| Rouge-Noir (1) | 26 | 0,08 | 0,17 |
| Rouge-Noir (2) | 34 | 1,79 | 0,19 |
| Rouge-Noir (3) | 38 | 9,76 | 0,24 |
Ces résultats confirment que les arbres AVL et rouge-noir sont plus efficaces que les arbres naïfs, même dans des cas défavorables.