6.1 Analyses de la longueur de cheminement et du profil
227
Le théorème 6.6 permet aussi de calculer la moyenne du polynôme de niveau :
E
W τ n (z)
=
+∞
k=0
E (U k (τ n )) z
k
=
1
n!
+∞
k=0
2
k z
k
n
k
=
1
n!
2z(2z + 1) . . . (2z + n − 1),
en connaissant la fonction génératrice des nombres de Stirling de première espèce
(voir section B.5.1). Ceci permet d’expliciter la loi de la profondeur d’insertion de
la (n + 1)-ième clé dans τ n exprimée par sa série génératrice d n (z) :
d n (z) :=
+∞
k=0
P (D n+1 = k) z
k .
Par l’équation (6.8), P(D n+1 = k) =
1
n + 1
E (U k (τ n )), et nous obtenons
d n (z) =
1
n + 1
E
W τ n (z)
=
1
(n + 1)!
n−1
j =0
(j + 2z),
ce qui est une expression explicite de la série génératrice de la profondeur
d’insertion. Finalement nous avons la proposition suivante, qui permet notamment
de retrouver le résultat du théorème 6.2.
Proposition 6.7 La loi de D n+1 , la profondeur d’insertion d’une clé dans un
arbre binaire de recherche de taille n sous la loi Ord, est donnée par sa fonction
génératrice
d n (z) :=
+∞
k=0
P (D n+1 = k) z
k
=
1
(n + 1)!
n−1
j =0
(j + 2z).
Après avoir exploité les résultats en moyenne sur le profil, utilisons maintenant
la loi conditionnelle de la profondeur d’insertion donnée dans l’équation (6.7) : cela
permet de calculer l’espérance conditionnelle du polynôme de niveau sachant τ n .
En effet, et c’est visible sur la figure 6.4, reprise de la figure 6.2 : lorsque l’arbre
pousse de τ n à τ n+1 par insertion d’une clé x, nous enlevons une feuille du niveau
k en insérant au niveau k et nous gagnons deux feuilles au niveau k en insérant au