8.2 Arbres quadrants de recherche
359
L’expression obtenue ne permettant cependant pas d’en déduire aisément le comportement asymptotique de f n , nous allons utiliser la fonction génératrice de la suite
f ∗
n , que nous écrivons sous la forme f ∗
n =
1
6 (1 − 2/n + 6/(n − 1)) :
f
∗ (u) =
u
1 − u
+ 2 (3u − 1) log
1
1 − u
,
et donc
f (z) = −
z
1 − z
+
2(1 + 2z)
1 − z
log
1
1 − z
.
Nous en tirons aisément, par un lemme de transfert [90] la valeur moyenne de la
longueur de cheminement :
Proposition 8.16 La valeur moyenne de la longueur de cheminement dans un
arbre quadrant de recherche construit sur n clés vérifie asymptotiquement lorsque
n → +∞, dans le cas d = 2
f n = n log n +
γ −
1
6
n + O(log n).
Nous ne détaillons pas ici les calculs permettant de terminer la preuve
de la proposition 8.16, qui se trouvent dans plusieurs articles : Devroye et
Laforest [61], Flajolet et al. [99, 101].
Proposition 8.17
La valeur moyenne de la longueur de cheminement
dans un arbre quadrant de recherche construit sur n clés vérifie asymptotiquement lorsque n → +∞, dans le cas d ≥ 3
f n =
2
d
n log n + μ d n + O(log n + n
−1+2 cos(2π/d) ),
pour une certaine constante μ d ne dépendant que de d.
La preuve de ce résultat se trouve dans l’article [101] : la transformée
d’Euler f ∗ (u) définie par l’équation (8.10) s’exprime comme fonction hypergéométrique, dont il est possible de faire l’étude asymptotique.