“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 138 — #148
i
i
i
i
i
i
i
i
138
3
• Techniques de programmation déclarative
Chaque sorte d’arbre a sa propre classe d’algorithmes pour les construire, les traverser et en chercher des informations. Dans cette section nous nous limitons aux arbres
binaires. Nous définissons des arbres binaires ordonnés et nous montrons comment
insérer des informations, chercher des informations et enlever des informations de ces
arbres.
a) Les arbres binaires ordonnés
Un arbre binaire ordonné OBTree est un arbre binaire dans lequel chaque nœud non
feuille contient une paire de valeurs :
OBTree : := leaf
| tree(OValue Value OBTree 1 OBTree 2 )
Chaque nœud non feuille contient les valeurs OValue et Value. La première valeur
OValue est un sous-type de Value qui est totalement ordonné, c’est-à-dire qui a des
fonctions de comparaison booléennes. Par exemple, Int (le type des entiers) est une
possibilité. La deuxième valeur Value est entraînée avec l’autre. Elle n’est soumise à
aucune condition particulière.
La première valeur est la clé et la deuxième valeur contient les informations. Un
arbre binaire est ordonné si pour chaque nœud non feuille, toutes les clés du premier
sous-arbre sont plus petites que la clé du nœud, et toutes les clés du deuxième sousarbre sont plus grandes que la clé du nœud.
b) L’enregistrement des informations dans les arbres
Un arbre binaire ordonné peut être utilisé comme un entrepôt d’informations si nous
définissons trois opérations : recherche, insertion et retrait d’éléments.
Chercher des informations dans un arbre binaire ordonné veut dire vérifier si la
clé est présente dans un des nœuds de l’arbre, et si c’est le cas, renvoyer les informations présentes dans ce nœud. Avec la condition d’ordre, l’algorithme de recherche
peut éliminer la moitié des nœuds restants à chaque pas. Cette technique s’appelle la
recherche binaire. Elle a besoin d’un nombre d’opérations proportionnel à la profondeur de l’arbre, la longueur du plus long chemin de la racine vers une feuille. Voici
une routine qui implémente cette recherche :
fun {Lookup X T}
case T of leaf then notfound
[] tree(Y V T1 T2) then
if X
else found(V) end
end
end
i
i
i
i
i
i
i
i
138
3
• Techniques de programmation déclarative
Chaque sorte d’arbre a sa propre classe d’algorithmes pour les construire, les traverser et en chercher des informations. Dans cette section nous nous limitons aux arbres
binaires. Nous définissons des arbres binaires ordonnés et nous montrons comment
insérer des informations, chercher des informations et enlever des informations de ces
arbres.
a) Les arbres binaires ordonnés
Un arbre binaire ordonné OBTree est un arbre binaire dans lequel chaque nœud non
feuille contient une paire de valeurs :
OBTree : := leaf
| tree(OValue Value OBTree 1 OBTree 2 )
Chaque nœud non feuille contient les valeurs OValue et Value. La première valeur
OValue est un sous-type de Value qui est totalement ordonné, c’est-à-dire qui a des
fonctions de comparaison booléennes. Par exemple, Int (le type des entiers) est une
possibilité. La deuxième valeur Value est entraînée avec l’autre. Elle n’est soumise à
aucune condition particulière.
La première valeur est la clé et la deuxième valeur contient les informations. Un
arbre binaire est ordonné si pour chaque nœud non feuille, toutes les clés du premier
sous-arbre sont plus petites que la clé du nœud, et toutes les clés du deuxième sousarbre sont plus grandes que la clé du nœud.
b) L’enregistrement des informations dans les arbres
Un arbre binaire ordonné peut être utilisé comme un entrepôt d’informations si nous
définissons trois opérations : recherche, insertion et retrait d’éléments.
Chercher des informations dans un arbre binaire ordonné veut dire vérifier si la
clé est présente dans un des nœuds de l’arbre, et si c’est le cas, renvoyer les informations présentes dans ce nœud. Avec la condition d’ordre, l’algorithme de recherche
peut éliminer la moitié des nœuds restants à chaque pas. Cette technique s’appelle la
recherche binaire. Elle a besoin d’un nombre d’opérations proportionnel à la profondeur de l’arbre, la longueur du plus long chemin de la racine vers une feuille. Voici
une routine qui implémente cette recherche :
fun {Lookup X T}
case T of leaf then notfound
[] tree(Y V T1 T2) then
if X
else found(V) end
end
end