7.2 Analyses asymptotiques
325
cheminement externe, la fonction ϕ(log 2 x) regroupe les termes imaginaires liés aux
y k :
ϕ(log 2 x) =
k∈Z\{0}
2ikπ
log 2
e
−2ikπ log 2 (x) .
7.2.4 Hauteur
Nous étudions dans cette section la hauteur d’un trie. Comme déjà mentionné,
l’étude asymptotique n’a de sens que dans les modèles considérant des mots infinis
(modèle infini i.i.d. uniforme et modèle de source).
Méthode élémentaire Là encore, avec le modèle i.i.d. uniforme, nous obtenons
des expressions explicites qui se prêtent à l’analyse avec des calculs élémentaires.
Rappelons l’expression (7.16) donnant la probabilité que la hauteur d’un trie
contenant n clés soit inférieure à k :
q n,k = P n (h ≤ k) =
n−1
j =0
1 −
j
2 k
,
d’où découle l’espérance de la hauteur
E n [h] =
∞
k=0
P n (h > k) =
∞
k=0
1 − q n,k
.
L’analyse asymptotique précise (par exemple jusqu’au terme constant) de la hauteur
se révèle assez complexe, et nous nous contentons ici de déterminer le terme
dominant de l’asymptotique.
Proposition 7.41 La hauteur moyenne d’un trie construit sur n clés i.i.d. produites
par une source binaire sans mémoire non biaisée est
E n [h] = 2 log 2 n + O(log log n).
Preuve La difficulté technique essentielle est d’obtenir des termes d’erreur sur q n,k
qui soient uniformes pour n et k grands afin d’obtenir une bonne estimation de la
hauteur
E n [h] =
∞
k=0
1 − q n,k
.
(7.37)