6.1 Analyses de la longueur de cheminement et du profil
219
Fig. 6.2 Un abr de taille 7, τ 7 , 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 et l’abr τ 8 obtenu par insertion ultérieure de
x 8 = 0, 6 sur la feuille bleue. Les deux arbres représentés ici sont les arbres complétés, dont
les feuilles correspondent aux possibilités d’insertion. La profondeur d’insertion de x 8 dans τ 7 est
d(x 8 , τ 7 ) = 3
6.1 Analyses de la longueur de cheminement et du profil
Nous considérons dans cette section des arbres binaires de recherche sous la loi
« des permutations uniformes », c’est-à-dire sous la loi Ord. La longueur de
cheminement se prête dans une première section 6.1.1 à une étude énumérative à
base de combinatoire analytique. Nous obtenons les moments de la longueur de
cheminement via une fonction génératrice bivariée, solution d’une équation aux
dérivées partielles. Dans la section 6.1.2, nous utilisons des méthodes probabilistes,
notamment la mise en évidence de martingales, pour obtenir le comportement
asymptotique presque sûr de la longueur de cheminement ainsi que du profil. La
méthode de contraction détaillée dans la section 6.1.3 éclaire la loi limite de la
longueur de cheminement. Elle est simulée dans la section 6.1.4.
6.1.1 Longueur de cheminement et séries génératrices
Soit τ n un abr de taille n (ou plutôt, le complété de l’abr, avec n nœuds internes
et n + 1 feuilles). Etudions la longueur de cheminement interne lci(τ n ), qui est un
paramètre additif de fonction de péage n − 1 (cf. la définition 1.48) ; l’étude serait
analogue avec lce(τ n ), puisque les deux longueurs de cheminement sont liées par la
relation (1.9) : lce(τ n ) = lci(τ n ) + 2n. L’additivité s’écrit :
lci(τ n ) = lci(τ
(g)
n ) + lci(τ
(d)
n ) + n − 1,
(6.1)
où τ
(g)
n et τ
(d)
n désignent les sous-arbres respectivement gauche et droit d’un abr τ n .