type arbre_bin =
|Vide
| Noeud of int*(arbre_bin)*(arbre_bin)
;;

let ex1 = Noeud(
  27,
  Noeud(
    12,
    Noeud(5,Vide,Vide),
    Noeud(
      19,
      Noeud(17,Vide,Vide),
      Noeud(
        24,
        Noeud(20,Vide,Vide),
        Noeud(26,Vide,Vide)
      )
    )
  ),
  Noeud(
    43,
    Noeud(36,Vide,Vide),
    Noeud(77,Vide,Vide)
  )
);;

type comparaison = Inf | Egal | Sup;;

let compare_int x y =
  if x<y then Inf else if x=y then Egal else Sup
;;

let rec recherche a func x = match a with
| Vide -> false
| Noeud(n,g,d)->match func x n with
| Inf -> recherche g func x
| Egal -> true
| Sup -> recherche d func x
;;
(*


   
C(0)=2
Opf = Comparaisons


2h+2
*)

(*a est un arbre de recherche dans tous les programmes suivants*)
let rec min_gauche_max_droit a max1 min2= match a with
| Vide -> failwith "Pas de min"
| N(e,g,d) -> if max1 > min_gauche_max_droit d then max1 else min_gauche_max_droit d;
  if min2 > min_gauche_max_droit a

;;
#trace min_gauche_max_droit;;





























































































































































































































































































































let rec verif_encadre a fuck x y = match a with
| Vide -> true
| 
;;
let verif_arbre_rech a func = verif_encadre a func (fst (min_gauche_max_droit a)) (snd (min_gauche_max_droit a));;
let verif_tri l func =
;;
(*Copier la fonction infixe ici*)

let verif_arb_rech2 a func =
;;
let insere_feuille a func x =
;;
let decoupe a func x =
;;
let insere_racine a func x = 
;;
let construction_feuille l func = 

;;

let construction_racine l func =

;;

let liste_ex1 = [1;2;3;4;5;6;7;8;9];;
let liste_ex2 = [1;3;5;7;9;8;6;4;2];;

let rotation_gauche a =

;;

let rotation_droite a =

;;

let rec mystere a1 a2 func =
  | _,Vide -> a1
  | Vide,_ -> a2
  | Noeud(e1,ag1,ad1), Noeud(e2, ag2,ad1) when compare e1 e2 = Inf
    -> mystere ad1 (Noeud(e2,mystere Noeud(e1,ag1,Vide) ag2 func, ad2)) func
  | Noeud(e1,ag1,ad1), Noeud(e2,ag2,ad2)
    -> mystere ag1 (Noeud(e2,ag2,mystere Noeud(e1,Vide,ad1) ad2 func)) func
;;