type 'a avl = Vide | N of int * 'a avl * 'a * 'a avl ;;

let exemple_1 =
 N
  (3, N (1, N (0, Vide, 0, Vide), 1, N (0, Vide, 2, Vide)), 3,
   N
    (2, N (1, N (0, Vide, 4, Vide), 5, N (0, Vide, 6, Vide)), 7,
     N (1, N (0, Vide, 8, Vide), 9, N (0, Vide, 10, Vide))))
and  exemple_2 =
 N
  (4, N (0, Vide, 0, Vide), 1,
   N
    (3, N (0, Vide, 2, Vide), 3,
     N
      (2, N (1, N (0, Vide, 4, Vide), 5, N (0, Vide, 6, Vide)), 7,
       N (1, N (0, Vide, 8, Vide), 9, N (0, Vide, 10, Vide)))))
and exemple_3 =
 N
  (2, N (1, N (0, Vide, 0, Vide), 1, N (0, Vide, 2, Vide)), 3,
   N
    (2, N (1, N (0, Vide, 4, Vide), 5, N (0, Vide, 6, Vide)), 7,
     N (1, N (0, Vide, 8, Vide), 9, N (0, Vide, 10, Vide))))
;;

(* Question 1 *)

let rec enum_infixe a = match a with
  | Vide -> []
  | N(_,g,x,d) -> (enum_infixe g)@[x]@(enum_infixe d)
;;

enum_infixe exemple_1 ;;

(* Question 2 *)

let rec est_croissante_strict l = match l with
  | [_] | [] -> true
  | x::y::q -> x<y && est_croissante_strict (y::q)
;;

(* Question 3 *)

let check_abr a = est_croissante_strict (enum_infixe a) ;;

check_abr exemple_1 && check_abr exemple_2 && check_abr exemple_3 ;;

(* Question 4 *)

let ha a = match a with
  | Vide -> -1
  | N(h,_,_,_) -> h
;;

ha exemple_3 ;;

(* Question 5 *)

let ha_bis a = match a with
  | Vide -> -1
  | N(_,g,_,d) -> 1+ max (ha g) (ha d)
;;

ha_bis exemple_3 ;;

let recalc_ha a = match a with
  | Vide -> Vide
  | N(_,g,x,d) -> N(ha_bis a, g,x,d)
;;

recalc_ha exemple_3 = exemple_1 ;;

(* Question 6 *)

(* Un arbre vérifie la propriété d'AVL s'il est vide, ou si :
 * - ses sous-arbres gauche et droit sont des AVL ;
 * - la différence de hauteurs entre les deux est d'au plus 1 ;
 * - le champ hauteur correspond bien à sa hauteur. *)

let rec check_avl a = match a with
  | Vide -> true
  | N(h,g,_,d) -> check_avl g && check_avl d &&
                  abs (ha g - ha d) <= 1 &&
                  h = 1 + max (ha g) (ha d)
;;

check_avl exemple_1 ;;

check_avl exemple_2 || check_avl exemple_3 ;;

(* Question 7 *)

let rotation_d a = match a with
  | N(_, N(_,alpha,y,beta),x,gamma) ->
      recalc_ha (N(0,alpha,y, recalc_ha (N(0,beta,x,gamma))))
  | _ -> failwith "rotation droite impossible"
;;

rotation_d exemple_1 = exemple_2 ;;

(* Question 8 *)

let rotation_g a = match a with
  | N(_,alpha,y,N(_,beta,x,gamma)) ->
      recalc_ha (N(0, (recalc_ha (N(0,alpha,y,beta))),x,gamma))
  | _ -> failwith "rotation gauche impossible"
;;

rotation_g exemple_2 = exemple_1 ;;

(* Question 9 *)

let equilibrer a = match a with
  | N(_,g,x,d) when ha g = ha d + 2 ->
    begin
      match g with
      | N(_,alpha,y,beta) when ha alpha >= ha beta -> rotation_d a
      | _ -> rotation_d (N(0,rotation_g g,x,d))
    end
  | N(_,g,x,d) when ha d = ha g + 2 ->
    begin
      match d with
      | N(_,alpha,y,beta) when ha beta >= ha alpha -> rotation_g a
      | _ -> rotation_g (N(0,g,x,rotation_d d))
    end
  | _ -> recalc_ha a
;;

(* Question 10 *)

let rec max_abr a = match a with
  | Vide -> failwith "vide"
  | N(_,_,x,Vide) -> x
  | N(_,_,_,d) -> max_abr d
;;

max_abr exemple_1 ;;

(* Question 11 *)

let rec inserer a x = match a with
  | Vide -> N(0,Vide,x,Vide)
  | N(h,g,y,d) when y = x -> a
  | N(h,g,y,d) when y<x -> equilibrer (N(h,g,y,inserer d x))
  | N(h,g,y,d) -> equilibrer (N(h,inserer g x,y,d))
;;

let rec supprimer a x = match a with
  | Vide -> Vide
  | N(_,g,y,d) when y>x -> equilibrer (N(0,supprimer g x,y,d))
  | N(_,g,y,d) when y<x -> equilibrer (N(0,g,y,supprimer d x))
  | N(_,Vide,y,d) -> d
  | N(_,g,y,d) -> let z = max_abr g in equilibrer (N(0,supprimer g z,z,d))
;;

(* Question 12 *)

let b = ref true in
let a = ref Vide in
for i=0 to 100 do
  a := inserer !a i ;
  b := !b && check_avl !a && check_abr !a
