232
6 Arbres binaires de recherche
et donc
lce(τ n ) = W
τ n (1) ;
Y n = M
n (1).
Par le théorème 6.8, nous remarquons que la valeur z = 1 est dans le domaine de
convergence p.s. et L 1 de la martingale de l’abr. Comme la dérivée d’une martingale
est encore une martingale (voir l’annexe C.8.1), nous avons immédiatement la
propriété de martingale du théorème suivant, dû à Régnier [219]. La convergence
de la martingale dérivée n’est pas détaillée ici, elle se trouve dans [39].
Théorème 6.11 Soit un processus d’abr (τ n ) n≥0 sous la loi Ord. Alors
Y n :=
1
n + 1
(lce(τ n ) − E(lce(τ n )))
est une F n -martingale. Cette martingale converge p.s. et dans L 1 vers une limite
aléatoire Y (c’est-à-dire que Y est une variable aléatoire).
Il existe des résultats analogues pour la longueur de cheminement interne lci(τ n )
(voir l’exercice 6.5).
Pour les raisons détaillées dans la section 3.3.1, la loi de Y s’appelle parfois « loi
du tri rapide ». La caractérisation de cette loi est faite dans la section 6.1.3 ci-après.
Elle admet une densité sur R qui est simulée dans la section 6.1.4.
Analyse p.s. du profil d’un abr
Le profil d’un abr τ n de taille n est donné par les U k (τ n ), nombre de
feuilles à chaque niveau k, défini par (6.5). Le comportement asymptotique
presque sûr des U k (τ n ) est précisé dans le théorème suivant. La démonstration
tire parti de la martingale de l’abr et se trouve dans [39].
Théorème 6.12 Pour tout z réel dans l’intervalle ]c /2; c/2[ de convergence
p.s. et L 1 du théorème 6.8, soit M ∞ (z) la limite de la martingale de l’abr sous
la loi Ord. Alors, presque sûrement, pour tout sous-ensemble compact K de
l’intervalle ]c /2; c/2[, nous avons
lim
n
sup
k:(k/ log n)∈K
U k (τ n )
E(U k (τ n ))
− M ∞
k
2 log n
= 0.