88
3 Arbres, algorithmes et données
Fig. 3.20 Un arbre parfait
de hauteur h : ses feuilles sont
sur les deux derniers niveaux
Pour un arbre parfait non saturé et de hauteur h, son nombre N de feuilles vérifie
2 h−1 < N < 2 h et donc h = =log 2 N. Supposons maintenant que cet arbre ait N −
p feuilles au dernier niveau et p feuilles à l’avant-dernier niveau (cf. la figure 3.20) :
sa longueur de cheminement est égale à (N − p)h + p(h − 1) = Nh − p =
Nlog 2 N − p. Il suffit maintenant de voir que 0 ≤ p ≤ N − 1 (p = 0 correspond
au cas de l’arbre saturé) pour obtenir la proposition suivante.
Proposition 3.13
i) La longueur de cheminement externe d’un arbre binaire parfait τ à N feuilles
vérifie Nlog 2 N − N + 1 ≤ lce(τ ) ≤ Nlog 2 N (les valeurs inférieure et
supérieure étant respectivement atteintes pour l’arbre ayant une seule feuille à
l’avant-dernier niveau et pour l’arbre saturé).
ii) La longueur de cheminement externe d’un arbre binaire à N feuilles est
supérieure ou égale à Nlog 2 N − N + 1.
Optimalité en moyenne du tri rapide
La proposition 3.13 nous permet de terminer la preuve de la proposition 3.9. Un
arbre de décision τ (n, A) ayant n! feuilles (cf. le lemme 3.12), sa longueur de
cheminement externe est au minimum égale à n!!log 2 n!! − n! + 1, et la profondeur
moyenne d’une feuille est alors log 2 n!! − 1 + 1/n!. Nous terminons en appliquant
la formule de Stirling pour obtenir le développement asymptotique de n! (cf. la
section B.5.1), ce qui donne log 2 n! = n log 2 n(1 + o(1)), et finalement l’équivalent
asymptotique de la profondeur moyenne d’une feuille de τ (n, A) : c’est bien
n log 2 n, comme annoncé.
Variantes algorithmiques du tri rapide
Nous terminons l’examen du tri rapide en mentionnant, pour les algorithmiciens, quelques variantes susceptibles d’améliorer ses performances pratiques. Une
référence intéressante pour cette partie est la thèse de Hennequin [129], qui examine
en détail différentes variantes, ainsi que leur influence sur le coût de l’algorithme
de tri.
3 Arbres, algorithmes et données
Fig. 3.20 Un arbre parfait
de hauteur h : ses feuilles sont
sur les deux derniers niveaux
Pour un arbre parfait non saturé et de hauteur h, son nombre N de feuilles vérifie
2 h−1 < N < 2 h et donc h = =log 2 N. Supposons maintenant que cet arbre ait N −
p feuilles au dernier niveau et p feuilles à l’avant-dernier niveau (cf. la figure 3.20) :
sa longueur de cheminement est égale à (N − p)h + p(h − 1) = Nh − p =
Nlog 2 N − p. Il suffit maintenant de voir que 0 ≤ p ≤ N − 1 (p = 0 correspond
au cas de l’arbre saturé) pour obtenir la proposition suivante.
Proposition 3.13
i) La longueur de cheminement externe d’un arbre binaire parfait τ à N feuilles
vérifie Nlog 2 N − N + 1 ≤ lce(τ ) ≤ Nlog 2 N (les valeurs inférieure et
supérieure étant respectivement atteintes pour l’arbre ayant une seule feuille à
l’avant-dernier niveau et pour l’arbre saturé).
ii) La longueur de cheminement externe d’un arbre binaire à N feuilles est
supérieure ou égale à Nlog 2 N − N + 1.
Optimalité en moyenne du tri rapide
La proposition 3.13 nous permet de terminer la preuve de la proposition 3.9. Un
arbre de décision τ (n, A) ayant n! feuilles (cf. le lemme 3.12), sa longueur de
cheminement externe est au minimum égale à n!!log 2 n!! − n! + 1, et la profondeur
moyenne d’une feuille est alors log 2 n!! − 1 + 1/n!. Nous terminons en appliquant
la formule de Stirling pour obtenir le développement asymptotique de n! (cf. la
section B.5.1), ce qui donne log 2 n! = n log 2 n(1 + o(1)), et finalement l’équivalent
asymptotique de la profondeur moyenne d’une feuille de τ (n, A) : c’est bien
n log 2 n, comme annoncé.
Variantes algorithmiques du tri rapide
Nous terminons l’examen du tri rapide en mentionnant, pour les algorithmiciens, quelques variantes susceptibles d’améliorer ses performances pratiques. Une
référence intéressante pour cette partie est la thèse de Hennequin [129], qui examine
en détail différentes variantes, ainsi que leur influence sur le coût de l’algorithme
de tri.