410
A Rappels algorithmiques
Fig. A.7 Coupure d’un
arbre binaire de recherche
suivant la clé 26
Fig. A.8 Les deux arbres
binaires de recherche obtenus
après coupure. Les liens
indiqués en vert ont été créés
pour reconstituer deux arbres
Fig. A.9 Insertion de la clé
26 à la racine de l’arbre de la
figure A.7
Fonction couper(élément X, Arbre A)
// Précondition : A est un arbre binaire de recherche.
// Postcondition : Retourne deux arbres binaires de recherche G et D, déduits
de l’arbre initial A (qui a été détruit) par coupure suivant la clé X.
// Utilise : couper
// Variables locales : Arbre G, Arbre D
si A == None alors
retourner (None, None)
sinon
si X ≤ A.clé alors
(G , A.gauche) = couper(X, A.gauche)
D = A
sinon
(A.droit, D) = couper(X, A.droit)
G = A
retourner (G , D)
Une fois l’arbre binaire de recherche A coupé suivant la clé X, il ne reste plus
qu’à mettre cette clé X dans un nouveau nœud, puis à lui rattacher les arbres
G comme fils gauche, et D comme fils droit, pour obtenir un arbre binaire de