80
3 Arbres, algorithmes et données
trouvent dans les deux sous-arbres de l’arbre de racine x ; les cas d’arrêt des appels
récursifs sont également les mêmes : sous-tableau vide ou avec une seule clé, vs.
sous-arbre vide ou avec une seule clé. C’est pourquoi la longueur de cheminement
externe d’un arbre binaire de recherche est parfois appelée « coût du tri rapide ».
Attention : lors des appels récursifs ultérieurs, les sous-suites, celle du soustableau gauche (resp. droit) sur lequel travaille l’algorithme PARTITION, et celle
qui servira à construire le sous-arbre gauche (resp. droit), ne sont en général plus les
mêmes : l’algorithme PARTITION ne conserve pas l’ordre relatif des clés plus petites
(resp. plus grandes) que le pivot. En particulier ce ne seront pas nécessairement les
mêmes clés qui seront utilisées comme pivot lors des appels à PARTITION sur les
deux sous-tableaux, et qui seront racines des deux sous-arbres de l’arbre binaire
de recherche en cours de construction. Nous donnons dans les figures 3.15 et 3.16
un exemple ; nous voyons que, si les sous-arbres de la racine et les sous-tableaux
sont bien composés des mêmes éléments, les pivots – qui seront donc racines des
sous-arbres apparaissant à l’étape suivante – ne sont pas les racines des sous-arbres
de l’arbre binaire de recherche construit en insérant les clés dans l’ordre du tableau
initial.
15 3 7 18 22 9 4
3
18
9 4
7
22
15
10
10
4; 3; 7
22
9
10
15; 18
Fig. 3.15 En haut, un tableau de 8 éléments, avant (à gauche) et après (à droite) l’exécution de
l’algorithme PARTITION, dans lequel la clé 10 sert de pivot. Les pivots lors du premier appel de
PARTITION (tableau de gauche) et lors des deux appels récursifs à venir (tableau de droite) sont
indiqués en rouge. En bas, l’arbre binaire obtenu en plaçant le pivot 10 à la racine, puis les deux clés
9 et 22, respectivement pivots des sous-tableaux gauche et droite, comme racines des sous-arbres
gauche et droit ; le tri n’est pas terminé
10
3
1 5
7
9
4
18
22
Fig. 3.16 L’arbre binaire de recherche obtenu par insertions successives des clés du tableau de
gauche de la figure 3.15. Les sous-suites qui servent à la construction des sous-arbres gauche et
droit sont respectivement 3, 7, 9, 4 et 15, 18, 22
3 Arbres, algorithmes et données
trouvent dans les deux sous-arbres de l’arbre de racine x ; les cas d’arrêt des appels
récursifs sont également les mêmes : sous-tableau vide ou avec une seule clé, vs.
sous-arbre vide ou avec une seule clé. C’est pourquoi la longueur de cheminement
externe d’un arbre binaire de recherche est parfois appelée « coût du tri rapide ».
Attention : lors des appels récursifs ultérieurs, les sous-suites, celle du soustableau gauche (resp. droit) sur lequel travaille l’algorithme PARTITION, et celle
qui servira à construire le sous-arbre gauche (resp. droit), ne sont en général plus les
mêmes : l’algorithme PARTITION ne conserve pas l’ordre relatif des clés plus petites
(resp. plus grandes) que le pivot. En particulier ce ne seront pas nécessairement les
mêmes clés qui seront utilisées comme pivot lors des appels à PARTITION sur les
deux sous-tableaux, et qui seront racines des deux sous-arbres de l’arbre binaire
de recherche en cours de construction. Nous donnons dans les figures 3.15 et 3.16
un exemple ; nous voyons que, si les sous-arbres de la racine et les sous-tableaux
sont bien composés des mêmes éléments, les pivots – qui seront donc racines des
sous-arbres apparaissant à l’étape suivante – ne sont pas les racines des sous-arbres
de l’arbre binaire de recherche construit en insérant les clés dans l’ordre du tableau
initial.
15 3 7 18 22 9 4
3
18
9 4
7
22
15
10
10
4; 3; 7
22
9
10
15; 18
Fig. 3.15 En haut, un tableau de 8 éléments, avant (à gauche) et après (à droite) l’exécution de
l’algorithme PARTITION, dans lequel la clé 10 sert de pivot. Les pivots lors du premier appel de
PARTITION (tableau de gauche) et lors des deux appels récursifs à venir (tableau de droite) sont
indiqués en rouge. En bas, l’arbre binaire obtenu en plaçant le pivot 10 à la racine, puis les deux clés
9 et 22, respectivement pivots des sous-tableaux gauche et droite, comme racines des sous-arbres
gauche et droit ; le tri n’est pas terminé
10
3
1 5
7
9
4
18
22
Fig. 3.16 L’arbre binaire de recherche obtenu par insertions successives des clés du tableau de
gauche de la figure 3.15. Les sous-suites qui servent à la construction des sous-arbres gauche et
droit sont respectivement 3, 7, 9, 4 et 15, 18, 22