“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 139 — #149
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
139
L’appel de {Lookup X T} renvoie found(V) si un nœud avec X est trouvé et
notfound sinon. Une autre manière d’écrire Lookup est avec andthen dans
l’instruction case :
fun {Lookup X T}
case T of leaf then notfound
[] tree(Y V T1 T2) andthen X==Y then found(V)
[] tree(Y V T1 T2) andthen X [] tree(Y V T1 T2) andthen X>Y then {Lookup X T2}
end
end
Beaucoup de développeurs considèrent la deuxième manière plus lisible parce qu’elle
est plus visuelle : elle donne des formes qui montrent à quoi ressemble l’arbre au lieu
de donner des instructions pour le décomposer. En un mot, c’est plus déclaratif. Cela
facilite la vérification de son exactitude. Il est plus facile de s’assurer qu’aucun cas
n’a été oublié. Dans les algorithmes plus compliqués sur les arbres, la correspondance
de formes avec andthen a un avantage définitif sur les instructions if explicites.
Pour insérer ou enlever des informations dans un arbre binaire ordonné, nous
construisons un nouvel arbre qui est identique à l’original sauf qu’il a plus ou moins
d’informations. Voici l’opération d’insertion :
fun {Insert X V T}
case T of leaf then tree(X V leaf leaf)
[] tree(Y W T1 T2) andthen X==Y then
tree(X V T1 T2)
[] tree(Y W T1 T2) andthen X tree(Y W {Insert X V T1} T2)
[] tree(Y W T1 T2) andthen X>Y then
tree(Y W T1 {Insert X V T2})
end
end
L’appel {Insert X V T} renvoie un nouvel arbre qui a la paire (X V) insérée au
bon endroit. Si T contient déjà X, le nouvel arbre remplacera les vieilles informations
par V.
c) Le retrait et la réorganisation de l’arbre
L’opération de retrait peut sembler surprenante. Voici une première tentative :
© Dunod – La photocopie non autorisée est un délit