86
3 Arbres, algorithmes et données
x2 < x1
x3 < x1
x3 < x1
1
x
>
4
x
1
x
<
4
x
x4 > x1
x3 > x1
*
1
*
2
*
4
*
3
4
*
*
3
*
*
*
4
non
oui
i
u
o
n
o
n
i
u
o
oui
non
oui
non
oui
non
oui
non
4
x
1
x
2
x
3
x
1
x
3
x
2
x
4
x
x4 x2 x1 x3
x3 x1 x2 x4
x3 > x1
x2 > x1
2 1 * *
x2 x1 x3 x4
1 * * *
1 x2 x3 x4
x2 < x1
x3 > x1
x2 > x1
non : echange de T[2]
x4 > x1
2 * * 1
x4 x1 x3 x2
x3 > x1
3 4 * *
x3 x4 x1 x2
Fig. 3.18
L’arbre de décision τ (4, P artition)
de la figure 3.17, auquel nous avons ajouté un deuxième marquage des feuilles (qui n’appartient pas à l’arbre
de décision proprement dit) : une feuille est aussi marquée par le tableau T
1 obtenu après l’exécution de PARTITION.
Ainsi, pour ce deuxième marquage la
notation x
4 x
2 x
3 x
1 signifie que le tableau a été réordonné de telle sorte que les premier et quatrième éléments x
1 et x
4 ont été échangés, et que les deuxième et
troisième éléments x
2 et x
3 sont restés à leur place. De même pour les autres marquages de feuilles. L’algorithme peut conduire à refaire des comparaisons déjà
effectuées, d’où des chemins filiformes dans l’arbre. Enfin, nous avons indiqué lorsque l’algorithme PARTITION
échange deux clés – pour une taille de tableau
n
= 4, cela ne se produit que pour les quatre permutations de la forme 34
∗ ∗ ou 2
∗ ∗1