8.2 Arbres quadrants de recherche
363
Comme l’écart-type
√
Var (d(X, τ n )) = σ (d(X, τ n )) = o (E [d(X, τ n )]), le
théorème C.9 fournit le résultat suivant.
Corollaire 8.21 Lorsque n tend vers +∞,
d(X, τ n )
log n
−→ 1 en probabilité.
8.2.6 Hauteur d’un arbre quadrant de recherche
Un encadrement de la hauteur d’un arbre quadrant de recherche de taille n est facile
à obtenir : au pire, l’arbre a un nœud par niveau, et est de hauteur n. Au mieux,
tous les niveaux (sauf peut-être le dernier) sont remplis, et nous avons (2 d ) j clés au
niveau j (la racine est au niveau 0). Si la hauteur de l’arbre saturé 7 est h, le nombre
de ses clés vaut n = (2 d(h+1) −1)/(2 d −1). En inversant ces relations, nous obtenons
un encadrement sur la hauteur h(τ n ) d’un arbre quadrant de recherche construit sur
n clés aléatoires :
1
d
log 2
n(2
d
− 1) + 1
− 1 ≤ h(τ n ) ≤ n.
Il est possible d’obtenir des résultats plus fins : Devroye [56] a montré
le théorème suivant.
Théorème 8.22 Soit h(τ n ) la hauteur d’un arbre quadrant de recherche
construit sur n clés. Alors, lorsque n tend vers +∞,
h(τ n )
log n
−→
c
d
en probabilité,
où c = 4,31107 . . . (déjà apparue dans l’étude des arbres binaires de
recherche) est la plus grande solution de l’équation
x log 2 + x − x log x = 1.
D’après le Théorème 8.22, les arbres quadrants de recherche sur des clés
de dimension d sont (en moyenne et approximativement quand n tend vers
+∞) d fois moins hauts que les arbres binaires de recherche.
7 Nous définissons un arbre quadrant saturé de façon analogue à un arbre binaire saturé (cf.
définition 1.26) comme un arbre dont tous les niveaux sont pleins, et donc où toutes les feuilles
sont au même niveau.
363
Comme l’écart-type
√
Var (d(X, τ n )) = σ (d(X, τ n )) = o (E [d(X, τ n )]), le
théorème C.9 fournit le résultat suivant.
Corollaire 8.21 Lorsque n tend vers +∞,
d(X, τ n )
log n
−→ 1 en probabilité.
8.2.6 Hauteur d’un arbre quadrant de recherche
Un encadrement de la hauteur d’un arbre quadrant de recherche de taille n est facile
à obtenir : au pire, l’arbre a un nœud par niveau, et est de hauteur n. Au mieux,
tous les niveaux (sauf peut-être le dernier) sont remplis, et nous avons (2 d ) j clés au
niveau j (la racine est au niveau 0). Si la hauteur de l’arbre saturé 7 est h, le nombre
de ses clés vaut n = (2 d(h+1) −1)/(2 d −1). En inversant ces relations, nous obtenons
un encadrement sur la hauteur h(τ n ) d’un arbre quadrant de recherche construit sur
n clés aléatoires :
1
d
log 2
n(2
d
− 1) + 1
− 1 ≤ h(τ n ) ≤ n.
Il est possible d’obtenir des résultats plus fins : Devroye [56] a montré
le théorème suivant.
Théorème 8.22 Soit h(τ n ) la hauteur d’un arbre quadrant de recherche
construit sur n clés. Alors, lorsque n tend vers +∞,
h(τ n )
log n
−→
c
d
en probabilité,
où c = 4,31107 . . . (déjà apparue dans l’étude des arbres binaires de
recherche) est la plus grande solution de l’équation
x log 2 + x − x log x = 1.
D’après le Théorème 8.22, les arbres quadrants de recherche sur des clés
de dimension d sont (en moyenne et approximativement quand n tend vers
+∞) d fois moins hauts que les arbres binaires de recherche.
7 Nous définissons un arbre quadrant saturé de façon analogue à un arbre binaire saturé (cf.
définition 1.26) comme un arbre dont tous les niveaux sont pleins, et donc où toutes les feuilles
sont au même niveau.