362
8 Arbres m-aires et quadrants
La preuve de ce lemme se fait simplement, en injectant dans la définition de λ n (t)
la relation de récurrence (8.12) sur P(d(X, τ n ) =
En différentiant la relation de récurrence donnée en (8.13), puis en remplaçant
t par 0, et enfin en tenant compte de λ
n (0) = E[d(X, τ n )], nous obtenons une
nouvelle relation de récurrence, cette fois sur les E[d(X, τ i )] :
E[d(X, τ n )] = 1 +
4
n(n − 1)
n−1
i=1
i (H n − H i ) E[d(X, τ i )].
Nous pouvons tout aussi facilement établir une relation de récurrence sur les
E[d(X, τ n ) 2 ] :
E[d(X, τ n )
2
] = 2E[d(X, τ n )] − 1
+
4
n(n − 1)
n−1
i=1
i (H n − H i ) E[d(X, τ i )
2
].
Remarquons que ces deux relations de récurrence sont très similaires ; le lemme
suivant, dont la démonstration est laissée au lecteur, permettra d’obtenir les
expressions de la moyenne et de la variance de d(X, τ n ).
Lemme 8.19 Soit la récurrence
u n = a n +
4
n(n − 1)
n−1
i=1
i (H n − H i ) u i
(n ≥ 3)
avec les conditions initiales u 1 = 0, u 2 = a 2 et (a n ) n≥2 une suite de réels. Alors,
pour n ≥ 3,
u n = a n + 4
n
j =3
1
j 2 (j − 1) 2 (j − 2)
j −1
i=1
i
2 (i − 1)a i .
Après quelques simplifications, nous obtenons le théorème suivant.
Théorème 8.20 La moyenne et la variance de la profondeur d’insertion d’une
clé X dans un arbre quadrant de recherche à n clés, de paramètre d = 2, sont
données par
E [d(X, τ n )] = H n −
1
6
−
2
3n
∼ log n;
Var (d(X, τ n )) =
1
2
H n + H
(2)
n −
13
6
+
5
9n
−
4
9n 2 ∼
1
2
log n,
où H
(2)
n =
1≤p≤n
1
p 2 .