370
8 Arbres m-aires et quadrants
8.3 Exercices et problèmes
8.1. Utiliser le comportement asymptotique au premier ordre de X n , donné par le
théorème 8.10 pour déduire le comportement asymptotique presque sûr au premier ordre de
S n , le nombre de nœuds d’un arbre m-aire de recherche défini par
S n = X
(2)
n + · · · + X
(m)
n .
Montrer que
S n
n
p.s.
−→
n→∞
1
2H m (1)
=
1
2(H m − 1)
.
8.2. Soit un arbre quadrant de recherche construit sur n = 2 clés, et de dimension d = 2 ; il a
donc 7 feuilles. Calculer les probabilités d’insertion dans la première, la seconde,. . . , la septième
feuille. Les feuilles d’un niveau donné ont-elles toutes même probabilité ? Calculer les probabilités
d’insertion aux niveaux 1 et 2.
8.3. Dans le cas d = 2, calculer la hauteur moyenne d’un arbre quadrant de taille 3, en
supposant tous les arbres quadrants de taille donnée équiprobables. Puis calculer les probabilités
des différents arbres quadrants de recherche avec 3 clés, et en déduire la hauteur moyenne d’un
arbre quadrant de recherche construit sur 3 clés sous la loi Ord.
8.4. Démontrer la proposition 8.12 : dans un arbre quadrant de recherche de taille n, sous la loi
P n , les sous-arbres d’un nœud donné sont indépendants, connaissant les tailles de ces sous-arbres.
8.5. Démontrer la proposition 8.13. On pourra utilement estimer la probabilité π n,p en
conditionnant par le fait que la racine de l’arbre ait sa i-ième coordonnée dans un petit intervalle
de la forme [u i , u i + du i ].
Problème 8.6. Le but de ce problème est de démontrer la proposition 8.15, qui donne les
probabilités de partage dans le cas d ≥ 2.
1. Montrer d’abord la première égalité de façon analogue à la proposition 8.13, qui traite le cas
d = 2.
2. En remplaçant 1/(1 − z/i) par exp(− log(1 − z/i)), réécrire ensuite la première expression
sous la forme
1
n [z d−1 ]
n
i=p+1
1
1−z/i , et en tirer la seconde égalité.
3. En conditionnant par l’événement la racine appartient à
d
i=1 [u i , u i + du i ], montrer que
π n,k =
n−1
k
1
0 . . .
1
0 (u 1 . . . u d ) k (1 − u 1 . . . u d ) n−k−1 du 1 . . . du d , et en déduire la troisième
égalité.
4. Finalement, montrer que
1
0 t q (logt) d dt = −
d
q+1
1
0 t q (log t) d−1 dt, et passer de la troisième
à la quatrième égalité.
8.7. Quel péage e n donne le nombre de feuilles d’un arbre ? Dans un arbre paginé, avec une
taille de page de b, quel péage e n donne le nombre de nœuds internes ? le nombre de feuilles ?
de nœuds ayant k clés ? Pour chacun de ces paramètres, peut-on obtenir une forme close pour sa
fonction génératrice ? sa valeur moyenne sur les arbres de taille n ?
8.8. Pour le cas d = 2, retrouver les valeurs de la moyenne et de la variance de la profondeur
d’insertion d(X, τ n ) à partir des expressions de W τn et δ n données dans la section 8.2.7.
8.9. Dans l’étude de la profondeur d’insertion pour le cas d = 2, démontrer la relation (8.17)
donnant la fonction W (z 2 , t) à l’aide de la fonction hypergéométrique F .
Problème 8.10. (Analyse des arbres quadrants paginés) On considère le paramètre additif
Nombre de pages. Soit b la taille d’une page. On se limitera ici au cas de clés bi-dimensionnelles :
d = 2.
8 Arbres m-aires et quadrants
8.3 Exercices et problèmes
8.1. Utiliser le comportement asymptotique au premier ordre de X n , donné par le
théorème 8.10 pour déduire le comportement asymptotique presque sûr au premier ordre de
S n , le nombre de nœuds d’un arbre m-aire de recherche défini par
S n = X
(2)
n + · · · + X
(m)
n .
Montrer que
S n
n
p.s.
−→
n→∞
1
2H m (1)
=
1
2(H m − 1)
.
8.2. Soit un arbre quadrant de recherche construit sur n = 2 clés, et de dimension d = 2 ; il a
donc 7 feuilles. Calculer les probabilités d’insertion dans la première, la seconde,. . . , la septième
feuille. Les feuilles d’un niveau donné ont-elles toutes même probabilité ? Calculer les probabilités
d’insertion aux niveaux 1 et 2.
8.3. Dans le cas d = 2, calculer la hauteur moyenne d’un arbre quadrant de taille 3, en
supposant tous les arbres quadrants de taille donnée équiprobables. Puis calculer les probabilités
des différents arbres quadrants de recherche avec 3 clés, et en déduire la hauteur moyenne d’un
arbre quadrant de recherche construit sur 3 clés sous la loi Ord.
8.4. Démontrer la proposition 8.12 : dans un arbre quadrant de recherche de taille n, sous la loi
P n , les sous-arbres d’un nœud donné sont indépendants, connaissant les tailles de ces sous-arbres.
8.5. Démontrer la proposition 8.13. On pourra utilement estimer la probabilité π n,p en
conditionnant par le fait que la racine de l’arbre ait sa i-ième coordonnée dans un petit intervalle
de la forme [u i , u i + du i ].
Problème 8.6. Le but de ce problème est de démontrer la proposition 8.15, qui donne les
probabilités de partage dans le cas d ≥ 2.
1. Montrer d’abord la première égalité de façon analogue à la proposition 8.13, qui traite le cas
d = 2.
2. En remplaçant 1/(1 − z/i) par exp(− log(1 − z/i)), réécrire ensuite la première expression
sous la forme
1
n [z d−1 ]
n
i=p+1
1
1−z/i , et en tirer la seconde égalité.
3. En conditionnant par l’événement la racine appartient à
d
i=1 [u i , u i + du i ], montrer que
π n,k =
n−1
k
1
0 . . .
1
0 (u 1 . . . u d ) k (1 − u 1 . . . u d ) n−k−1 du 1 . . . du d , et en déduire la troisième
égalité.
4. Finalement, montrer que
1
0 t q (logt) d dt = −
d
q+1
1
0 t q (log t) d−1 dt, et passer de la troisième
à la quatrième égalité.
8.7. Quel péage e n donne le nombre de feuilles d’un arbre ? Dans un arbre paginé, avec une
taille de page de b, quel péage e n donne le nombre de nœuds internes ? le nombre de feuilles ?
de nœuds ayant k clés ? Pour chacun de ces paramètres, peut-on obtenir une forme close pour sa
fonction génératrice ? sa valeur moyenne sur les arbres de taille n ?
8.8. Pour le cas d = 2, retrouver les valeurs de la moyenne et de la variance de la profondeur
d’insertion d(X, τ n ) à partir des expressions de W τn et δ n données dans la section 8.2.7.
8.9. Dans l’étude de la profondeur d’insertion pour le cas d = 2, démontrer la relation (8.17)
donnant la fonction W (z 2 , t) à l’aide de la fonction hypergéométrique F .
Problème 8.10. (Analyse des arbres quadrants paginés) On considère le paramètre additif
Nombre de pages. Soit b la taille d’une page. On se limitera ici au cas de clés bi-dimensionnelles :
d = 2.