7.1 Analyses exactes
299
La probabilité P n (h ≤ k) qu’un trie contenant n clés soit de hauteur inférieure ou
égale à k est donc
P n (h ≤ k) = n! [z
n
](1 + z/2
k )
2 k =
n!
2 nk [z
n
](1 + z)
2 k =
n−1
j =0
1 −
j
2 k
. (7.16)
Remarque 7.15 Lorsque n ≤ 2 k dans (7.16), un des termes du produit s’annule et
nous obtenons bien P n (h ≤ k) = 0 dans ce cas.
Nous en déduisons aussi la valeur moyenne de la hauteur d’un trie à n clés ou mots
dans ce modèle
E n [h] =
∞
k=0
P n (h > k) =
∞
k=0
⎛
⎝ 1 −
n−1
j =0
1 −
j
2 k
⎞
⎠ .
(7.17)
Nous résumons dans la proposition suivante les résultats obtenus dans le modèle
infini i.i.d. (binaire) uniforme.
Proposition 7.16 (Tries – modèle infini i.i.d. uniforme – expressions exactes)
Les valeurs moyennes de la taille S et de la longueur de cheminement externe
d’un trie contenant n mots dans le modèle infini i.i.d. uniforme, avec un alphabet
binaire, satisfont
E n [S] =
k≥0
2
k
1 −
1 −
1
2 k
n
−
n
2 k
1 −
1
2 k
n−1
E n [] = n
k≥0
1 −
1 −
1
2 k
n−1
.
La probabilité qu’un trie binaire contenant n mots soit de hauteur inférieure ou
égale à k est
P n (h ≤ k) =
n−1
j =0
1 −
j
2 k
.
Remarque 7.17
1. La méthode qui vient d’être présentée permet d’obtenir les expressions exactes
de la valeur moyenne d’autres paramètres, comme la longueur de cheminement
externe d’un PATRICIA trie, voir Flajolet et al. [97] et les exercices 7.6, 7.7 et 7.8.
2. Pour le modèle infini i.i.d. binaire non uniforme, les techniques s’adaptent
également à un modèle probabiliste où les probabilités p et q = 1 − p d’avoir 0
ou 1 sont différentes de
1
2 (cas biaisé).