292
7 Arbres digitaux
Hauteur L’étude du paramètre χ k (ω) défini par l’équation (7.5) et de la série
génératrice cumulée χ
(d)
k (z) (dont les coefficients comptent les tries de hauteur
inférieure ou égale à k) est un peu différente de par sa nature « multiplicative ».
La traduction en équation fonctionnelle de l’équation (7.6) donne pour k ≥ 1
χ
(d)
k (z) =
χ
(d−1)
k−1 (z)
2
,
χ
(d)
0 (z) = 1 + 2
d z.
En itérant nous obtenons
χ
(d)
k (z) =
1 + 2
d−k z
2 k
.
Le polynôme χ
(d)
k (z) est aisément calculé pour d fixé et k ≤ d, ce qui permet
de calculer la probabilité qu’un trie binaire contenant n clés dans le modèle fini
équiprobable soit de hauteur inférieure ou égale à k :
P
(d)
n (h ≤ k) =
1
2 d
n
[z
n
] χ
(d)
k (z) = 2
n(d−k)
2 k
n
2 d
n
= 2
n(d−k)
n−1
j =0
2 k − j
2 d − j
.
(7.9)
Par exemple, pour d = 3 (comme dans l’exemple précédent), nous obtenons la
table suivante qui donne la probabilité qu’un trie contenant deux clés soit de hauteur
inférieure ou égale à k (ce que nous pouvons vérifier à l’aide la figure 7.2).
k
0 1 2 3
P
(3)
2 (h ≤ k) 0
4
7
6
7
1
Ces calculs permettent aussi de calculer la valeur moyenne de la hauteur d’un
trie dans ce modèle
E
(d)
n [h] =
∞
k=0
P
(d)
n (h > k) =
k≥0
⎛
⎝ 1 − 2
n(d−k)
n−1
j =0
2 k − j
2 d − j
⎞
⎠ .
(7.10)
Pour d = 3, nous calculons par exemple
n
1 2
3
4
5 6 7 8
E
(3)
n [h] 0
11
7 ≈ 1,571
17
7 ≈ 2,428
97
35 ≈ 2,771 3 3 3 3
Nous résumons dans la proposition suivante les résultats obtenus dans le modèle
fini équiprobable B (d) .