Exercice 1 [Arbres binaires]

Chaque nœud d'un arbre polymorphe possède une valeur, un sous-arbre gauche et un sous-arbre droit.

1. Définir bintree le type des arbres binaires polymorphes
2. Écrire la fonction values: 'a bintree -> 'a list qui renvoie l'ensemble des valeurs présentes dans un arbre (avec doublons). Les valeurs apparaîtront dans l'ordre suivant : racine, sous-arbre gauche puis sous-arbre droit. Vous définirez et utiliserez une fonction auxiliaire afin d'éviter les concaténations de liste.
3. Écrire la fonction map_tree: ('a -> 'b) -> 'a bintree -> 'b bintree qui renvoie un arbre dans lequel toutes les valeurs ont été remplacées par leur image par la fonction donnée en premier argument.
4. Écrire la fonction fold_tree: ('a -> 'b -> 'b) -> 'a bintree -> 'b -> 'b qui est la fonction équivalente à List.fold_right pour les arbres binaires. L'exploration de l'arbre est faite dans l'ordre suivant : sous-arbre droit, racine puis sous-arbre gauche.

Exercice 2 [Arbres binaires de recherche]

1. Définir abr le type des arbres binaires de recherche polymorphes.
2. Donner des constructeurs intelligents pour le type abr. Ces constructeurs devront permettre de respecter la structure d'abr. On utilisera la fonction de comparaison générique Pervasives.compare pour les comparaisons.
3. Écrire la fonction values: 'a bintree -> 'a list qui renvoie l'ensemble des valeurs présentes dans un arbre (avec doublons). Les valeurs apparaîtront dans l'ordre suivant : racine, sous-arbre gauche puis sous-arbre droit. Vous définirez et utiliserez une fonction auxiliaire afin d'éviter les concaténations de liste.
4. Écrire la fonction de recherche d'une valeur dans un abr. Cette fonction aura le type 'a -> 'a abr -> bool.
5. Redéfinir les fonctions map_tree et fold_tree pour les abr.
6. On appelle coupure d'un abr a suivant une valeur v la séparation de cet abr en deux abr a1 et a2 tels que tous les éléments de a1 sont inférieurs ou égaux à v et tous ceux de a2 sont strictement supérieurs à v et tels que le multi-ensemble des éléments de a1 et a2 est celui des éléments de a.
   Écrire une fonction coupure permettant de réaliser la coupure d'un abr suivant une valeur. Cette fonction ne devra parcourir qu'une (partie) d'une branche de l'abr.
7. Proposer une fonction de fusion de deux abr utilisant la fonction de coupure.
8. Proposer une fonction permettant de retirer un élément d'un abr. Cette fonction retournera l'arbre passé en argument si la valeur n'est pas présente dans cet arbre.
9. L'un des problèmes majeurs des abr est leur tendance à dégénerer en liste (entraînant un accroissement de complexité à l'ajout et lors de la recherche).
   Proposer une fonction create : int -> int abr permettant de créer un abr résultant de l'ajout des entiers entre 0 et n (où n est le paramètre de la fonction) dans cet ordre (moralement create n = add n (add (n-1) .... (add 0 empty))).
   Tester cette fonction avec un entier grand (de l'ordre de 10000) expliquer rapidement la raison du temps d'exécution.

Exercice 3 [AVL]

Afin de palier le problème des abr nous allons maintenant équilibrer nos arbres.

1. Définir avl le type des arbres AVL polymorphes.
2. Donner des constructeurs intelligents pour le type abr. Ces constructeurs devront permettre de respecter la structure d'AVL. On utilisera la fonction de comparaisons générique compare pour les comparaisons.
3. Reprendre les questions de l'exercice 2 pour les AVL.