408
A Rappels algorithmiques
Fig. A.6 À gauche, suppression de la clé à la racine dans l’arbre binaire de recherche de la
figure A.4 par la fonction supprimerRacine : la plus grande clé du sous-arbre gauche, 0, va à la
racine ; à droite, l’arbre obtenu après suppression
A.2.3 Suppression d’une clé
L’algorithme de suppression d’une clé X travaille en deux temps : recherche de
l’emplacement de X, faite par la fonction supprimer, puis suppression effective de
X, qui est alors à la racine d’un sous-arbre, par la fonction supprimerRacine. Nous
donnons ci-dessous d’abord une version récursive de la fonction supprimer, puis
la fonction supprimerRacine. Celle-ci se contente de retourner l’arbre vide si la
racine est une feuille et l’unique sous-arbre (droit ou gauche) si la racine est un nœud
simple. Lorsque la racine est un nœud double, elle y met comme clé la plus grande
clé du sous-arbre gauche (qui est alors supprimée de ce sous-arbre), et retourne la
racine dont la clé et le sous-arbre gauche ont donc été modifiés (figure A.6).
Fonction supprimer(élément X, Arbre A)
// Précondition : A est un arbre binaire de recherche.
// Postcondition : Retourne l’arbre initial si X n’y est pas présent, et sinon
l’arbre binaire de recherche obtenu par suppression de la première
occurrence de X rencontrée.
// Utilise : supprimer, supprimerRacine
si A == None alors
retourner A
si A.clé == X alors
retourner supprimerRacine(A)
sinon
si A.clé > X alors
A.gauche = supprimer(X, A.gauche)
sinon
A.droit = supprimer(X, A.droit)
retourner A