“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 140 — #150
i
i
i
i
i
i
i
i
140
3
• Techniques de programmation déclarative
fun {Delete X T}
case T of leaf then leaf
[] tree(Y W T1 T2) andthen X==Y then leaf
[] tree(Y W T1 T2) andthen X tree(Y W {Delete X T1} T2)
[] tree(Y W T1 T2) andthen X>Y then
tree(Y W T1 {Delete X T2})
end
end
L’appel {Delete X T} doit renvoyer un nouvel arbre qui n’a pas de nœud avec
la clé X. Si T ne contient pas X, T sera renvoyé sans changement. Le retrait semble
simple, mais cette définition est fausse. Voyez-vous le problème ?
Il s’avère que Delete n’est pas aussi simple que Lookup ou Insert. L’erreur
dans cette définition est quand X==Y tout le sous-arbre sera enlevé au lieu d’un seul
nœud. Ce n’est correct que quand le sous-arbre est dégénéré, c’est-à-dire quand T1
et T2 sont tous les deux des nœuds feuilles. La correction n’est pas complètement
évidente : quand X==Y nous devons réorganiser le sous-arbre pour qu’il ne contienne
plus la clé Y mais reste un arbre binaire ordonné. Il y a deux cas, illustrés dans les
figures 3.11 et 3.12.
feuille
T1
Y
T1
Figure 3.11 Le retrait du nœud Y quand un sous-arbre est une feuille (cas simple).
Y
Yp
?
Y p
Enlever Y
T2
T1
T2
T1
Tp
Monter Yp
La plus petite
T2 moins Yp
clé de T2
T1
Figure 3.12 Le retrait du nœud Y quand aucun sous-arbre n’est une feuille (cas difficile).
La figure 3.11 est le cas simple, quand un sous-arbre est une feuille. L’arbre réorganisé est simplement l’autre sous-arbre. La figure 3.12 est le cas difficile, quand
aucun sous-arbre n’est une feuille. Comment remplissons-nous le trou qui reste après
le retrait de Y ? Une autre clé doit prendre la place de Y, « montant » de l’intérieur