3.3 Tri d’un ensemble de clés
85
peut pas être un arbre de décision pour un algorithme de tri. C’est par exemple ce
qui se passe pour la première feuille de l’arbre de décision – pour l’algorithme
PARTITION et non pour le tri rapide – donné dans la figure 3.18 : cette feuille
correspond aux six permutations 4 ∗ ∗ ∗ telles que la plus grande clé soit en tête :
le tableau final étiquetant la feuille est x 4 x 2 x 3 x 1 , qui est non trié dans 5 cas sur 6
et où seul x 1 est assuré d’être à la bonne place après l’exécution de la partition
(figure 3.19).
Par définition de l’arbre de décision associé à un algorithme de tri A, chaque
chemin de la racine vers une feuille dans l’arbre τ (n, A) correspond à l’exécution
de A sur l’unique permutation associée à cette feuille (les classes d’équivalence
associés aux feuilles sont toutes de taille 1) et sa longueur est le nombre de
comparaisons faites par l’algorithme sur le tableau des n éléments donné par la
permutation. Remarquons à ce propos que l’algorithme peut refaire des comparaisons déjà effectuées, nous l’avons vu sur l’exemple de la figure 3.17, ou bien faire
des comparaisons inutiles, par exemple comparer deux valeurs x et y sur un chemin
où il a déjà vérifié que x < z et z < y pour une troisième valeur z : un arbre de
décision, tel que donné dans la définition 3.11, n’est pas nécessairement complet.
Sous le modèle des permutations uniformes pour les tableaux, chaque feuille de
l’arbre τ (n, A) a la même probabilité 1/n!, et le nombre moyen de comparaisons
fait par l’algorithme A est égal à la moyenne de la profondeur d’une feuille, soit
lce(τ (n, A))/n!. Il se pose donc la question d’évaluer la longueur de cheminement
externe lce(τ (n, A)), ou plus exactement d’en obtenir une borne inférieure qui soit
valable pour tout algorithme A. Cela sera donné par la longueur de cheminement
minimale d’un arbre binaire avec un nombre de feuilles donné, que nous allons
maintenant étudier.
Longueur de cheminement externe minimale d’un arbre binaire
La longueur de cheminement externe d’un arbre binaire avec un nombre de feuilles
donné est minimale lorsque l’arbre est le plus « compact » possible, avec ses feuilles
sur deux niveaux, et donc, quitte à supposer que les feuilles du dernier niveau sont le
plus à gauche possible, 16 lorsque l’arbre est complet ou avec un unique nœud simple
à l’avant-dernier niveau ; c’est ce que nous avons appelé dans la définition 1.26 un
arbre parfait (cf. la figure 3.20). Soit donc τ un arbre binaire, et soit τ l’arbre obtenu
en compactant ses branches filiformes, et en réordonnant ses feuilles de façon à
obtenir un arbre parfait : lce( τ ) ≤ lce(τ ).
Regardons tout d’abord le cas où τ est l’arbre saturé (cf. la définition 1.26) de
hauteur h, et notons N le nombre de ses feuilles, qui sont toutes à la profondeur
maximale : N = 2 h . Sa longueur de cheminement externe est h N = N log 2 N.
16 Cette étape n’est pas essentielle, mais facilite la formulation de notre raisonnement ultérieur sur
les différents types de nœuds de l’arbre.
85
peut pas être un arbre de décision pour un algorithme de tri. C’est par exemple ce
qui se passe pour la première feuille de l’arbre de décision – pour l’algorithme
PARTITION et non pour le tri rapide – donné dans la figure 3.18 : cette feuille
correspond aux six permutations 4 ∗ ∗ ∗ telles que la plus grande clé soit en tête :
le tableau final étiquetant la feuille est x 4 x 2 x 3 x 1 , qui est non trié dans 5 cas sur 6
et où seul x 1 est assuré d’être à la bonne place après l’exécution de la partition
(figure 3.19).
Par définition de l’arbre de décision associé à un algorithme de tri A, chaque
chemin de la racine vers une feuille dans l’arbre τ (n, A) correspond à l’exécution
de A sur l’unique permutation associée à cette feuille (les classes d’équivalence
associés aux feuilles sont toutes de taille 1) et sa longueur est le nombre de
comparaisons faites par l’algorithme sur le tableau des n éléments donné par la
permutation. Remarquons à ce propos que l’algorithme peut refaire des comparaisons déjà effectuées, nous l’avons vu sur l’exemple de la figure 3.17, ou bien faire
des comparaisons inutiles, par exemple comparer deux valeurs x et y sur un chemin
où il a déjà vérifié que x < z et z < y pour une troisième valeur z : un arbre de
décision, tel que donné dans la définition 3.11, n’est pas nécessairement complet.
Sous le modèle des permutations uniformes pour les tableaux, chaque feuille de
l’arbre τ (n, A) a la même probabilité 1/n!, et le nombre moyen de comparaisons
fait par l’algorithme A est égal à la moyenne de la profondeur d’une feuille, soit
lce(τ (n, A))/n!. Il se pose donc la question d’évaluer la longueur de cheminement
externe lce(τ (n, A)), ou plus exactement d’en obtenir une borne inférieure qui soit
valable pour tout algorithme A. Cela sera donné par la longueur de cheminement
minimale d’un arbre binaire avec un nombre de feuilles donné, que nous allons
maintenant étudier.
Longueur de cheminement externe minimale d’un arbre binaire
La longueur de cheminement externe d’un arbre binaire avec un nombre de feuilles
donné est minimale lorsque l’arbre est le plus « compact » possible, avec ses feuilles
sur deux niveaux, et donc, quitte à supposer que les feuilles du dernier niveau sont le
plus à gauche possible, 16 lorsque l’arbre est complet ou avec un unique nœud simple
à l’avant-dernier niveau ; c’est ce que nous avons appelé dans la définition 1.26 un
arbre parfait (cf. la figure 3.20). Soit donc τ un arbre binaire, et soit τ l’arbre obtenu
en compactant ses branches filiformes, et en réordonnant ses feuilles de façon à
obtenir un arbre parfait : lce( τ ) ≤ lce(τ ).
Regardons tout d’abord le cas où τ est l’arbre saturé (cf. la définition 1.26) de
hauteur h, et notons N le nombre de ses feuilles, qui sont toutes à la profondeur
maximale : N = 2 h . Sa longueur de cheminement externe est h N = N log 2 N.
16 Cette étape n’est pas essentielle, mais facilite la formulation de notre raisonnement ultérieur sur
les différents types de nœuds de l’arbre.