1.Définition

Une arborescence binaire de recherche est construite sur un ensemble E muni d'une relation d'ordre R.

Une arborescence binaire vide V est une arborescence binaire de recherche.

Un noeud N(e, sag, sad) est une arborescence binaire de recherche si et seulement si

sag et sad sont des arborescences binaires de recherche,
toute étiquette e' de sag vérifie e' R e et
toute étiquette e' de sad ne vérifie pas e' R e.

2.Implantation

On définit le type ocaml suivant pour représenter une une arborescence binaire :

type 'a ab = V | N of 'a * 'a ab * 'a ab ;;

et le type ocaml suivant pour représenter une arborescence binaire de recherche :

type 'a abr = {inf : 'a -> 'a -> bool ; ab : 'a ab} ;;

3.Création d'une arborescence binaire de recherche vide

Donner une définition de la fonction vide telle que (vide rel), lorsque rel est une relation d'ordre sur le type des étiquettes, retourne la représentation d'une arborescence de recherche vide.

4.Insertion d'un élément dans une arborescence binaire de recherche

Donner une définition de la fonction ins telle que (ins e a) retourne une arborescence binaire de recherche contenant toutes les étiquettes de l'arborescence binaire de recherche a et l'étiquette e insérée en feuille.

5.Recherche d'un élément dans une arborescence binaire de recherche

Donner une définition de la fonction member telle que (member x a) retourne true si et seulement si l'élément x est égal à une étiquette de l'arborescence binaire de recherche a.

6.Liste des étiquettes en ordre infixe

Donner une définition de la fonction to_list telle que (to_list a) retourne la liste des étiquettes de l'arborescence binaire de recherche a, liste ordonnée suivant le parcours infixe de l'arborescence.

7.Essais

Déclarer un tableau v de 20 éléments contenant, en ordre croissant, les entiers de 0 à 19.
Modifier le tableau v pour obtenir une permutation par tirage aléatoire de tous ses éléments.
Construire une arborescence binaire de recherche a à partir du tableau v permuté.
Déclarer la liste l résultant de l'application (to_list a).

8.Suppression d'un élément

Nous travaillons temporairement sur le champ ab d'une arborescence binaire de recherche.

8.1.Plus grand élément

Donner une définition de la fonction max : 'a ab -> 'a telle que (max a.ab) retourne la plus grande étiquette de l'arborescence binaire de recherche a ou lève l'exception Invalid_argument "max" si l'arbre a.ab est vide.

8.2.Suppression du plus grand élément

Donner une définition de la fonction sauf_max : 'a ab -> 'a ab telle que (sauf_max a.ab) retourne l'arbre a.ab amputé de sa plus grande étiquette ou lève l'exception Invalid_argument "sauf_max" si l'arbre a.ab est vide.

8.3.Les deux résultats en un seul parcours

En vous aidant des définitions précédantes, donner une définition directe de la fonction max_saufMax : 'a ab -> 'a * 'a ab telle que (max_saufMax a.ab) retourne le doublet :

plus grande étiquette de l'arbre a.ab,
arbre a.ab amputé de sa plus grande étiquette

ou lève l'exception Invalid_argument "max_saufMax" si l'arbre a.ab est vide.

8.4.Suppression de l'étiquette à la racine

Pour supprimer l'étiquette en racine d'un arbre a.ab d'une arborescence binaire de recherche a non vide, il suffit de "faire remonter" la plus grande étiquette de son sous-arbre gauche - si elle existe - à la racine (ou la plus petite étiquette de son sous_arbre droit).

Donner une définition de la fonction sauf_rac : 'a ab -> 'a ab telle que (sauf_rac a.ab)retourne l'arbre d'une arborescence binaire de recherche contenant toutes les étiquettes de a sauf celle à la racine de a ou lève l'exception Invalid_argument "sauf_rac" si l'arbre a.ab est vide.

8.5.Suppression d'une étiquette

Pour cette étape finale, on travaille à nouveau sur une arborescence binaire de recherche.

Donner une définition de la fonction sauf_elem : 'a -> 'a abr -> 'a abr telle que (sauf_elem x a) retourne une arborescence binaire de recherche issue de a par suppression d'une étiquette égale à x ou lève l'exception Not_found si une telle étiquette n'existe pas dans a.