Untitled

exception Collision;;

let rec insertion t (new_k : string) new_v =
  match t with
    Lf -> Br ((new_k, new_v), Lf, Lf)
  | Br((k, v), t1, t2) -> if new_k < k then Br ((k, v), insertion t1 new_k new_v, t2)
      else if new_k > k then Br ((k, v), t1, insertion t2 new_k new_v)
      else raise Collision;;