A Rappels algorithmiques
409
Fonction supprimerRacine(Arbre A)
// Précondition : A est un arbre binaire de recherche non vide.
// Postcondition : Retourne l’arbre binaire de recherche obtenu en
supprimant la valeur contenue à la racine puis en réorganisant l’arbre.
// Variables locales : Arbre B, Arbre temp
si A.gauche == None alors
A = A.droit
sinon
si A.droit == None alors
A = A.gauche
sinon
B = A.gauche
si B.droit == None alors
A.clé = B.clé
A.gauche = B.gauche
sinon
temp = B.droit
tant que temp.droit != None faire
B = temp
temp = temp.droit
A.clé = temp.clé
B.droit = temp.gauche
retourner A
A.2.4 Coupure et insertion à la racine
Dans certains cas, il peut être pertinent d’insérer une clé X dans un arbre binaire
de recherche A au niveau non pas d’une feuille, mais de la racine. Pour cela, nous
utiliserons l’opération de coupure, qui détruit l’arbre initial et renvoie deux arbres
binaires de recherche G et D, tels que G contient les clés de A inférieures ou égales
à X, et D les clés de A strictement supérieures à X.
Nous présentons dans la figure A.7 un exemple de coupure d’un arbre binaire de
recherche suivant une clé (non présente dans l’arbre), ici prise égale à 26, puis dans
la figure A.8 les deux arbres binaires de recherche qui en résultent : les liens de 15
à 30, de 30 à 25 et de 25 à 28 ont été détruits, puis les liens de 15 à 25 et de 30 à 28
ont été recréés. Ces deux arbres binaires de recherche deviendront ensuite les deux
sous-arbres du nouvel arbre de recherche créé lors de l’insertion à la racine de la clé
26 ; cf. la figure A.9.