7.4 Exercices
335
Utiliser la proposition 7.46 pour montrer que le premier terme de l’asymptotique de la hauteur
est (1 +
1
b ) log 2 n.
7.12. Tries hybrides Implémenter la structure de TST (ternary search trie), qui est une structure
de trie dans laquelle les nœuds frères sont stockés grâce à une structure d’abr (voir [19, 233] pour
une présentation et [45] pour une analyse). Chaque nœud de la structure est composé de 4 champs :
une lettre, un lien gauche, un lien de descente et un lien droit. Lors d’une recherche, on compare la
lettre courante du mot recherché à la lettre contenue dans le nœud, si cette lettre est respectivement
inférieure, égale ou supérieure, le lien respectivement gauche, d’égalité ou droit est emprunté. La
recherche continue à la prochaine lettre du mot recherché s’il y a égalité, et en considérant la lettre
courante du mot recherché si les autres liens ont été empruntés (navigation de type abr).
7.13. Arbre digital de recherche Étudions la moyenne de la longueur de cheminement externe
a n dans le modèle infini i.i.d. uniforme avec alphabet binaire.
– Montrer que la suite a n vérifie a 0 = 0 et
a n = n − 1 + 2
n−1
k=0
n − 1
k
a k , n ≥ 1.
– Soit A(z) =
n≥0 a n z n /n! la série génératrice exponentielle. Montrer que A(z) vérifie
l’équation fonctionnelle
A
(z) = ze
z + 2A(z/2)e
z/2 .
(7.44)
Remarquons que l’équation est similaire à celle obtenue pour les tries mais fait intervenir une
dérivée qui rend l’analyse plus difficile.
– Soit B(z) = e −z A(z) =
n≥0 b n /n!. À l’aide de la relation (7.44), montrer que B(z) satisfait
l’équation
B
(z) + B(z) = z + 2B(z/2).
– Extraire le coefficient d’ordre n pour établir la relation
b n = −
1 −
1
2 n−2
b n−1 , n ≥ 3,
et b 0 = b 1 = 0 et b 2 = 1.
– En itérant, montrer qu’on obtient
b n = (−1)
n Q n−2 ,
avec
Q n =
n
j =0
1 −
1
2 j
.
Notons que lorsque n tend l’infini, Q n approche la limite Q ∞ = 0,288788 . . . .
– Montrer que grâce à la relation A(z) = e z B(z), on peut extraire le coefficient a n sous la forme
a n =
k≥2
n
k
(−1)
k Q k−2 .
335
Utiliser la proposition 7.46 pour montrer que le premier terme de l’asymptotique de la hauteur
est (1 +
1
b ) log 2 n.
7.12. Tries hybrides Implémenter la structure de TST (ternary search trie), qui est une structure
de trie dans laquelle les nœuds frères sont stockés grâce à une structure d’abr (voir [19, 233] pour
une présentation et [45] pour une analyse). Chaque nœud de la structure est composé de 4 champs :
une lettre, un lien gauche, un lien de descente et un lien droit. Lors d’une recherche, on compare la
lettre courante du mot recherché à la lettre contenue dans le nœud, si cette lettre est respectivement
inférieure, égale ou supérieure, le lien respectivement gauche, d’égalité ou droit est emprunté. La
recherche continue à la prochaine lettre du mot recherché s’il y a égalité, et en considérant la lettre
courante du mot recherché si les autres liens ont été empruntés (navigation de type abr).
7.13. Arbre digital de recherche Étudions la moyenne de la longueur de cheminement externe
a n dans le modèle infini i.i.d. uniforme avec alphabet binaire.
– Montrer que la suite a n vérifie a 0 = 0 et
a n = n − 1 + 2
n−1
k=0
n − 1
k
a k , n ≥ 1.
– Soit A(z) =
n≥0 a n z n /n! la série génératrice exponentielle. Montrer que A(z) vérifie
l’équation fonctionnelle
A
(z) = ze
z + 2A(z/2)e
z/2 .
(7.44)
Remarquons que l’équation est similaire à celle obtenue pour les tries mais fait intervenir une
dérivée qui rend l’analyse plus difficile.
– Soit B(z) = e −z A(z) =
n≥0 b n /n!. À l’aide de la relation (7.44), montrer que B(z) satisfait
l’équation
B
(z) + B(z) = z + 2B(z/2).
– Extraire le coefficient d’ordre n pour établir la relation
b n = −
1 −
1
2 n−2
b n−1 , n ≥ 3,
et b 0 = b 1 = 0 et b 2 = 1.
– En itérant, montrer qu’on obtient
b n = (−1)
n Q n−2 ,
avec
Q n =
n
j =0
1 −
1
2 j
.
Notons que lorsque n tend l’infini, Q n approche la limite Q ∞ = 0,288788 . . . .
– Montrer que grâce à la relation A(z) = e z B(z), on peut extraire le coefficient a n sous la forme
a n =
k≥2
n
k
(−1)
k Q k−2 .