8.2 Arbres quadrants de recherche
353
Il est possible d’obtenir différentes probabilités conditionnelles sur les tailles des
sous-arbres ; la proposition ci-dessous en présente quelques-unes, dues à Devroye
et Laforest [61] et à Flajolet et al. [99].
Proposition 8.13 Soit τ un arbre quadrant de recherche à n clés, en dimension
d = 2, sous la loi P n .
i) La probabilité que la taille cumulée des deux premiers sous-arbres, τ (0) et τ (1) ,
soit m, vaut
P n
τ
(0)
∪ τ
(1)
= m
= P n (n 0 + n 1 = m) =
1
n
(0 ≤ m ≤ n − 1).
ii) La probabilité μ n 0 ,n 1 ,n 2 ,n 3 que les sous-arbres τ (i) , i = 0, . . . , 3, soient de
tailles respectives n i , avec n 0 + n 1 + n 2 + n 3 = n − 1 vaut
μ n 0 ,n 1 ,n 2 ,n 3 =
1
n
(n 0 + n 1 )! (n 0 + n 2 )! (n 1 + n 3 )! (n 2 + n 3 )!
n! n 0 ! n 1 ! n 2 ! n 3 !
.
iii) La probabilité w n,p,, que le premier sous-arbre τ (0) soit de taille p et le
troisième sous-arbre τ (2) soit de taille − p vaut
w p,n,, =
1
n (( + 1)
.
iv) La probabilité π n,p que le premier sous-arbre τ (0) soit de taille p est
π n,p =
1
n
H n − H p
.
En particulier, la probabilité que le premier sous-arbre τ (0) soit vide est
π n,0 =
H n
n
.
v) La probabilité qu’un sous-arbre τ (i) , i = 0, . . . , 3, soit de taille p est égale
à π n,p .
Preuve Nous explicitons les calculs pour la première propriété : P
(x,y)
n
τ (0) ∪ τ (1)
= m
, et ne détaillons pas les démonstrations des autres égalités ;
cf. l’exercice 8.5. Sachant que la clé à la racine de l’arbre τ est (x, y), nous avons
P
(x,y)
n
(n 0 + n 1 = m) =
n − 1
m
x
m (1 − x)
n−1−m ,