258
6 Arbres binaires de recherche
Fig. 6.11 En haut à gauche, un arbre biaisé de taille 6, avec l’épine dorsale des nœuds roses, 6
feuilles noires et une feuille rose. En haut à droite, l’arbre obtenu en faisant pousser une feuille
noire. En bas les deux arbres possibles en faisant pousser la feuille rose
Bernoulli de paramètre
2z
n+2z . En particulier, la moyenne de s n peut se calculer :
E z (s n ) = 1 +
2z
1 + 2z
+ · · · +
2z
n − 1 + 2z
∼ 2z log n
lorsque n → +∞, et nous obtenons pour s n des résultats classiques de loi
des grands nombres, théorème central limite et grandes déviations, détaillés dans
l’exercice 6.6.
La première partie de la proposition suivante met en évidence une martingale
qui va permettre de représenter P z , la loi de l’arbre biaisé, sous forme de produit,
comme c’était déjà le cas pour l’arbre biaisé de Galton-Watson.
Proposition 6.32 Soit s n le niveau de la feuille rose d’un arbre biaisé. Soit z un
réel strictement positif. Rappelons la notation :
γ n (z) =
n−1
j =0
1 +
z
j + 1
.