26
1 Botanique
Fig. 1.24 À gauche, l’abr τ construit avec les clés x 1 = 0,3 ; x 2 = 0,1 ; x 3 = 0,4 ; x 4 =
0,15 ; x 5 = 0,9 ; x 6 = 0,02 ; x 7 = 0,2, au milieu son arbre des rangs C(τ ) ; à droite sa forme π(τ ).
Ici x 6 < x 2 < x 4 < x 7 < x 1 < x 3 < x 5 et donc le réordonnement est σ n = (6, 2, 4, 7, 1, 3, 5) et
σ −1
n = (5, 2, 6, 3, 7, 1, 4)
Fig. 1.25 Un arbre binaire de recherche obtenu par insertions successives des clés 0,4 ; 0,8 ; 0,3 ;
0,1 ; 0,35 ; 0,93 ; 0,9 ; 0,39 dans un arbre initialement vide
Ainsi, la permutation σ n trie les clés, de sorte que le parcours symétrique d’un arbre
binaire de recherche τ fournit les clés triées selon l’ordre croissant. La permutation
σ −1
n
donne les rangs des clés, comme l’illustre la figure 1.24. L’arbre binaire
de recherche obtenu par insertions successives de σ −1
n (x 1 ), . . . , σ −1
n (x n ) est aussi
l’arbre des rangs C(τ ) obtenu par le marquage canonique de la définition 1.16. Il
a la même forme que celle de l’arbre binaire de recherche construit sur les clés
x 1 , . . . , x n .
Remarque 1.33 Différentes suites de clés (ou différentes permutations) peuvent
donner le même arbre binaire de recherche. Par exemple, l’insertion des clés 0,4 ;
0,8 ; 0,3 ; 0,1 ; 0,35 ; 0,93 ; 0,9 ; 0,39 donne l’arbre de la figure 1.25. Cet arbre a
le même arbre des rangs et donc la même forme d’arbre que dans la figure 1.24.