8.2 Arbres quadrants de recherche
365
devient une variable aléatoire et U p (τ n ), le nombre de feuilles au niveau p, est aussi
une variable aléatoire. Par conséquent,
E
W τ n (z)
=
p≥0
E
U p (τ n )
z
p .
Lemme 8.24 L’espérance E
W τ n (z)
du polynôme de niveaux satisfait la récurrence suivante :
E
W τ n (z)
= 2
d z
n−1
p=0
π n,p E
W τ p (z)
,
(8.15)
où π n,p est la probabilité qu’un sous-arbre quelconque de la racine d’un arbre de
taille n soit lui-même de taille p, et est donnée par la proposition 8.15.
Preuve Par la relation (8.14),
E
W τ n (z)
= z
2 d −1
i=0
E
W τ
(i)
n
(z)
.
Soit i ∈ {0, . . . , 2 d − 1} fixé. En conditionnant par les tailles des sous-arbres,
E
W τ
(i)
n
(z)
= E
E(W τ
(i)
n
(z)
∀j, |τ
(j )
n | = n j )
=
n−1
p=0
E
E(W τ
(i)
n
(z)1 {|τ
(i)
n |=p}
∀j, |τ
(j )
n | = n j )
,
la dernière égalité venant de la distinction entre les différentes tailles possibles du
sous-arbre τ
(i)
n . Par la proposition 8.12, la loi de τ
(i)
n sachant les tailles des sousarbres est celle d’un arbre de taille p, donc
E
W τ
(i)
n
(z)
=
n−1
p=0
E(W τ p (z))P(|τ
(i)
n | = p) =
n−1
p=0
E(W τ p (z))π n,p ,
qui ne dépend pas de i. Finalement, nous obtenons bien (8.15).
Nous donnons quelques indications sur la fonction génératrice univariée de
la profondeur d’insertion dans l’exercice 8.11, mais c’est la fonction génératrice
bivariée, dont nous entamons maintenant l’étude, qui va permettre d’établir la
normalité asymptotique de cette variable aléatoire.