312
7 Arbres digitaux
Proposition 7.29 L’espérance L n de la longueur de cheminement d’un trie aléatoire construit sur n mots issus d’une source binaire non biaisée est
L n = n log 2 n + n ψ(n) + o(n).
où ψ(n) est définie en (7.26).
Nous avons calculé ici les deux premiers termes du développement
asymptotique de L n avec des moyens élémentaires. Ce développement peut
être obtenu de façon plus élégante, et plus puissante, avec des outils plus
sophistiqués (formule de Rice [222] que nous verrons bientôt, ou transformée
de Mellin [100]). Nous obtenons la proposition suivante.
Proposition 7.30 L’espérance de la longueur de cheminement d’un trie
aléatoire construit sur n mots issus d’une source binaire non biaisée est
L n = n
log 2 n +
γ
log 2
+
1
2
+ ϕ(log 2 n)
+ o(n),
où ϕ est une fonction périodique de moyenne nulle et d’amplitude faible (au
plus 10 −5 ) et où γ est la constante d’Euler.
Dans cette proposition ϕ est la partie fluctuante, de moyenne nulle, de la
fonction ψ de l’équation (7.26).
Une analyse similaire peut être conduite pour étudier la taille d’un trie
dans le même modèle. Le résultat est surprenant puisque des fluctuations
apparaissent mais cette fois-ci dans le terme dominant ! En effet nous
obtenons le résultat suivant.
Proposition 7.31 L’espérance de la taille d’un trie aléatoire pour n mots
issus d’une source binaire non biaisée est
S n =
n
log 2
(1 + ϕ(log 2 n)) + o(n),
où ϕ est une fonction périodique de moyenne nulle et d’amplitude faible (au
plus 10 −5 ).
Des techniques d’analyse avancées sont nécessaires pour décrire plus précisément et analytiquement ces oscillations (par exemple son développement en
série de Fourier). Ces techniques sont présentées brièvement dans les deux
prochaines sections.