7.1 Analyses exactes
293
Proposition 7.9 (Tries – modèle fini équiprobable) Les valeurs moyennes de la
taille S et de la longueur de cheminement externe d’un trie contenant n mots de
longueur d dans le modèle fini équiprobable satisfont
E
(d)
n [S] =
1
2 d
n
[z
n
]2
d (1 + z)
2 d
d
j =0
1
2 j
1 −
1 + 2 j z
(1 + z) 2 j
E
(d)
n [] =
1
2 d
n
[z
n
]2
d (1 + z)
2 d
d
j =0
z
1
1 + z
−
1
(1 + z) 2 j
.
La probabilité qu’un trie binaire contenant n mots soit de hauteur inférieure ou
égale à k est
P
(d)
n (h ≤ k) = 2
n(d−k)
n−1
j =0
2 k − j
2 d − j
.
Pour rendre le lien plus apparent avec l’analyse de la hauteur dans le modèle i.i.d.
uniforme qui va suivre, nous pouvons réécrire l’égalité précédente
P
(d)
n (h ≤ k) =
n−1
j =0
1 −
j
2 k
1 −
j
2 d
.
(7.11)
En faisant tendre d → ∞, nous vérifions que la limite est égale à la l’expression de
l’équation (7.16) (la formule que nous obtiendrons rigoureusement dans le modèle
i.i.d. uniforme de la section suivante).
7.1.2 Approche symbolique (modèle infini i.i.d. binaire
uniforme)
Dans cette section, l’univers des clés est B = {0, 1} N . Pour un paramètre v, nous
notons
v n = E n [v],
la valeur moyenne du paramètre v pour un trie contenant n clés (qui sont des mots
infinis). L’aléa consiste à considérer indépendamment n mots infinis. Les mots sont
ainsi supposés produits par une source sans mémoire binaire non biaisée (aussi
appelée binaire symétrique), ce que nous pouvons aussi décrire en disant que les
symboles d’un mot sont des variables i.i.d. de loi uniforme sur l’alphabet. Autrement
dit encore, la probabilité de produire un symbole 0 est égale à celle de produire un