352
8 Arbres m-aires et quadrants
Proposition 8.12 Soit τ un arbre quadrant de recherche de taille n, sous la loi
P n . Soient τ (0) , . . . , τ (2 d −1) (notés sans indice n pour alléger) les 2 d sous-arbres
de la racine. Alors, conditionnellement en les tailles n 0 , . . . , n 2 d −1 des sous-arbres
de la racine, ceux-ci sont des arbres quadrants de recherche indépendants de lois
respectives P n 0 , . . . , P n 2 d −1 . De plus, les lois des tailles des sous-arbres sont les
mêmes.
Le cas général est un peu compliqué, aussi nous regardons d’abord le cas d = 2,
pour lequel des résultats explicites sont faciles à obtenir (cf. figure 8.6).
Loi des tailles des sous-arbres : cas d = 2
Soit un arbre τ construit sur n clés, qui suit la loi P n , et soit (x, y) la clé à sa racine,
qui est une v.a. de loi Ord 1 × Ord 1 .
Les sous-arbres de τ , notés τ (i) pour 0 ≤ i ≤ 3, sont de tailles aléatoires n i
et n 0 + n 1 + n 2 + n 3 = n − 1. Définissons P
(x,y)
n
comme étant la loi P n sachant
que la racine vaut (x, y), et soit E i l’événement : l’insertion d’une nouvelle clé se
fait dans le sous-arbre τ (i) ; les E i sont numérotés comme les quarts de plan de la
figure 3.12 ; cf. la figure 8.7.
Nous avons
⎧
⎪ ⎨
⎪ ⎩
P
(x,y)
n
(E 0 )
= xy
P
(x,y)
n
(E 0 ∪ E 1 ) = x
P
(x,y)
n
(E 0 ∪ E 2 ) = y.
Fig. 8.6 Les sous-arbres
d’un arbre quadrant de
recherche, dans le cas d = 2
Fig. 8.7 Les événements E i
et le découpage du carré [0, 1]