type arbre =
  | F
  | N of arbre * int * arbre;;

(* QUESTION 1 ============================================================== *)

let test = N (N (F,3,F), 5, N (F,8,F));;

let rec profondeur = function
  | F -> 0
  | N (g,_,d) -> max (profondeur g) (profondeur d) + 1;;

let valeurs a =
  let rec aux l = function
    | F -> l
    | N (g,v,d) -> aux (v :: aux l d) g
  in aux [] a;;

(* QUESTION 2 ============================================================== *)

let rec insere e = function
  | F -> N (F,e,F)
  | N (g,v,d) -> 
      if e > v then N (g,v,insere e d)
      else N (insere e g,v,d);;

let test2 = list_it insere [28; 3; 9; 18; 16; 33; 9] F;;

let rec cherche e = function
  | F -> false
  | N (g,v,d) -> e = v 
  || e < v && cherche e g 
  || e > v && cherche e d;;

(* QUESTION 3 ============================================================== *)

let rec supprime_minimal = function
  | F -> failwith "Pas de minimal"
  | N (F,v,d) -> v, d
  | N (g,v,d) -> 
      let r, a = supprime_minimal g in
      r, N (a,v,d);;

let rec supprime e = function
  | F -> F
  | N (g,v,d) -> 
      if e < v then N (supprime e g,v,d)
      else if e > v then N (g,v,supprime e d)
      else if d = F then g
      else let r, a = supprime_minimal d in
      N (g,r,a);;

let test3 = list_it supprime [3; 33; 16; 9] test2;;

(* QUESTION 4 ============================================================== *)

