type braun = E | N of int * braun * braun

(* Deux tas de Braun *)
let t1 = N(1, N(3, N(7,E,E), E), N(4,E,E))
let t2 = N(1, N(5,E,E), N(12,E,E))

(* Fonction à comprendre pour répondre à la question 4 *)
let rec inserer (a:braun) (x:int) = match a with
  |E -> N(x,E,E)
  |N(r,g,d) when x < r -> N(x, inserer d r, g)
  |N(r,g,d) -> N(r, inserer d x, g)

(* Fonction à utiliser pour la question 5 et compléter via les questions 6 et 7 *)
(* ATTENTION : on ne peut pas utiliser cette fonction avant d'avoir écrit extraire_element et remplacer_min *)
(** Entrée : deux tas de Braun t et t' tels que |t'| <= |t| <= |t'| + 1.
Sortie : un tas de Braun contenant l'union des éléments contenus dans t et t'. *)
let rec fusionner (g:braun) (d:braun) :braun = match g, d with
    |E, E |N(_,E,E), E -> g
    |N(rg, gg, dg), N(rd, gd, dd) ->
      if rg <= rd then N(rg, d, fusionner gg dg)
      else let x, g' = extraire_element g in
           N(rd, remplacer_min d x, g')
    |_ -> failwith "conditions sur les arbres non respectées dans fusionner"