(** Le type des arbres binaires. *)
type 'a ab = V | N of 'a * 'a ab * 'a ab ;;

(** Le type des arbres binaires de recherche. *)
type 'a abr = {inf : 'a -> 'a -> bool ; ab : 'a ab} ;;

(** [vide inf] retourne une arborescence de recherche vide, construite
  sur la relation [inf] spécifiée.   *)
let vide r = {inf = r ; ab = V} ;;

let t = vide ( < ) ;;

(** [insere x abr] retourne l'arborescence binaire de recherche obtenue par
  insertion de l'élément x dans l'ABR [abr]. *)
let insere x a =
  let rec ins_x = function
      V -> N (x, V, V)
    | N (e, ag, ad) ->
	if a.inf x e then N (e, ins_x ag, ad)
	else N (e, ag, ins_x ad)
  in {a with ab = ins_x a.ab} ;;

let t5 = insere 5 t ;;
let t15 = insere 1 t5 ;;
let t157 = insere 7 t15 ;;

(** [member x abr] retourne [true] SSI x a au moins une occurrence dans l'ABR
  [abr]. *)
let member x a =
  let rec mem_x = function
      V -> false
    | N (e, ag, ad) ->
	x = e || if a.inf x e then mem_x ag else mem_x ad
  in mem_x a.ab ;;

member 1 t157 ;;
member 0 t157 ;;

(** [to_list abr] retourne la liste des étiquettes de l'ABR [abr], liste
  ordonnée selon le parcours infixe de l'arbre. *)
let to_list abr =
  let rec tl = function
      V -> []
    | N (e, ag, ad) -> tl ag @ (e :: tl ad)
  in tl abr.ab ;;

to_list t157 ;;

(** [max abr.ab] retourne le plus grand élément (au sens de [abr.inf]) de
  l'arbre binaire [abr.ab] d'une ABR [abr] ;
  lève l'exception Invalid_argument "max" si l'arbre [abr.ab] est vide. *)
let max =
  let rec max = function
      N (e, _, V) -> e
    | N (_, _, ad) -> max ad
    | _ -> raise Exit
  in function
      V -> invalid_arg "max"
    | a -> max a ;;

max t157.ab ;;