336
7 Arbres digitaux
La somme ainsi obtenue peut s’évaluer grâce par exemple à la méthode de Rice (cette approche
est due à Knuth ; voir [92] pour une présentation complète de cette approche et [91, 135] pour
des approches plus récentes et plus générales ; voir également [172, 239]).
7.14. Hauteur d’un trie On présente ici une approche probabiliste alternative à celle de la
section 7.2.4. Pour un ensemble de mot X = {x 1 , . . . , x n }, définissons C ij comme la longueur
du plus long préfixe commun entre x i et x j (voir [144]). Alors la hauteur du trie s’écrit
H n = max
1≤i {C ij } + 1.
– Dans le modèle infini i.i.d. uniforme montrer que
P(C ij = k) =
1
2 k+1 .
– En déduire que puisque que le nombre de paires (i, j ) est borné par n 2 ,
P(H n > k) ≤ n
2 P(C ij ≥ k).
– Montrer que pour tout ε > 0,
P(H n > 2(1 + ε) log 2 n) ≤
1
n 2 ε
.
Remarque : cela donne simplement le bon ordre de grandeur pour la hauteur. Il est possible de
montrer, à l’aide d’une méthode de second moment [239] un peu plus sophistiquée, que l’on a
également pour tout ε > 0,
P(H n > 2(1 − ε) log 2 n) → 0.