gistfile1.ml

let rec trace_insert ((x,d) as e) t = match t with
| Empty -> (Node(e,Empty,Empty), H x)
| Node((y,d'),l,r) -> if (y=x) then (Node(e,l,r),H x)
		      else if x<y then 
                           let(t',tr) = trace_insert e l in ( Node((y,d'),t',r), L(y,tr) )
			   else 
                           let(t',tr) = trace_insert e r in ( Node((y,d'),l,t'), R(y,tr) )