414
A Rappels algorithmiques
Nous pouvons maintenant donner l’algorithme de fusion de deux arbres binaires
de recherche ; c’est la fonction fusionner ci-après.
Fonction fusionner(Arbre G, Arbre D)
// Précondition : G et D sont deux arbres binaires de recherche, tels que
toutes les clés de G soient strictement inférieures à toutes les clés de D.
// Postcondition : Retourne un arbre binaire de recherche, construit à partir
des arbres initiaux G et D (qui ont été détruits) et contenant leurs clés.
// Utilise : fusionner, tirerAléa (qui renvoie une valeur prise dans
{gauche, droite})
si G == None alors
retourner D
sinon
si D == None alors
retourner G
sinon
si tirerAléa() == gauche alors
G.droit = fusionner(G.droit, D)
retourner G
sinon
D.gauche = fusionner(G , D.gauche)
retourner D
À partir de cet algorithme de fusion de deux arbres binaires de recherche, il est
simple d’obtenir une alternative à l’algorithme classique de suppression d’une clé
X :
– tout comme pour la suppression classique, la première partie de l’algorithme est
simplement la recherche récursive de l’emplacement de la clé X à supprimer ;
– une fois trouvée cette valeur à la racine d’un (sous-)arbre A il suffit d’appeler,
au lieu de la fonction supprimerRacine, la fonction fusionner sur les sousarbres gauche et droit de A, qui – bien évidemment – vérifient la propriété d’ordre
des clés préalable à la fusion.