84
3 Arbres, algorithmes et données
la classe d’équivalence de f est exactement la longueur de la branche. Le coût
minimal, resp. maximal, d’exécution sur des données de taille n est donc la longueur
de la plus courte, resp. plus longue, branche, c’est-à-dire le niveau de saturation de τ ,
resp. sa hauteur.
Quant au coût moyen, sous le modèle des permutations uniformes pour les
tableaux il peut lui aussi être obtenu simplement à partir de τ : c’est simplement le
quotient lce(τ )/|∂τ |, 15 i.e., la profondeur moyenne d’une feuille, lorsque les classes
d’équivalence sont de taille 1 ; sinon nous pondérons la profondeur de chaque feuille
par la taille de la classe d’équivalence qui l’étiquette.
Sur l’exemple de la figure 3.17, la plus petite longueur de branche est égale à 3,
la plus grande à 5, la longueur de cheminement externe (qui n’est ici pas pertinente,
puisque les feuilles sont étiquetées par des classes de cardinalité 2! ou 6!) est égale
à 31, et la longueur de cheminement externe, pondérée par les tailles des classes
d’équivalence, à 90. Cela nous dit que l’algorithme PARTITION, exécuté sur un
tableau de 4 éléments distincts, effectue toujours entre 3 et 5 comparaisons, et que
le nombre moyen de comparaisons, sous la loi des permutations uniformes sur les
tableaux, vaut
90
4! = 3,75.
Arbre de décision associé à un algorithme de tri par comparaison
Soit τ (n, A) l’arbre de décision associé à un algorithme de tri par comparaison A
s’exécutant sur un tableau de n clés toutes distinctes. Les feuilles de τ (n, A) sont
marquées par le résultat de l’exécution de l’algorithme sur un tableau T [1 . . n], i.e.,
par le réordonnement σ obtenu à la fin du tri – de la même manière que, sur l’arbre
de la figure 3.17 relatif à l’algorithme PARTITION, la feuille la plus à gauche est
marquée par σ (4)σ (2)σ (3)σ (1), c’est-à-dire par x 4 x 2 x 3 x 1 .
Lemme 3.12 L’arbre de décision τ (n, A) correspondant à l’exécution d’un algorithme A de tri par comparaison sur n clés distinctes a exactement n! feuilles.
Preuve Si le tableau en entrée de l’algorithme est T 0 = [σ (1), . . . , σ (n)], le tableau
trié est [σ −1 ◦ σ (1), . . . , σ −1 ◦ σ (n)] = [1, . . . , n], et chaque permutation σ
conduit donc à une feuille de τ (n, A) marquée par σ −1 : l’arbre τ (n, A) a au
plus Card(S n ) = n! feuilles ; une permutation ne peut marquer qu’une feuille au
plus. Une autre manière de voir qu’une permutation ne marque qu’une feuille au
plus est la suivante : si une permutation marque (au moins) deux feuilles, prenons
le plus petit ancêtre commun de ces deux feuilles ; en ce nœud l’exécution de
l’algorithme aurait conduit à poursuivre dans les deux sous-arbres gauche et droit,
i.e., la comparaison marquant ce nœud serait à la fois vraie et fausse.
Si maintenant un arbre de décision a (strictement) moins de n! feuilles, une
au moins des classes d’équivalence de R A marquant les feuilles a au moins deux
éléments, i.e., deux permutations. Dans un tel cas, le tri n’est pas fini, et l’arbre ne
15 Nous rappelons que ∂τ est l’ensemble des feuilles de τ .
3 Arbres, algorithmes et données
la classe d’équivalence de f est exactement la longueur de la branche. Le coût
minimal, resp. maximal, d’exécution sur des données de taille n est donc la longueur
de la plus courte, resp. plus longue, branche, c’est-à-dire le niveau de saturation de τ ,
resp. sa hauteur.
Quant au coût moyen, sous le modèle des permutations uniformes pour les
tableaux il peut lui aussi être obtenu simplement à partir de τ : c’est simplement le
quotient lce(τ )/|∂τ |, 15 i.e., la profondeur moyenne d’une feuille, lorsque les classes
d’équivalence sont de taille 1 ; sinon nous pondérons la profondeur de chaque feuille
par la taille de la classe d’équivalence qui l’étiquette.
Sur l’exemple de la figure 3.17, la plus petite longueur de branche est égale à 3,
la plus grande à 5, la longueur de cheminement externe (qui n’est ici pas pertinente,
puisque les feuilles sont étiquetées par des classes de cardinalité 2! ou 6!) est égale
à 31, et la longueur de cheminement externe, pondérée par les tailles des classes
d’équivalence, à 90. Cela nous dit que l’algorithme PARTITION, exécuté sur un
tableau de 4 éléments distincts, effectue toujours entre 3 et 5 comparaisons, et que
le nombre moyen de comparaisons, sous la loi des permutations uniformes sur les
tableaux, vaut
90
4! = 3,75.
Arbre de décision associé à un algorithme de tri par comparaison
Soit τ (n, A) l’arbre de décision associé à un algorithme de tri par comparaison A
s’exécutant sur un tableau de n clés toutes distinctes. Les feuilles de τ (n, A) sont
marquées par le résultat de l’exécution de l’algorithme sur un tableau T [1 . . n], i.e.,
par le réordonnement σ obtenu à la fin du tri – de la même manière que, sur l’arbre
de la figure 3.17 relatif à l’algorithme PARTITION, la feuille la plus à gauche est
marquée par σ (4)σ (2)σ (3)σ (1), c’est-à-dire par x 4 x 2 x 3 x 1 .
Lemme 3.12 L’arbre de décision τ (n, A) correspondant à l’exécution d’un algorithme A de tri par comparaison sur n clés distinctes a exactement n! feuilles.
Preuve Si le tableau en entrée de l’algorithme est T 0 = [σ (1), . . . , σ (n)], le tableau
trié est [σ −1 ◦ σ (1), . . . , σ −1 ◦ σ (n)] = [1, . . . , n], et chaque permutation σ
conduit donc à une feuille de τ (n, A) marquée par σ −1 : l’arbre τ (n, A) a au
plus Card(S n ) = n! feuilles ; une permutation ne peut marquer qu’une feuille au
plus. Une autre manière de voir qu’une permutation ne marque qu’une feuille au
plus est la suivante : si une permutation marque (au moins) deux feuilles, prenons
le plus petit ancêtre commun de ces deux feuilles ; en ce nœud l’exécution de
l’algorithme aurait conduit à poursuivre dans les deux sous-arbres gauche et droit,
i.e., la comparaison marquant ce nœud serait à la fois vraie et fausse.
Si maintenant un arbre de décision a (strictement) moins de n! feuilles, une
au moins des classes d’équivalence de R A marquant les feuilles a au moins deux
éléments, i.e., deux permutations. Dans un tel cas, le tri n’est pas fini, et l’arbre ne
15 Nous rappelons que ∂τ est l’ensemble des feuilles de τ .