364
8 Arbres m-aires et quadrants
8.2.7 Polynômes de niveaux
Nous présentons maintenant une méthode alternative pour l’étude de la profondeur
d’insertion d(X, τ n ), paramètre déjà étudié en Section 8.2.5. Après avoir défini
les polynômes de niveaux W τ n (z) (qui sont des variables aléatoires) et établi une
relation de récurrence sur leurs espérances, nous relions ces espérances à δ n (z), la
fonction génératrice de probabilité de d(X, τ n ). L’étape suivante consiste à étudier
la fonction génératrice bivariée W (z, t) =
n≥0 E[W τ n (z)]t n . Dans le cas d = 2,
une équation fonctionnelle sur W permet de retrouver les résultats précédents sur la
moyenne et la variance de d(X, τ n ). Nous pouvons aussi montrer, en dimension d
quelconque, que la profondeur d’insertion suit asymptotiquement une loi normale.
Cette approche est due à Flajolet et Lafforgue [86].
Définition 8.23 Soit τ un arbre quadrant de recherche dans Q, et soit U p (τ ) le
nombre de feuilles de l’arbre τ qui se trouvent au niveau p. Rappelons que les
feuilles sont les nœuds externes ainsi que les places d’insertion dans l’arbre quadrant
complété.
Le polynôme de niveaux d’un arbre τ est
W τ (z) :=
p≥0
U p (τ ) z
p
=
u feuille de τ
z
|u| ,
où |u| est la profondeur (ou niveau) de la feuille u.
Nous avons W ε (z) = 1 (où ε est l’arbre vide) ; le polynôme de niveaux pour l’arbre
τ 0 réduit à une feuille-racine (qui ne contient pas de clé) est W τ 0 (z) = 1 ; et pour
l’arbre τ 1 avec une seule clé à la racine et 2 d feuilles, W τ 1 (z) = 2 d z.
La valeur en z = 1 du polynôme de niveaux de l’arbre τ est égale à son nombre
de feuilles :
W τ (1) = (2
d
− 1) |τ | + 1.
Soient τ (0) , τ (1) , . . . , τ (2 d −1) les sous-arbres à la racine de l’arbre τ ; les polynômes
de niveaux de ces arbres satisfont une relation de récurrence, qui est l’outil-clé dans
la suite :
W τ (z) = z
2 d −1
i=0
W τ (i) (z).
(8.14)
Lorsque l’arbre τ devient aléatoire, tiré selon la loi P n , le polynôme de niveaux
W τ n (z) =
p≥0
U p (τ n )z
p
8 Arbres m-aires et quadrants
8.2.7 Polynômes de niveaux
Nous présentons maintenant une méthode alternative pour l’étude de la profondeur
d’insertion d(X, τ n ), paramètre déjà étudié en Section 8.2.5. Après avoir défini
les polynômes de niveaux W τ n (z) (qui sont des variables aléatoires) et établi une
relation de récurrence sur leurs espérances, nous relions ces espérances à δ n (z), la
fonction génératrice de probabilité de d(X, τ n ). L’étape suivante consiste à étudier
la fonction génératrice bivariée W (z, t) =
n≥0 E[W τ n (z)]t n . Dans le cas d = 2,
une équation fonctionnelle sur W permet de retrouver les résultats précédents sur la
moyenne et la variance de d(X, τ n ). Nous pouvons aussi montrer, en dimension d
quelconque, que la profondeur d’insertion suit asymptotiquement une loi normale.
Cette approche est due à Flajolet et Lafforgue [86].
Définition 8.23 Soit τ un arbre quadrant de recherche dans Q, et soit U p (τ ) le
nombre de feuilles de l’arbre τ qui se trouvent au niveau p. Rappelons que les
feuilles sont les nœuds externes ainsi que les places d’insertion dans l’arbre quadrant
complété.
Le polynôme de niveaux d’un arbre τ est
W τ (z) :=
p≥0
U p (τ ) z
p
=
u feuille de τ
z
|u| ,
où |u| est la profondeur (ou niveau) de la feuille u.
Nous avons W ε (z) = 1 (où ε est l’arbre vide) ; le polynôme de niveaux pour l’arbre
τ 0 réduit à une feuille-racine (qui ne contient pas de clé) est W τ 0 (z) = 1 ; et pour
l’arbre τ 1 avec une seule clé à la racine et 2 d feuilles, W τ 1 (z) = 2 d z.
La valeur en z = 1 du polynôme de niveaux de l’arbre τ est égale à son nombre
de feuilles :
W τ (1) = (2
d
− 1) |τ | + 1.
Soient τ (0) , τ (1) , . . . , τ (2 d −1) les sous-arbres à la racine de l’arbre τ ; les polynômes
de niveaux de ces arbres satisfont une relation de récurrence, qui est l’outil-clé dans
la suite :
W τ (z) = z
2 d −1
i=0
W τ (i) (z).
(8.14)
Lorsque l’arbre τ devient aléatoire, tiré selon la loi P n , le polynôme de niveaux
W τ n (z) =
p≥0
U p (τ n )z
p