let rec add s n =
  if is_empty s then make_tree empty (n, n) empty else
  let (v1, v2) as v = root s in
  let s0 = left_branch s in
  let s1 = right_branch s in
  if v1 <> min_int && n < v1 - 1 then make_tree (add s0 n) v s1 else
  if v2 <> max_int && n > v2 + 1 then make_tree s0 v (add s1 n) else
  if n + 1 = v1 then
    if not (is_empty s0) then
      let (u1, u2), s0' = split_rightmost s0 in
      if u2 <> max_int && u2 + 1 = n then
        make_tree s0' (u1, v2) s1
      else
        make_tree s0 (n, v2) s1
    else
      make_tree s0 (n, v2) s1
  else if v2 + 1 = n then
    if not (is_empty s1) then
      let (u1, u2), s1' = split_leftmost s1 in
      if n <> max_int && n + 1 = u1 then
        make_tree s0 (v1, u2) s1'
      else
        make_tree s0 (v1, n) s1
    else
      make_tree s0 (v1, n) s1
  else s