(** Problème ENSI '98 **)




type int_arbre = Nil | Noeud of int*int_arbre*int_arbre;;

(* Union d'ABR *)
let rec couper c = function
	|Nil -> (Nil, Nil)
	|Noeud(i,a,b) ->  if c=i
				then (Noeud(i,a,Nil),b)
				else if c<i
					  then let (ga,da)=couper c a in (ga,Noeud(i,da,b))
					  else let (gb,db)=couper c b in (Noeud(i,a,gb),db)
;;

let test=Noeud(17,
		   Noeud(9,
			   Noeud(1,Nil,Nil),
			   Noeud(13,
				   Noeud(10,Nil,Noeud(12,Nil,Nil)),
				   Noeud(14,Nil,Nil)
				   )
			   ),
		   Noeud(19,Nil,Nil)
		   )
;;

couper 10 test;;

let inserer_racine i a = let (G,D)=couper i a in Noeud(i,G,D);;

let rec min = function
	|Nil -> failwith "Arbre vide"
	|Noeud(a,Nil,_) -> a
	|Noeud(_,g,_) -> min g
;;

let union a b = 
	let racine = min b
in	let (g,d)=couper racine b
in Noeud (racine,a,d);;