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"