(* This code extends 'mini_prelude'. *)

type color = 
    Black 
  | Red ;;

type ('a) tree = 
    Tree of color * ('a) tree * 'a * ('a) tree 
  | Empty ;;

let empty = Empty ;;

let rec member v5 = 
  (fun v6 -> 
    (fun v7 -> 
      (match v7 with 
          Empty -> false 
        | (Tree (v4, v3, v2, v1)) -> 
            (if ((v5 v6) v2) 
            then (((member v5) v6) v3) 
            else 
              (if ((v5 v2) v6) 
              then (((member v5) v6) v1) 
              else true))))) ;;

type ('a) option = 
    Some of 'a 
  | None ;;

let balance_left_left = 
  (fun v11 -> 
    (fun v9 -> 
      (fun v10 -> 
        (match v11 with 
            Empty -> None 
          | (Tree (v8, v7, v6, v5)) -> 
              (match v8 with 
                  Red -> 
                    (match v7 with 
                        Empty -> None 
                      | (Tree (v4, v3, v2, v1)) -> 
                          (match v4 with 
                              Red -> (Some ((Tree (Red, (Tree (Black, v3, v2, v1)), v6, (Tree (Black, v5, v9, v10)))))) 
                            | Black -> None)) 
                | Black -> None))))) ;;

let balance_left_right = 
  (fun v11 -> 
    (fun v9 -> 
      (fun v10 -> 
        (match v11 with 
            Empty -> None 
          | (Tree (v8, v7, v6, v5)) -> 
              (match v8 with 
                  Red -> 
                    (match v5 with 
                        Empty -> None 
                      | (Tree (v4, v3, v2, v1)) -> 
                          (match v4 with 
                              Red -> (Some ((Tree (Red, (Tree (Black, v7, v6, v3)), v2, (Tree (Black, v1, v9, v10)))))) 
                            | Black -> None)) 
                | Black -> None))))) ;;

let balance_right_left = 
  (fun v11 -> 
    (fun v9 -> 
      (fun v10 -> 
        (match v10 with 
            Empty -> None 
          | (Tree (v8, v7, v6, v5)) -> 
              (match v8 with 
                  Red -> 
                    (match v7 with 
                        Empty -> None 
                      | (Tree (v4, v3, v2, v1)) -> 
                          (match v4 with 
                              Red -> (Some ((Tree (Red, (Tree (Black, v11, v9, v3)), v2, (Tree (Black, v1, v6, v5)))))) 
                            | Black -> None)) 
                | Black -> None))))) ;;

let balance_right_right = 
  (fun v11 -> 
    (fun v9 -> 
      (fun v10 -> 
        (match v10 with 
            Empty -> None 
          | (Tree (v8, v7, v6, v5)) -> 
              (match v8 with 
                  Red -> 
                    (match v5 with 
                        Empty -> None 
                      | (Tree (v4, v3, v2, v1)) -> 
                          (match v4 with 
                              Red -> (Some ((Tree (Red, (Tree (Black, v11, v9, v7)), v6, (Tree (Black, v3, v2, v1)))))) 
                            | Black -> None)) 
                | Black -> None))))) ;;

let balance' = 
  (fun v7 -> 
    (fun v5 -> 
      (fun v8 -> 
        (fun v6 -> 
          (if (v7 = Black) 
          then 
            (match (((balance_left_left v5) v8) v6) with 
                None -> 
                  (match (((balance_left_right v5) v8) v6) with 
                      None -> 
                        (match (((balance_right_left v5) v8) v6) with 
                            None -> 
                              (match (((balance_right_right v5) v8) v6) with 
                              None -> (Tree (Black, v5, v8, v6)) 
                              | (Some (v1)) -> v1) 
                          | (Some (v2)) -> v2) 
                    | (Some (v3)) -> v3) 
              | (Some (v4)) -> v4) 
          else (Tree (v7, v5, v8, v6))))))) ;;

let rec ins v5 = 
  (fun v6 -> 
    (fun v7 -> 
      (match v7 with 
          Empty -> (Tree (Red, Empty, v6, Empty)) 
        | (Tree (v4, v3, v2, v1)) -> 
            (if ((v5 v6) v2) 
            then ((((balance' v4) (((ins v5) v6) v3)) v2) v1) 
            else 
              (if ((v5 v2) v6) 
              then ((((balance' v4) v3) v2) (((ins v5) v6) v1)) 
              else (Tree (v4, v3, v2, v1))))))) ;;

let insert = 
  (fun v5 -> 
    (fun v7 -> 
      (fun v6 -> 
        (match (((ins v5) v7) v6) with 
            Empty -> (raise (Match_failure (string_of_bool true, 0, 0))) 
          | (Tree (v4, v3, v2, v1)) -> (Tree (Black, v3, v2, v1)))))) ;;