Un ABR (arbre binaire de recherche) est un arbre tel que pour chaque noeud x, tous les éléments du sous-arbre gauche ont une valeur inférieure à x et tous les éléments du sous-arbre droit ont une valeur supérieure à x. Nous utiliserons dans les exercices suivants le type
Écrire une fonction ins_abr : (’a -> ’a -> bool) -> ’a -> ’a bin_tree -> ’a bin_tree telle que ins_abr f x t insère l’élément x dans l’arbre t en utilisant la fonction de comparaison f.
Écrire une fonction abr_of_list : (’a -> ’a -> bool) -> ’a list -> ’a bin_tree telle que abr_of_list f l retourne un arbre contenant tous les éléments de l, disposés avec la fonction f.
Écrire la fonction list_of_abr : ’a bin_tree -> ’a list retournant une liste contenant les éléments de l’arbre passé en paramètre.
Écrire une fonction tri_liste : (’a -> ’a -> bool) -> ’a list -> ’a list qui trie la liste passée en paramètre à l’aide d’un ABR.
Nous utiliserons le type suivant pour représenter des fonctions simples :
Écrire une fonction str_of_exp : exp -> string telle que str_of_exp e retourne une représentation sous forme de chaîne de caractères de l’expression e.
Écrire une fonction image : exp -> int -> int telle que image e x retourne l’image de x par la fonction e.
Écrire une fonction derive : exp -> exp retournant la dérivée de l’expression passée en paramètre.
Écrire une fonction degre : exp -> int retournant le degré du polynôme représenté par l’expression passée en paramètre.