332
7 Arbres digitaux
Proposition 7.46 (Hauteur asymptotique du trie (cas général)) Pour un
trie construit sur n clés produites par une source (satisfaisant certaines
hypothèses assez générales non détaillées ici), l’espérance de la hauteur
vérifie quand n → +∞
E n [h] =
2
| log λ(2)|
log n + Q(log n) −
γ + log ρ − log 2
log λ(2)
−
1
2
+ o(1),
où λ(2) et ρ sont des constantes positives définies en (7.42) et (7.43) et où
Q(u) est une fonction périodique d’amplitude « très petite » (généralement
plus petite que 10 −4 pour les sources usuelles).
De plus, la distribution asymptotique de la hauteur est de type double
exponentielle en k,
lim
n→∞
sup
k≥0
Pn(h < k) − exp
−ρn
2 λ(2)
k
= 0.
Remarque 7.47 Dans le cas binaire sans mémoire non biaisée,
λ(2) = ρ =
1
2
,
ce qui redonne le résultat de la proposition 7.42.
7.3 Mise en perspective
Nous avons vu dans ce chapitre quelques méthodes analytiques pour étudier en
moyenne les principaux paramètres de trie.
Tout d’abord, d’un point de vue algorithmique, les résultats de ce chapitre
montrent que la structure de trie est efficace : elle permet en moyenne de chercher
une clé avec un coût logarithmique tout en nécessitant un espace linéaire en le
nombre de clés. Nous insistons sur le fait que ce coût logarithmique pour les tries
n’est pas directement comparable à celui obtenu pour la recherche dans les arbres
binaires de recherche. Dans un abr on compte le nombre de comparaisons de clés,
alors que dans un trie, on compte le nombre de comparaisons de symboles (qui
constituent les clés).
Des expériences sur l’anglais (en supprimant la ponctuation) donnent une
bonne adéquation entre analyse et expérimentation (voir l’exemple de Moby Dick
d’Herman Melville dans [45] sur une structure plus générale de trie dit hybride, où
en chaque nœud interne du trie nous considérons une structure de donnée simple –
liste, abr, tableau – pour accéder à ses enfants).
7 Arbres digitaux
Proposition 7.46 (Hauteur asymptotique du trie (cas général)) Pour un
trie construit sur n clés produites par une source (satisfaisant certaines
hypothèses assez générales non détaillées ici), l’espérance de la hauteur
vérifie quand n → +∞
E n [h] =
2
| log λ(2)|
log n + Q(log n) −
γ + log ρ − log 2
log λ(2)
−
1
2
+ o(1),
où λ(2) et ρ sont des constantes positives définies en (7.42) et (7.43) et où
Q(u) est une fonction périodique d’amplitude « très petite » (généralement
plus petite que 10 −4 pour les sources usuelles).
De plus, la distribution asymptotique de la hauteur est de type double
exponentielle en k,
lim
n→∞
sup
k≥0
Pn(h < k) − exp
−ρn
2 λ(2)
k
= 0.
Remarque 7.47 Dans le cas binaire sans mémoire non biaisée,
λ(2) = ρ =
1
2
,
ce qui redonne le résultat de la proposition 7.42.
7.3 Mise en perspective
Nous avons vu dans ce chapitre quelques méthodes analytiques pour étudier en
moyenne les principaux paramètres de trie.
Tout d’abord, d’un point de vue algorithmique, les résultats de ce chapitre
montrent que la structure de trie est efficace : elle permet en moyenne de chercher
une clé avec un coût logarithmique tout en nécessitant un espace linéaire en le
nombre de clés. Nous insistons sur le fait que ce coût logarithmique pour les tries
n’est pas directement comparable à celui obtenu pour la recherche dans les arbres
binaires de recherche. Dans un abr on compte le nombre de comparaisons de clés,
alors que dans un trie, on compte le nombre de comparaisons de symboles (qui
constituent les clés).
Des expériences sur l’anglais (en supprimant la ponctuation) donnent une
bonne adéquation entre analyse et expérimentation (voir l’exemple de Moby Dick
d’Herman Melville dans [45] sur une structure plus générale de trie dit hybride, où
en chaque nœud interne du trie nous considérons une structure de donnée simple –
liste, abr, tableau – pour accéder à ses enfants).