2.2 Aléa sur les arbres marqués
51
Fig. 2.6 À gauche, l’arbre binaire de recherche construit avec les clés x 1 = 0,3 ; x 2 = 0,1 ; x 3 =
0,4 ; x 4 = 0,15 ; x 5 = 0,9 ; x 6 = 0,02 ; x 7 = 0,2 ; à droite, celui obtenu par insertion ultérieure de
x 8 = 0,6, qui s’insère sur le carré bleu. Nous obtenons : x 6 < x 2 < x 4 < x 7 < x 1 < x 3 < x 8 < x 5
et donc le réordonnement est σ n+1 = (6, 2, 4, 7, 1, 3, 8, 5) et σ
−1
n+1 = (5, 2, 6, 3, 8, 1, 4, 7)
j + 1-ième feuille de τ n , deux conditionnements sont possibles :
(a) en conditionnant par l’arbre marqué et donc par les valeurs de x 1 . . . , x n , ce qui
rend compte de l’évolution de l’arbre marqué τ n : pour tout j ∈ {0, 1, . . . , n},
P
x n+1 ∈]x σ n (j ) , x σ n (j +1) [
τ n
= x σ n (j +1) − x σ n (j ) ;
(b) lorsque c’est la forme de l’arbre ou son re-étiquetage qui nous intéresse, nous
conditionnons par le réordonnement σ n :
P
x n+1 ∈]x σ n (j ) , x σ n (j +1) [
σ n
= P(σ n+1 (j + 1) = n + 1) =
1
n + 1
.
Cette dernière relation peut se voir aussi avec le rang R k d’une clé x k , le rang
de x k étant défini par :
R k =
k
j =1
1 1 {x j ≤x k } , k ≥ 1.
Comme les variables aléatoires x i sont indépendantes et de même loi, R k est de
loi uniforme sur {1, . . . , k}, de sorte que pour tout j = 0, . . . , n,
P(R n+1 = j + 1 | R 1 , . . . , R n ) =
1
n + 1
.
En résumé, en termes d’évolution dynamique de la forme de l’abr, c’est-à-dire
avec le conditionnement (b), l’insertion de la n+1-ième clé dans un abr de taille n
est uniforme parmi les n+1 possibilités d’insertion. Rappelons-nous la définition
du processus d’arbre bourgeonnant de la section 2.1.2 : nous constatons ainsi le fait
suivant.