8.3 Exercices et problèmes
371
1. Montrer que le nombre moyen de pages vaut γ b n + O(log n), où
γ b = 9
1
0
(1 − t) 3
t (1 + 2t) 2 dt
t
0
1 + 2v
(1 − v) 2 E b (v)dv,
avec
E b (z) = z
b
1
(1 − z) 2 +
b
1 − z
+ b(b + 1)
.
2. Calculer les valeurs de γ b pour b = 0, 1, 2. Montrer que, lorsque b → +∞, γ b = 3/b +
O(1/b 2 ).
3. En prenant b = 1, montrer que la proportion de feuilles dans un arbre quadrant de recherche
non paginé vaut asymptotiquement (i.e. pour un nombre de clés n tendant vers l’infini) 4π 2 −
39 + O(1/n) = 0.4784 · · · + O(1/n).
4. Montrer que le nombre de pages avec j clés, 0 ≤ j ≤ b, vaut asymptotiquement γ b,j n, avec
γ b,j =
γ b
b + 1
+
2
3
.
3bγ b + 2γ b − 6
b(b + 1)
(H b+1 − H j − 1).
(Voir l’article de Flajolet et Hoshi [84].)
Problème 8.11. (Fonction génératrice de la profondeur d’insertion) Soient respectivement
d(X, τ n ) et U p (τ n ) la profondeur d’insertion de la clé X, et le nombre de feuilles à profondeur p,
dans un arbre aléatoire τ n .
1. Relier la valeur prise par d(X, τ n ) à l’expression de U p (τ n+1 ) en fonction de U p (τ n ).
2. Établir la relation de récurrence sur les variables aléatoires U p (τ n ) :
U p (τ n+1 ) = U p (τ n ) + 2
d 1 {d(X,τn)=p−1} − 1 {d(X,τn)=p} .
3. En déduire que
E[W τ n+1 (z)] = E[W τn (z)] + (2
d z − 1)E
z
d(X,τn)
p.s.
4. Soit δ n (z) =
p d n,p z p = E(z d(X,τn) ) la fonction génératrice de probabilités de d(X, τ n ),
avec d n,p = P(d(X, τ n ) = p). Elle est reliée à la fonction génératrice des moments par la
relation δ n (e t ) = λ n (t). Montrer que δ n s’exprime en fonction des espérances des polynômes
de niveaux :
δ n (z) =
1
2 d z − 1
E[W τ n+1 (z)] − E[W τn (z)]
.
5. En déduire une relation de récurrence sur les coefficients de δ n :
d n,p = 2
d d n,p−1 − E
U p (τ n+1 )
+ E
U p (τ n )
.
8.12. Est-il possible d’écrire une martingale pour la profondeur d’insertion dans un arbre
quadrant, en s’inspirant de la méthode employée pour les arbres binaires de recherche ? (Penser
aux probabilités conditionnelles P[d(X, τ n ) = p
τ n ].)
371
1. Montrer que le nombre moyen de pages vaut γ b n + O(log n), où
γ b = 9
1
0
(1 − t) 3
t (1 + 2t) 2 dt
t
0
1 + 2v
(1 − v) 2 E b (v)dv,
avec
E b (z) = z
b
1
(1 − z) 2 +
b
1 − z
+ b(b + 1)
.
2. Calculer les valeurs de γ b pour b = 0, 1, 2. Montrer que, lorsque b → +∞, γ b = 3/b +
O(1/b 2 ).
3. En prenant b = 1, montrer que la proportion de feuilles dans un arbre quadrant de recherche
non paginé vaut asymptotiquement (i.e. pour un nombre de clés n tendant vers l’infini) 4π 2 −
39 + O(1/n) = 0.4784 · · · + O(1/n).
4. Montrer que le nombre de pages avec j clés, 0 ≤ j ≤ b, vaut asymptotiquement γ b,j n, avec
γ b,j =
γ b
b + 1
+
2
3
.
3bγ b + 2γ b − 6
b(b + 1)
(H b+1 − H j − 1).
(Voir l’article de Flajolet et Hoshi [84].)
Problème 8.11. (Fonction génératrice de la profondeur d’insertion) Soient respectivement
d(X, τ n ) et U p (τ n ) la profondeur d’insertion de la clé X, et le nombre de feuilles à profondeur p,
dans un arbre aléatoire τ n .
1. Relier la valeur prise par d(X, τ n ) à l’expression de U p (τ n+1 ) en fonction de U p (τ n ).
2. Établir la relation de récurrence sur les variables aléatoires U p (τ n ) :
U p (τ n+1 ) = U p (τ n ) + 2
d 1 {d(X,τn)=p−1} − 1 {d(X,τn)=p} .
3. En déduire que
E[W τ n+1 (z)] = E[W τn (z)] + (2
d z − 1)E
z
d(X,τn)
p.s.
4. Soit δ n (z) =
p d n,p z p = E(z d(X,τn) ) la fonction génératrice de probabilités de d(X, τ n ),
avec d n,p = P(d(X, τ n ) = p). Elle est reliée à la fonction génératrice des moments par la
relation δ n (e t ) = λ n (t). Montrer que δ n s’exprime en fonction des espérances des polynômes
de niveaux :
δ n (z) =
1
2 d z − 1
E[W τ n+1 (z)] − E[W τn (z)]
.
5. En déduire une relation de récurrence sur les coefficients de δ n :
d n,p = 2
d d n,p−1 − E
U p (τ n+1 )
+ E
U p (τ n )
.
8.12. Est-il possible d’écrire une martingale pour la profondeur d’insertion dans un arbre
quadrant, en s’inspirant de la méthode employée pour les arbres binaires de recherche ? (Penser
aux probabilités conditionnelles P[d(X, τ n ) = p
τ n ].)