6.1 Analyses de la longueur de cheminement et du profil
221
l’insertion d’une clé X n+1 (indépendante et de même loi que les précédentes) se fait
à profondeur d(X n+1 , τ n ), et dans la suite nous noterons plus légèrement
D n+1 := d(X n+1 , τ n )
pour cette profondeur d’insertion, qui est une variable aléatoire.
Dans ce même modèle Ord, l’insertion se fait uniformément sur l’une des n + 1
feuilles de l’arbre τ n et donc
E(D n+1 ) =
1
n + 1
E(lce(τ n ))
qui devient avec l’équation (1.9) reliant longueurs de cheminement interne et
externe :
E(D n+1 ) =
1
n + 1
(E(lci(τ n )) + 2n),
soit finalement
E(D n+1 ) = 2(H n+1 − 1) = 2 log n + 2(γ − 1) + O
1
n
,
où γ = 0,577215 . . . est la constante d’ Euler. Le théorème suivant résume ce que
nous venons d’obtenir.
Théorème 6.2 Pour un abr τ n de taille n sous la loi Ord, la moyenne de la longueur
de cheminement interne est
E (lci(τ n )) = 2(n+1)H n −4n = 2n log n+2(γ −2) n+2 log n+2γ +1+O
1
n
,
et la moyenne de la profondeur d’insertion est
E(D n+1 ) = 2(H n+1 − 1) = 2 log n + 2(γ − 1) + O
1
n
,
où les valeurs asymptotiques sont pour n → +∞, et où γ = 0,577215 . . . est la
constante d’Euler.
Premiers moments de la longueur de cheminement interne
Pour ce faire, nous introduisons la fonction génératrice de probabilités bivariée
(voir l’annexe B.3.2)
F (x, y) =
n,k≥0
P (lci(τ n ) = k) x
n y
k .