3.3 Tri d’un ensemble de clés
87
x2 < x1
x3 < x1
x3 < x1
1
x
>
4
x
1
x
<
4
x
x4 > x1
x3 > x1
*
*
1
2
*
*
*
4
1
*
*
2
*
*
4
3
*
1
*
2
*
*
*
1
*
4
*
3
4
*
*
3
non
oui
n
o
n
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
x2 x1 x3 x4
x4 x2 x1 x3
x1 x2 x3 x4
x3 x1 x2 x4
x3 x4 x1 x2
x4 x1 x3 x2
Fig. 3.19
L’arbre de décision τ (4, P artition)
de la figure 3.18, une fois les branches filiformes compactées. Les feuilles sont toujours marquées à la fois par
les tableaux initial et final