“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 141 — #151
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
141
d’un des sous-arbres. L’idée est de prendre la plus petite clé de T2, appelée Yp, et
d’en faire la racine de l’arbre réorganisé. Les nœuds restants de T2 font un sous-arbre
plus petit, appelée Tp, qui est placé dans l’arbre réorganisé. Cela garantit que l’arbre
réorganisé est toujours ordonné, puisque par construction toutes les clés de T1 sont
plus petites que Yp, qui est plus petite que toutes les clés de Tp.
Il est intéressant de voir ce qui se passe quand nous enlevons la racine à plusieurs
reprises. Cela va « évider » l’arbre de l’intérieur, en enlevant de plus en plus la partie
gauche de T2. Finalement, le sous-arbre de gauche de T2 est enlevé complètement et
le sous-arbre de droite prend sa place. En continuant, T2 rétrécit de plus en plus, en
passant par des étapes intermédiaires dans lesquelles il est toujours plus petit, tout en
restant un arbre binaire ordonné. À un moment donné il disparaît complètement.
Pour implémenter la correction, nous utilisons une fonction {RemoveSmallest
T2} qui renvoie la clé la plus petite de T2, sa valeur associée et un nouvel arbre qui
n’a pas cette clé. Avec cette fonction nous pouvons écrire une version correcte de
Delete :
fun {Delete X T}
case T of leaf then leaf
[] tree(Y W T1 T2) andthen X==Y then
case {RemoveSmallest T2} of none then T1
[] Yp#Vp#Tp then tree(Yp Vp T1 Tp) end
[] tree(Y W T1 T2) andthen X
[] tree(Y W T1 T2) andthen X>Y then
tree(Y W T1 {Delete X T2})
end
end
La fonction RemoveSmallest renvoie soit un triple Yp#Vp#Tp soit l’atome none.
Voici une définition récursive :
fun {RemoveSmallest T}
case T of leaf then none
[] tree(Y V T1 T2) then
case {RemoveSmallest T1} of none then Y#V#T2
[] Yp#Vp#Tp then Yp#Vp#tree(Y V Tp T2) end
end
end
Une autre possibilité serait de prendre l’élément le plus grand de T1 au lieu de
l’élément le plus petit de T2. Le résultat final serait similaire.
La difficulté supplémentaire de Delete par rapport à Insert ou Lookup se
produit souvent avec des algorithmes sur les arbres. Cela arrive parce que le fait d’être
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
141
d’un des sous-arbres. L’idée est de prendre la plus petite clé de T2, appelée Yp, et
d’en faire la racine de l’arbre réorganisé. Les nœuds restants de T2 font un sous-arbre
plus petit, appelée Tp, qui est placé dans l’arbre réorganisé. Cela garantit que l’arbre
réorganisé est toujours ordonné, puisque par construction toutes les clés de T1 sont
plus petites que Yp, qui est plus petite que toutes les clés de Tp.
Il est intéressant de voir ce qui se passe quand nous enlevons la racine à plusieurs
reprises. Cela va « évider » l’arbre de l’intérieur, en enlevant de plus en plus la partie
gauche de T2. Finalement, le sous-arbre de gauche de T2 est enlevé complètement et
le sous-arbre de droite prend sa place. En continuant, T2 rétrécit de plus en plus, en
passant par des étapes intermédiaires dans lesquelles il est toujours plus petit, tout en
restant un arbre binaire ordonné. À un moment donné il disparaît complètement.
Pour implémenter la correction, nous utilisons une fonction {RemoveSmallest
T2} qui renvoie la clé la plus petite de T2, sa valeur associée et un nouvel arbre qui
n’a pas cette clé. Avec cette fonction nous pouvons écrire une version correcte de
Delete :
fun {Delete X T}
case T of leaf then leaf
[] tree(Y W T1 T2) andthen X==Y then
case {RemoveSmallest T2} of none then T1
[] Yp#Vp#Tp then tree(Yp Vp T1 Tp) end
[] tree(Y W T1 T2) andthen X
[] tree(Y W T1 T2) andthen X>Y then
tree(Y W T1 {Delete X T2})
end
end
La fonction RemoveSmallest renvoie soit un triple Yp#Vp#Tp soit l’atome none.
Voici une définition récursive :
fun {RemoveSmallest T}
case T of leaf then none
[] tree(Y V T1 T2) then
case {RemoveSmallest T1} of none then Y#V#T2
[] Yp#Vp#Tp then Yp#Vp#tree(Y V Tp T2) end
end
end
Une autre possibilité serait de prendre l’élément le plus grand de T1 au lieu de
l’élément le plus petit de T2. Le résultat final serait similaire.
La difficulté supplémentaire de Delete par rapport à Insert ou Lookup se
produit souvent avec des algorithmes sur les arbres. Cela arrive parce que le fait d’être
© Dunod – La photocopie non autorisée est un délit