8.2 Arbres quadrants de recherche
355
Proposition 8.15 Soit τ (i) , i = 0, . . . , 2 d − 1, l’un des sous arbres de la
racine d’un arbre quadrant de recherche à n clés 4 tiré suivant la loi P n , et
soit π n,p la probabilité que τ (i) soit de taille p. Alors π n,p est donnée par les
expressions équivalentes suivantes :
π n,p =
1
n
p 1
i 1 . . . i d−1
=
1
n
m 1 +2m 2 +···+(d−1)m d−1 =n
(H
(1)
n − H
(1)
p ) m 1 . . . (H
(d−1)
n
− H
(d−1)
p
) m d−1
d−1
i=1 i m i m i !
=
n − 1
p
n−p−1
i=0
n − p − 1
i
(−1) i
(p + 1 + i) d
=
n − 1
p
1
0
t
p (1 − t)
n−p−1 (− log t) d−1
(d − 1)!
dt.
Dans la troisième de ces formules, H
(r)
m désigne un nombre harmonique
généralisé : H
(r)
m =
1≤j ≤m j −r (et donc H
(1)
m = H m ).
Des indications sur la preuve de cette proposition sont données dans le
problème 8.6.
8.2.4 Paramètres additifs
Nous avons défini les paramètres additifs sur les arbres en Section 1.3.2 ; rappelons
qu’un paramètre additif v sur un arbre quadrant de recherche τ est défini par un
péage, ou coût à la racine, r(τ ), et par une relation de récurrence, avec ε désignant
l’arbre vide :
v(ε) = r(ε);
v(τ ) = r(τ ) +
0≤j ≤2 d −1 v(τ (j ) ) .
Exemples (pour des arbres quadrants complétés)
– Pour un péage r(τ ) = 1 {|τ |=1} , nous obtenons le nombre de feuilles de l’arbre.
– Les péages r 1 (τ ) = 1 {|τ |≥1} et r 2 (τ ) = 1 {|τ |≥2} donnent respectivement le
nombre total de nœuds de l’arbre, et le nombre de nœuds internes.
4 Nous gardons la notation τ (i) au lieu de τ
(i)
n tant qu’il n’y a pas d’ambiguïté.