A Rappels algorithmiques
411
recherche, déduit de A en insérant X à la racine ; c’est la fonction insérerRacine
ci-dessous.
Fonction InsertionRacine(élément X, arbre A)
// Précondition : A est un arbre binaire de recherche.
// Postcondition : Retourne l’arbre binaire de recherche obtenu en insérant la
clé X à la racine dans A.
// Utilise : couper, créerFeuille, nouveau
// Variable locale : Arbre B
si A == None alors
retourner créerFeuille(X)
sinon
B = nouveau()
B.clé = X
(B.gauche, B.droit) = couper(X, A)
retourner B
A.2.5 Fusion de deux arbres binaires de recherche
et suppression
La fusion est en quelque sorte l’inverse de la coupure : elle prend en entrée deux
arbres binaires de recherche G et D tels que toutes les clés de G soient strictement
inférieures à toutes les clés de D, et construit récursivement un nouvel arbre binaire
de recherche contenant toutes leurs clés. Nous commençons par présenter le principe
de l’algorithme sur un exemple, avant de donner la fonction fusionner. Nous
étudions ensuite la manière dont cet algorithme de fusion permet d’implémenter
un nouvel algorithme de suppression d’une clé dans un arbre binaire de recherche,
donné par la fonction supprimerFusion.
Partons des arbres G et D de la figure A.10, de tailles respectives 9 et 8,
et choisissons aléatoirement (par appel à une fonction tirerAléa, que nous ne
précisons pas davantage ici ; nous y reviendrons en section A.2.6) de fusionner, soit
G avec le sous-arbre gauche de D (nous appellerons ceci la fusion gauche), soit
Fig. A.10 Deux arbres binaires de recherche à fusionner : G (à gauche) et D (à droite)