A Rappels algorithmiques
413
Fig. A.15 En haut, de
gauche à droite : les arbres
obtenus par fusion de G 3 et
D 2 , de G 3 et D 1 , de G 2 et
D 1 . En bas : l’arbre obtenu
par fusion de G et D 1
Fig. A.16 L’arbre final
obtenu par fusion de G et D.
Remarquons que la coupure
de ce dernier arbre par une
clé, par exemple 14, comprise
strictement entre la plus
grande clé de G et la plus
petite clé de D, redonne les
deux arbres initiaux G et D :
les opérations de fusion et de
coupure sont deux opérations
inverses l’une de l’autre