222
6 Arbres binaires de recherche
La démarche habituelle consiste à trouver une équation de récurrence sur les
probabilités P(lci(τ n ) = k) et à en déduire une équation fonctionnelle sur F . Soit
k ≥ 0. En conditionnant sur la taille de τ
(g)
n , nous avons pour n ≥ 1
P(lci(τ n ) = k) =
n−1
p=0
P
lci(τ n ) = k
|τ
(g)
n | = p
P
|τ
(g)
n | = p
,
puis grâce à la proposition 6.1 et avec l’équation (6.1)
P(lci(τ n ) = k) =
1
n
n−1
p=0
P
lci(τ
(g)
n ) + lci(τ
(d)
n ) + n − 1 = k
|τ
(g)
n | = p
=
1
n
n−1
p=0
k 1 +k 2 +n−1=k
P
lci(τ p ) = k 1
P
lci(τ n−1−p ) = k 2
.
Alors, F satisfait l’équation intégro-fonctionnelle suivante
∂F
∂x
(x, y) = F
2 (xy, y) .
(6.2)
Cette équation donne des informations sur la loi de lci(τ n ), en étudiant les fonctions
génératrices des moments de lci(τ n ) (cf. la section 4.1.2 et l’annexe B.3.2 pour
les relations explicites entre fonctions génératrices et moments). Faisons-le pour
l’espérance (les calculs sont plus lourds pour la variance), ce qui fournit une
méthode alternative à l’analyse en moyenne ci-dessus.
Appelons B la fonction génératrice de la moyenne de lci(τ n ) :
B(x) :=
n≥0
E(lci(τ n )) x
n .
Alors
B(x) =
∂F
∂y
(x, y) | y=1 .
En dérivant par rapport à x et grâce à l’équation (6.2), il vient
B
(x) =
∂
∂y
F
2 (xy, y) | y=1
= 2xF
3 (x, 1) + 2F (x, 1)B(x).