220
6 Arbres binaires de recherche
Le principe « diviser pour régner » permet d’obtenir une relation de récurrence
sur la variable qui nous intéresse. Ce principe est posé dans la proposition 2.13 de
la section 2.2.3. Rappelons-le :
Proposition 6.1 Soient τ
(g)
n et τ
(d)
n les sous-arbres respectivement gauche et droit
d’un abr τ n de taille n. Soit p ∈ {0, . . . , n − 1}. Alors P
|τ
(g)
n | = p
=
1
n et,
conditionnellement en la taille de τ
(g)
n égale p, les sous-arbres τ
(g)
n et τ
(d)
n sont
indépendants, τ
(g)
n a même loi que τ p et τ
(d)
n a même loi que τ n−1−p .
Analyse en moyenne de la longueur de cheminement interne et de la profondeur
d’insertion
Soit p ∈ {0, . . . , n − 1}. En conditionnant sur la taille du sous-arbre gauche τ
(g)
n ,
E(lci(τ n )) =
n−1
p=0
E
lci(τ n )
|τ
(g)
n | = p
P(|τ
(g)
n | = p).
En utilisant la proposition 6.1 et l’équation (6.1), nous obtenons
E (lci(τ n )) = n − 1 +
1
n
n−1
p=0
E(lci(τ p ) + E(lci(τ n−1−p )
.
Posons a n = E (lci(τ n )), pour écrire
a n = n − 1 +
2
n
n−1
p=0
a p
puis n(a n − n + 1) − (n − 1)(a n−1 − n + 2) = 2a n−1 , ce qui donne na n = (n +
1)a n−1 + 2(n − 1) et en divisant par n(n + 1) :
a n
n + 1
=
a n−1
n
+ 2
n − 1
n(n + 1)
,
et finalement
E (lci(τ n )) = 2(n + 1)(H n+1 − 1) − 2n = 2(n + 1)H n − 4n,
où le nombre harmonique H n désigne la somme des inverses des n premiers entiers.
Avec le développement asymptotique de H n (cf. section B.5.1), cela montre que
l’espérance du coût de construction d’un abr τ n est asymptotiquement équivalente à
2n log n.
En termes de profondeur d’insertion : nous avons noté d(x, τ n ) la profondeur
d’insertion d’une clé x dans τ n . Sur la figure 6.2, la clé x = 0, 6 est insérée à
profondeur d(x, τ n ) = 3. Dans le modèle Ord des « permutations uniformes »,