Les arbres binaires de
recherche équilibrés
– Introduction
– Arbres binaires de recherche
– Arbres AVL
– Arbres rouge-noir
– Performances
– Conclusion
Arbres binaires de recherche
Découverts vers la fin des années 1950.
Définition 1 (Arbre binaire). Soit E un en-
semble. Un arbre binaire est :
– soit l’arbre vide ∅ ;
– soit un nœud A(g, r, d), où g désigne le
sous-arbre gauche, d le sous-arbre droit, et
r ∈ E les données satellites stockées dans
le nœud.
Définition 2 (Arbre binaire de recherche).
Un arbre binaire est de recherche lorsque, si
x est un nœud de l’arbre, et y un nœud du
sous-arbre gauche (resp. droit) de x, on a
y < x (resp. x < y).
Exemples d’arbres binaires de
recherche
Hauteur d’un arbre binaire
Proposition 1. Soit un arbre binaire non vide
de hauteur h et possédant n nœuds. On a :
blog2 nc 6 h 6 n − 1.
Ces bornes sont optimales.
18103151411164223322759781898517062Rotations
Proposition 2. Les rotations préservent la
propriété d’arbre binaire de recherche.
DEBCABDECArotation droiterotation gaucheArbres AVL
Introduits pour la première fois par Adel’son-
Vel’ski˘ı et Landis en 1962.
Définition 3. Un arbre binaire de recherche
est un arbre AVL si, pour n’importe lequel de
ses nœuds, la différence de hauteur entre ses
deux fils diffère d’au plus un.
Exemples d’arbres AVL
Hauteur d’un arbre AVL
Proposition 3. Soit un arbre AVL de hauteur
h et possédant n nœuds. On a :
h 6
3
2
log2(n + 1).
18141031115164227233259785118706298Hauteur d’un arbre AVL
Démonstration. Soit uh le nombre minimal de nœuds
d’un arbre de hauteur h > 0. On a u0 = 1, u1 = 2, et :
∀h ∈ N,
uh+2 = uh + uh+1 + 1.
Soit, après résolution :
uh = Aαh + Bβh − 1,
avec :
A =
√
5 + 2
5
√
α =
1 +
2
On a donc :
5
≈ 1, 89,
B =
5
≈ 0, 11,
5
≈ 1, 62,
Publicité
β =
5
≈ −0, 62.
√
5 − 2
5
√
1 −
2
n > uh > Aαh − 2,
n + 2 > Aαh,
h < logα(n + 1) + logα
h < logα(n + 1) =
3
2
L’inégalité est vraie pour h = −1.
log2(n + 1).
h <
(cid:18) 1
A
·
n + 2
n + 1
(cid:19)
,
log2(n + 1),
ln 2
ln α
Rééquilibrage d’un arbre AVL
DEBCABDECAhh-1h-3h-2h-2-ph-ph-2h-1-ph-2-ph-3FGBDECAFGDEBCADFGEBCAhh-1h-3h-3h-2h-3-ph-3-qhh-1h-3h-2h-3-qh-3h-3-ph-1h-2h-2h-3h-3-ph-3-qh-3Exemple de construction d’un
arbre AVL
Détail de l’insertion de 18, 98, 51, 70 et 62
dans un arbre vide.
1818981898511851985118985118987051189870625118706298Arbres rouge-noir
Inventés par Bayer en 1972. Étudiés en détail
par Guibas et Sedgewick en 1978.
Définition 4. Un arbre binaire de recherche
est un arbre rouge-noir s’il vérifie les proprié-
tés suivantes :
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 en-
fants sont noirs ;
5. pour chaque nœud, tous les chemins re-
liant le nœud à une feuille contiennent le
même nombre de nœuds noirs (ce nombre
est appelé hauteur noire).
Exemples d’arbres rouge-noir
Hauteur d’un arbre rouge-noir
Proposition 4. Soit un arbre rouge-noir de
hauteur h et possédant n nœuds. On a :
h 6 2 log2(n + 1).
18103151411164227233259785118706298Hauteur d’un arbre rouge-noir
Démonstration. Lemme : un sous-arbre de hauteur h
et de hauteur noire ω possède au moins 2ω − 1 nœuds.
Pour h = −1 ou h = 0, c’est évident.
Soit A(g, r, d) un arbre rouge-noir de hauteur h + 1.
Alors ω(g) > ω − 1, et ω(d) > ω − 1. On a alors :
n > (cid:0)2ω−1 − 1(cid:1) + (cid:0)2ω−1 − 1(cid:1) + 1,
> 2ω − 1.
Le lemme est ainsi démontré au rang h + 1.
Un arbre rouge-noir non vide vérifie ω > h/2. En ap-
pliquant le lemme, il vient : n > 2h/2 − 1, d’où :
h 6 2 log2(n + 1).
L’inégalité est vraie pour n = 0.
Insertion dans un arbre
rouge-noir
DEBCADEBCAyzxx’FGBDECAFGDEBCADFGEBCAyzxyzx’Suppression d’un arbre
rouge-noir
BDECADEBCAyzxy’z’x’BDECABDECAyzxx’BFGDECABDFGECADFGEBCAyzxyz’xExemple de construction d’un
Publicité
arbre rouge-noir
Détail de l’insertion de 18, 98, 51, 70 et 62
dans un arbre vide.
1818189818985118519851189851189870511898705118987051189870625118706298Arbres construits
aléatoirement
Algorithme Test
Naïf
AVL
Rouge-Noir
Naïf
AVL
Rouge-Noir
Naïf
AVL
Rouge-Noir
1
1
1
2
2
2
3
3
3
h
41
18
19
45
19
20
42
20
21
τ0 (s)
19,73
19,71
20,09
47,02
46,03
47,05
109,81
107,30
108,79
τ1 (s)
0,08
0,08
0,08
0,20
0,20
0,20
0,44
0,47
0,49
τ2 (s)
0,04
0,05
0,05
0,13
0,14
0,14
0,36
0,26
0,33
τ3 (s)
0,04
0,08
0,06
0,07
0,17
0,13
Publicité
0,15
0,38
0,27
Test 1 : m = 1 000 000, n = 64 000 et p = 4 000
Test 2 : m = 2 000 000, n = 128 000 et p = 8 000
Test 3 : m = 4 000 000, n = 256 000 et p = 16 000
n : nombre de nœuds de l’arbre
h : hauteur de l’arbre
τ0 : insertion/recherche de m clés aléatoires
τ1 : suppression de p clés aléatoires
τ2 : insertion de p clés aléatoires
τ3 : suppression des n clés dans l’ordre croissant
Test d’un des cas les pires
Algorithme Test
h
Naïf
AVL
AVL
AVL
Rouge-Noir
Rouge-Noir
Rouge-Noir
1
1
2
3
1
2
3
31 999
14
18
20
26
34
38
h
log2 n
2 138
τ0 (s)
614
τ0
n log2 n
1 383
(µs)
0,9
0,9
1,0
1,7
1,8
1,8
0,06
1,31
5,51
0,08
1,79
9,76
0,13
0,14
0,14
0,17
0,19
0,24
Test 1 : n = 32 000
Test 2 : n = 512 000
Test 3 : n = 2 000 000
n : nombre de nœuds de l’arbre
h : hauteur de l’arbre
τ0 : insertion des n clés dans l’ordre croissant