Arbres binaires de recherche équilibrés

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.

Arbres binaires de recherche

Les arbres binaires de recherche ont été découverts vers la fin des années 1950. Ils sont définis comme suit :

• Arbre binaire : Soit E un ensemble. Un arbre binaire est soit l’arbre vide ∅, soit un nœud A(g, r, d), où g est le sous-arbre gauche, d le sous-arbre droit, et r ∈ E les données stockées dans le nœud.
• Arbre binaire de recherche : Un arbre binaire est dit de recherche si, pour tout nœud x, tous les nœuds y du sous-arbre gauche de x vérifient y < x, et tous les nœuds y du sous-arbre droit de x vérifient x < y.

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.

Rotations

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 :

• Rotation droite
• Rotation gauche

Ces rotations sont essentielles pour rééquilibrer les arbres binaires de recherche.

Arbres AVL

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 :

• Un arbre binaire de recherche est un arbre AVL si, pour chaque nœud, la différence de hauteur entre ses deux fils est au plus égale à 1.

Hauteur d’un arbre AVL

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 :

• A = (√5 + 2) / 5 ≈ 1,89
• α = (1 + √5) / 2 ≈ 1,62
• B = (√5 - 2) / 5 ≈ 0,11
• β = (1 - √5) / 2 ≈ -0,62

On en déduit :

h < logα(n + 1) ≈ (3/2) log2(n + 1).

Rééquilibrage d’un arbre AVL

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.

Arbres rouge-noir

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 :

1. Chaque nœud est soit rouge, soit noir.
2. La racine est noire.
3. Chaque sous-arbre vide est noir.
4. Si un nœud est rouge, alors ses deux enfants sont noirs.
5. Pour chaque nœud, tous les chemins menant à une feuille contiennent le même nombre de nœuds noirs, appelé hauteur noire.

Hauteur d’un arbre rouge-noir

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).

Insertion et suppression dans un arbre rouge-noir

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.

Performances comparées

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.

Test dans un des cas pires

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.

Glossaire des termes clés

• Arbre binaire : Structure de données composée de nœuds, chaque nœud ayant au plus deux enfants.
• Arbre binaire de recherche : Arbre binaire où pour chaque nœud, les valeurs du sous-arbre gauche sont inférieures et celles du sous-arbre droit supérieures.
• Hauteur d’un arbre : Longueur du plus long chemin de la racine à une feuille.
• Rotation : Opération modifiant la structure d’un arbre binaire tout en conservant la propriété d’ordre.
• Arbre AVL : Arbre binaire de recherche équilibré où la différence de hauteur entre sous-arbres gauche et droit est au plus 1.
• Arbre rouge-noir : Arbre binaire de recherche avec des nœuds colorés en rouge ou noir, respectant des propriétés d’équilibre spécifiques.
• Hauteur noire : Nombre de nœuds noirs sur un chemin d’un nœud donné à une feuille dans un arbre rouge-noir.
• Rééquilibrage : Processus de rotations et recolorations pour maintenir l’équilibre d’un arbre après insertion ou suppression.
• τ0, τ1, τ2, τ3 : Temps mesurés pour différentes opérations sur les arbres (insertion/recherche, suppression, etc.).

Points clés à retenir

• Les arbres binaires de recherche permettent un accès rapide aux données grâce à leur organisation ordonnée.
• Les arbres AVL garantissent un équilibre strict avec une différence de hauteur ≤ 1, assurant une hauteur logarithmique.
• Les arbres rouge-noir utilisent une coloration pour équilibrer l’arbre avec des propriétés moins strictes mais efficaces.
• Les rotations sont des opérations fondamentales pour maintenir l’équilibre des arbres.
• Les performances des arbres AVL et rouge-noir sont nettement supérieures aux arbres naïfs, notamment en termes de hauteur et temps d’opérations.
• La hauteur maximale d’un arbre AVL est environ (3/2) log2(n + 1), tandis que celle d’un arbre rouge-noir est au plus 2 log2(n + 1).