(* On souhaite d'abord déterminer que la transformation I est bijective. 
   Pour cela, on montre qu'elle est:

   - Surjective: si w est un mot contenant n-1 fois a et n+1 fois b, il 
                 est de la forme ubv où u est un mot de Dyck (puisqu'il 
                 contient deux b qui ne peuvent être associés à un a), 
                 et w = I(ubv')

   - Injective: supposons que I(ubv) = I(xby), avec u et x deux mots de 
                Dyck. Cela implique que u = x, puisque x ne peut être un
                préfixe strict de u (xb ne peut être préfixe d'aucun mot
                de Dyck). Par conséquent, l'égalité implique que ubv' = uby'
                et donc que v = y. 

   Cela montre donc que l'ensemble des mots non de Dyck est en bijection avec
   A(n-1,n+1). Et donc, le nombre de mots de Dyck est |A(n,n) - A(n-1,n+1)|,
   soit: 1/(n+1) C(2n,n)
*)

(* QUESTION 5 ============================================================== *)

(* La deuxième étape est d'établir une bijection entre les mots de Dyck et
   les arbres binaires. On procède par une étape intermédiaire. Pour cela,
   on montre que la transformation J est bijective: 

   - Surjective: si on considère un arbre donné, on peut le parcourir dans
                 l'ordre, écrire a en rencontrant un noeud pour la première 
                 fois et b en le rencontrant pour la dernière fois. Le 
                 résultat est un mot de Dyck (chaque b est associé au a du 
                 même noeud) qui permet la reconstruction inverse (a pour 
                 créer, b pour quitter).

   - Injective: supposons J(u) = J(v). Si u <> v, il existe un point où 
                J rencontre un 'a' dans u et un 'b' dans v (tout ayant été
                identique jusque-là. Alors, pour v, l'algorithme interrompt
                la construction du noeud en cours, qui se retrouve 
                définitivement figé au nombre de fils actuel. Pour u, 
                l'algorithme ajoute au moins un fils. Les deux arbres seront
                alors différents. Donc u = v.

   Une fois cette preuve effectuée, on montre une bijection entre des arbres
   généraux et des 1,2-arbres. Pour cela, on rebranche le premier fils de 
   chaque noeud à gauche de ce noeud, et le premier frère à droite. Il s'agit
   d'une bijection dont l'inversion est évidente.

   Enfin, pour mettre en bijection les 1,2-arbres et les arbres binaires, on 
   ajoute des feuilles aux 0-noeuds et 1-noeuds pour obtenir un arbre binaire
   à n+1 feuilles.
*)

(* QUESTION 6 ============================================================== *)

(* Le nombre d'arbres d'une certaine taille. *)
let rec catalan n = 
  if n <= 0 then 1 
  else
    catalan (n-1) * 2 * (2*n + 1) / (n+1);;

type a = Zero | Deux of a * a;;

let rec aleatoire n =
  if n <= 0 then Zero else
  let combien = catalan n in
  let lequel = ref (random __ int combien) 
  and i = ref 0 in
  (    
    while !lequel > 0 do
      lequel := !lequel - (catalan !i) * (catalan (n - !i - 1));
      incr i
    done; 
    Deux (aleatoire (!i-1),aleatoire (n - !i))
  );;

aleatoire 10;;

(* Affichage des arbres à valeurs ========================================== *)

let affiche a = 
  let i = ref 0 in
  let rec aux p = function
    | F -> 
        printf __ printf "  node [label=\"\"]; %d; %d -> %d; \n" !i p !i; 
        incr i
    | N (g,v,d) -> 
        let j = !i in
        printf __ printf "  node [label=\"%d\"]; %d; %d -> %d; \n" v j p j;
        incr i;
        aux j g;
        aux j d
  in 
  printf __ printf "digraph G {\n  node [shape=\"circle\"];\n";
  match a with
    | F -> printf __ printf "  node [label = \"\"]; 0;\n}\n"
    | N (g,v,d) -> 
        let j = !i in 
        printf __ printf "  node [label=\"%d\"]; %d; \n" v j;
        incr i;
        aux j g;
        aux j d;
        printf __ printf "}\n";;

affiche test2;;

(* QUESTION DIFFICILE ====================================================== *)

type m_arbre = 
{
  gauche : m_arbre option ref;
  droite : m_arbre option ref;
  mutable valeur : int;
};;

let rec m_insere e = function 
  | ref None as a -> a := Some { 
      gauche = ref None;
      droite = ref None;
      valeur = e }
  | ref (Some s) -> 
        if e < s.valeur then m_insere e s.gauche
        else m_insere e s.droite;;

let rec m_cherche e = function
  | ref None -> false
  | ref (Some s) ->
      if e < s.valeur then m_cherche e s.gauche
      else if e > s.valeur then m_cherche e s.droite
      else true;;

let m_valeurs a = 
  let rec aux l = function
    | ref None -> l
    | ref (Some s) ->
        aux (s.valeur :: aux l s.droite) s.gauche
  in aux [] a;;

let vide () = ref None;;

let test4 = 
  let a = vide () in 
  do_list (fun x -> m_insere x a) 
    [ 16; 18; 9; 3; 9; 33; 28 ];
  a;;

let rec m_supprime_gauche = function
  | ref None -> failwith "Pas de minimum"
  | ref (Some s) as a -> 
      if (!(s.gauche) = None) then (a := !(s.droite); s.valeur)
      else m_supprime_gauche s.gauche;;

let rec m_supprime e = function
  | ref None -> ()
  | ref (Some s) as a ->
      if s.valeur = e then 
        if !(s.gauche) = None then a := !(s.droite)
        else s.valeur <- m_supprime_gauche s.gauche
      else if s.valeur < e then 
        m_supprime e s.droite
      else 
        m_supprime e s.gauche;;

let rec m_clone = function
  | ref None -> ref None
  | ref (Some s) -> ref (Some { 
      droite = m_clone s.droite;
      gauche = m_clone s.gauche;
      valeur = s.valeur });;

let test5 = 
  let a = m_clone test4 in
  do_list (fun i -> m_supprime i a) [3; 33; 16; 9];
  a;;