6.1 Analyses de la longueur de cheminement et du profil
231
qui permet d’étudier le polynôme de niveau en séparant la partie déterministe
(l’espérance qui est explicite) et la partie aléatoire qui, étant une martingale, possède
des propriétés agréables. C’est ainsi que nous pouvons obtenir des résultats de type
théorème central limite et grandes déviations sur la mesure μ τ n définie en (6.6) ;
cf. [37] et Jabbour-Hattab [139] pour des grandes déviations sur la profondeur
d’insertion.
La proposition suivante donne l’asymptotique de la largeur, définie
comme le nombre maximal de nœuds sur un même niveau, d’un arbre binaire
de recherche ; cf. [37, Cor. 1] pour la preuve.
Proposition 6.10 Soit U(τ n ) := max k≥0 U k (τ n ) la largeur de l’arbre τ n .
Presque sûrement lorsque n → +∞,
U(τ n )
n
√
4π log n
= 1 + O
1
√
log n
.
Analyse p.s. de la longueur de cheminement externe
Grâce à la martingale de l’abr, nous allons trouver le comportement asymptotique
presque sûr de la longueur de cheminement externe de l’abr, renormalisée de la
façon suivante. Posons
Y n :=
1
n + 1
(lce(τ n ) − E(lce(τ n ))) .
(6.10)
Remarquons d’abord que la longueur de cheminement externe s’exprime avec
W τ n , le polynôme de niveau de l’abr, puisque
lce(τ n ) =
u∈∂τ n
|u| =
k≥0
k U k (τ n ) = W
τ n (1).
Par conséquent, en dérivant M n (z) :=
W τ n (z)
E(W τ n (z))
par rapport à z puis en prenant
z = 1, nous obtenons (en nous rappelant que W τ n (1) = n + 1 )
M
n (1) =
1
n + 1
W
τ n (1) − E(W
τ n (1))
,