1.2 Arbres marqués
25
Fig. 1.23 Les étapes de la construction d’un 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, insérées dans cet ordre. Les possibilités
d’insertion sont représentées par des
Construction statique
Soit n ≥ 1 et soient n clés x 1 , . . . , x n prises dans un ensemble totalement ordonné
L’abr de taille n associé à ces n clés prises dans cet ordre est construit de la façon
suivante :
– la clé x 1 est la marque de la racine ;
– le sous-arbre gauche est l’abr associé à {x 1 , . . . , x n } ∩ ≤x 1 , où nous avons posé
≤x 1 = {x ∈ x ≤ x 1 } ;
– le sous-arbre droit est l’abr associé à {x 1 , . . . , x n }∩ >x 1 , où >x 1 = {x ∈ x >
x 1 } ;
– lorsque l’une des opérations précédentes produit l’ensemble vide, le sous-arbre
est réduit à
Commentaire combinatoire
Reprenons la construction algorithmique dynamique ci-dessus, lorsque les clés
x 1 , . . . , x n sont supposées toutes distinctes. Nous avons vu (c’est la définition 1.17)
qu’à tout n-uplet (x 1 , . . . , x n ) est associée la permutation σ n ∈ S n , appelée
réordonnement de x 1 , . . . , x n , définie par :
x σ n (1) < x σ n (2) < · · · < x σ n (n) .
(1.8)