226
6 Arbres binaires de recherche
et en prenant l’espérance (cf. les règles pour l’espérance conditionnelle section C.7)
P(D n+1 = k) = E
U k (τ n )
n + 1
= E(μ τ n (k)).
(6.8)
Cette égalité exprime que des résultats en moyenne sur la mesure μ τ n donnent des
résultats en loi sur la profondeur d’insertion D n+1 . Autrement dit, des résultats en
moyenne sur le profil donnent des résultats en loi sur la profondeur d’insertion.
Définition 6.5 Nous appelons polynôme de niveau d’un arbre binaire de recherche τ n , le polynôme défini formellement par
W τ n (z) :=
+∞
k=0
U k (τ n ) z
k .
Il s’agit bien d’un polynôme, car il n’y a plus de feuilles à profondeur supérieure à la
hauteur : pour k > h(τ n ), nous avons U k (τ n ) = 0. Bien entendu, c’est une variable
aléatoire, puisque les U k (τ n ) sont aléatoires. Pour n = 0 nous avons W τ 0 (z) = 1 ;
et pour z = 1, nous avons pour tout n, W τ n (1) = n + 1, le nombre total de feuilles
de τ n .
Nous obtiendrons facilement la moyenne du polynôme de niveau, dès que nous
aurons la moyenne des U k (τ n ). Cette moyenne fait l’objet du théorème suivant, dû
à Lynch [169] :
Théorème 6.6 La moyenne du nombre de feuilles au niveau k dans un arbre binaire
de recherche aléatoire de taille n, sous le modèle Ord, vaut
E (U k (τ n )) =
2 k
n!
n
k
,
où les nombres
n
k
sont les nombres de Stirling de première espèce (voir la
section B.5.1).
Preuve Nous utilisons le principe « diviser pour régner » de la proposition 6.1.
Posons
a n,k :=
n!
2 k E (U k (τ n )) .
Un petit calcul permet de voir que les a n,k satisfont la relation de récurrence des
nombres de Stirling de première espèce et ont les mêmes valeurs initiales.
Nous déduisons immédiatement du théorème 6.6, avec l’équation (6.8), la loi de
la profondeur d’insertion de la (n + 1)-ième clé dans τ n :
P(D n+1 = k) =
2 k
(n + 1)!
n
k
.