8.2 Arbres quadrants de recherche
361
Conditionnons par la taille du sous-arbre τ
(j )
n et par le fait que la clé X soit insérée
dans ce sous-arbre :
P
d(X, τ n ) = , X ∈ τ
(j )
n
=
n−1
i=0
P
d(X, τ
(j )
n ) = − 1
X ∈ τ
(j )
n , |τ
(j )
n | = i
P
X ∈ τ
(j )
n
|τ
(j )
n | = i
P
τ
(j )
n
= i
.
Sachant les tailles des sous-arbres, la clé X se trouve dans le sous-arbre τ
(j )
n avec
probabilité
P(X ∈ τ
(j )
n
∀i = 0, 1, 2, 3, |τ
(i)
n | = n i ) =
|τ
(j )
n |
|τ
(0)
n | + |τ
(1)
n | + |τ
(2]
n | + |τ
[3)
n |
=
n j
n − 1
,
donc P
X ∈ τ
(j )
n
|τ
(j )
n | = i
=
i
n − 1
. En outre, nous utilisons la valeur de
P
τ
(j )
n
= i
obtenue pour le cas d = 2 (cf. la propriété 8.13.iv) : P
τ
(j )
n
= i
=
1
n
(H n − H i ). Enfin, par la proposition 8.12, la loi de τ
(j )
n sachant les tailles de sousarbres est celle d’un arbre de taille i, donc
P
d(X, τ
(j )
n ) = − 1
X ∈ τ
(j )
n , |τ
(j )
n | = i
= P (d(X, τ i ) = − 1) .
Finalement
P
d(X, τ n ) = , X ∈ τ
(j )
n
=
n−1
i=0
P (d(X, τ i ) = − 1)
i
n(n − 1)
(H n − H i )
et ne dépend pas de j . Donc
P (d(X, τ n ) = ) =
4
n(n − 1)
n−1
i=0
i(H n − H i )P (d(X, τ i ) = − 1) .
(8.12)
Fonction génératrice des moments de d(X, τ n )
Lemme 8.18 Soit λ n (t) = E[e td(X,τ n ) ] =
P(d(X, τ n ) = )e
t la fonction
génératrice des moments de d(X, τ n ). Elle satisfait la relation de récurrence
λ n (t) =
4e t
n(n − 1)
.
n−1
i=1
i (H n − H i ) λ i (t).
(8.13)