type 'a arbre = Nil
  | D of 'a arbre * 'a * 'a arbre
  | T of 'a arbre * 'a * 'a arbre * 'a * 'a arbre
  | Q of 'a arbre * 'a * 'a arbre * 'a * 'a arbre * 'a * 'a arbre;;
let split4 = function
| Q(a1, k1, a2, k2, a3, k3, a4) -> (D(a1, k1, a2), k2, D(a3, k3, a4) )
| _ -> failwith("split 4") ;;
let i4 = function
| Q(a1, k1, a2, k2, a3, k3, a4) -> true
| _ -> false ;;
(* O(ln n) *)
let rec insert cmp v = function
| Nil -> failwith("insert")
| Q(a1, k1, a2, k2, a3, k3, a4) -> D(D(a1, k1, a2), k2, D(a3, k3, a4)) (*head*)
| D(Nil, k, Nil) -> if cmp v k = -1
  then T(Nil, v, Nil, k, Nil)
  else T(Nil, k, Nil, v, Nil)
| T(Nil, k1, Nil, k2, Nil) -> if cmp v k1 = -1
  then Q(Nil, v, Nil, k1, Nil, k2, Nil)
  else if cmp v k2 = 1
    then Q(Nil, k1, Nil, k2, Nil, v, Nil)
    else Q(Nil, k1, Nil, v, Nil, k2, Nil)
| D(a1, k1, a2) -> if cmp v k1 = -1
  then if i4 a1
    then let (a1', k1', a1'') = split4 a1
      in insert cmp v (T (a1', k1', a1'', k1, a2))
    else D (insert cmp v a1, k1, a2)
  else if i4 a2
    then let (a2', k2', a2'') = split4 a2
      in insert cmp v (T (a1, k1, a2', k2', a2''))
    else D (a1, k1, insert cmp v a2)
| T(a1, k1, a2, k2, a3) -> if cmp v k1 == -1
  then if i4 a1
    then let (a1', k1', a1'') = split4 a1 in if cmp v k1' = 1
      then Q (a1', k1', insert cmp v a1'', k1, a2, k2, a3)
      else Q (insert cmp v a1', k1', a1'', k1, a2, k2, a3)
    else T(insert cmp v a1, k1, a2, k2, a3)
  else if cmp v k2 = 1
    then if i4 a3
      then let (a3', k3', a3'') = split4 a3 in if cmp v k3' = 1
    then Q (a1, k1, a2, k2, a3', k3', insert cmp v a3'')
    else Q (a1, k1, a2, k2, insert cmp v a3', k3', a3'') 
      else T(a1, k1, a2, k2, insert cmp v a3)
    else if i4 a2
      then let (a2', k2', a2'') = split4 a2 in if cmp v k2' = 1
    then Q (a1, k1, a2', k2', insert cmp v a2'', k2, a3)
    else Q (a1, k1, insert cmp v a2', k2', a2'', k2, a3)
      else T(a1, k1, insert cmp v a2, k2, a3);;
let insert cmp v tree = if tree = Nil then D(Nil, v, Nil) else insert cmp v tree;;
let cmp_i a b = if a < b then -1 else if a = b then 0 else 1;;
let insert_i = insert cmp_i;;
(* O(ln n) *)
let rec search cmp v = function
| Nil -> None
| D (a1, k1, a2) -> let c = cmp v k1 in
  if c = 0 then Some k1 else search cmp v (if c = 1 then a2 else  a1)
| T(a1, k1, a2, k2, a3) -> let c = cmp v k1 in
  if c = 0 then Some k1 else if c = -1 then search cmp v a1
  else search cmp v (D(a2, k2, a3))
| Q(a1, k1, a2, k2, a3, k3, a4) -> let c = cmp v k2 in
  if c = 0 then Some k2 else if c = -1
    then search cmp v (D(a1, k1, a2))
    else search cmp v (D(a3, k3, a4));;
(* O(n) <=> O(2^p) *)
let arbre2li =
let rec i acc= function
| Nil -> acc
| D(a1, k1, a2) -> i (k1::(i acc a2)) a1
| T(a1, k1, a2, k2, a3) -> i (k1::(i acc (D(a2, k2, a3)) )) a1
| Q(a1, k1, a2, k2, a3, k3, a4) -> i (k1::(i acc (T(a2, k2, a3, k3, a4)))) a1
in i [];;