412
A Rappels algorithmiques
Fig. A.11 Les (sous)-arbres
à fusionner récursivement G
et D 1
Fig. A.12 Les sous-arbres à
fusionner G 2 et D 1
Fig. A.13 Les sous-arbres à
fusionner G 3 et D 1
Fig. A.14
L’arbre D 2
D avec le sous-arbre droit de G (fusion droite). Supposons par exemple que nous
choisissions la fusion gauche : nous allons fusionner G avec le fils gauche de D,
appelons-le D 1 . Supposons ensuite que la fusion de G et de D 1 (cf. la figure A.11)
appelle la fusion droite, i.e., du sous-arbre droit de G, notons-le G 2 , avec D 1 (cf. la
figure A.12). Continuons ainsi en choisissant aléatoirement de faire à la troisième
étape une fusion droite de G 3 , sous-arbre droit de G 2 , avec D 1 (cf. figure A.13), puis
une fusion gauche, et enfin une dernière fusion droite qui nous amènera à fusionner
un arbre vide à gauche, avec un arbre D 2 (représenté en figure A.14) dont la racine
contient la clé 15, et l’unique feuille, la clé 16. En revenant des appels récursifs,
nous trouvons ensuite successivement l’arbre obtenu par fusion de G 3 et D 2 , de G 3
et D 1 , G 2 et D 1 , de G et D 1 (cf. figure A.15), et enfin l’arbre global, fusion de G et
D (cf. figure A.16).