done ;
for i=0 to 100 do
  a := supprimer !a i ;
  b := !b && check_avl !a && check_abr !a
done ;
!b ;;

(* Question 13 *)

type 'a arbre = Vide | N of 'a arbre * 'a * 'a arbre ;;

let exemple_4 =
 N
  (N (N (N (Vide, 3, Vide), 7, Vide), 9, N (N (Vide, 1, Vide), 5, Vide)), 10,
   N (N (N (Vide, 2, Vide), 6, Vide), 8, N (N (Vide, 0, Vide), 4, Vide)))
and exemple_5 =
 N
  (N (N (N (Vide, 7, Vide), 3, Vide), 9, N (N (Vide, 1, Vide), 5, Vide)), 10,
   N (N (N (Vide, 2, Vide), 6, Vide), 8, N (N (Vide, 0, Vide), 4, Vide)))
and exemple_6 =
 N
  (N
    (N (N (N (Vide, 3, Vide), 7, Vide), 9, N (N (Vide, 1, Vide), 5, Vide)),
     10,
     N (N (N (Vide, 2, Vide), 6, Vide), 8, N (N (Vide, 0, Vide), 4, Vide))),
   11, N (Vide, 3, Vide))
and exemple_7 =
 N
  (N
    (N (N (Vide, 4, Vide), 8, N (Vide, 0, Vide)), 10,
     N (N (Vide, 2, Vide), 6, Vide)),
   11, N (N (N (Vide, 3, Vide), 7, Vide), 9, N (N (Vide, 1, Vide), 5, Vide)))
and exemple_8 =
 N
  (N
    (N (N (Vide, -1, Vide), 4, N (Vide, 0, Vide)), 8,
     N (N (Vide, 2, Vide), 6, Vide)),
   10, N (N (N (Vide, 3, Vide), 7, Vide), 9, N (N (Vide, 1, Vide), 5, Vide)))
;;

(* Question 14 *)

(* Pour tester si un arbre est un TPE, on écrit une fonction auxiliaire
 * prenant en entrée un arbre et renvoyant un couple (b, n) où b est un booléen
 * indiquant si l'arbre est un TPE et n son nombre de noeuds.
 * Ainsi, un arbre a est un TPE s'il est vide, ou si :
 * — ses deux sous-arbres gauche et droit sont des TPE ;
 * — la condition sur le nombre de nœuds des sous-arbres gauche et droit est vérifiée ;
 * — la condition de tas est vérifiée,
 *   c'est-à-dire que son sous-arbre gauche est vide ou sa racine est inférieure
 *   à la racine de a, et de même pour le sous-arbre droit *)

let racine a = match a with
  | Vide -> failwith "vide"
  | N(_,x,_) -> x
;;

let check_tpe a =
  let rec aux a = match a with
    | Vide -> true, 0
    | N(g,x,d) -> let b,n = aux g and c,m = aux d in
      b && c &&
      (g=Vide || x>=racine g) && (d=Vide || x>=racine d) &&
      n-1<=m && m<=n, n+m+1
  in fst (aux a)
;;

check_tpe exemple_4 ;;

check_tpe exemple_5 || check_tpe exemple_6 ;;

(* Question 15 *)

(* Pour l'insertion de x dans un tas t (non nécessairement équilibré),
 * il suffit de suivre le principe suivant :
 * — si t est vide, on renvoie un tas contenant seulement x ;
 * — sinon, si x est inférieur à la racine r de t,
 *   on peut insérer arbitrairement dans le sous-arbre gauche ou droit de t;
 * — dans le cas où x est strictement supérieur à la racine r de t,
 *   on remplace r par x, et on insère r dans le sous-arbre gauche ou droit *)

(* La difficulté est de préserver la propriété d'arbre presque équilibré.
 * L'astuce consiste à échanger les sous-arbres gauche et droit lorsqu'on
 * insère récursivement.
 * En effet, si t est un tas dont les sous-arbres gauche et droit sont g et d, 
 * alors n_d <= n_g <= n_d + 1.
 * Si on insère un élément dans d pour obtenir d', on a alors
 * n_g <= n_d' <= n_g + 1 : l'arbre ayant pour sous-arbre gauche d' et pour
 * sous-arbre droit g vérifie la propriété d'APE en la racine. *)

let rec inserer a x = match a with
  | Vide -> N(Vide, x, Vide)
  | N(g,y,d) when y>x -> N(inserer d x, y, g)
  | N(g,y,d) -> N(inserer d y, x, g)
;;

inserer exemple_4 11 = exemple_7 ;;

(* Question 16 *)

let rec modifier_racine a r = match a with
  | Vide -> Vide
  | N(g,_,d) when (g = Vide || racine g <= r) && (d = Vide || racine d <= r) -> N(g,r,d)
  | N(g,x,d) when (d = Vide || racine d <= racine g) -> N(modifier_racine g r, racine g, d)
  | N(g,x,d) -> N(g,racine d, modifier_racine d r)
;;

modifier_racine exemple_7 (-1) = exemple_8 ;;

(* Question 17 *)

let supprimer_racine a =
  let rec aux a = match a with
    | Vide -> failwith "Vide"
    | N(Vide, e, _) -> Vide, e
    | N(g,x,d) -> let g2,e = aux g in N(d,x,g2), e
  in let b,e = aux a in racine a, modifier_racine b e
;;

supprimer_racine exemple_7 ;;