type BTree =
        | Node of   v1:     int         *
                    v2:     int option  *
                    parent: BTree ref   *
                    left:   BTree ref   *
                    mid:    BTree ref   *
                    right:  BTree ref
        | Leaf of   v1:     int         *
                    v2:     int option  *
                    parent: BTree ref
        | Empty


    let median (a:int) (b:int) (c:int) =
        Array.sort [|a;b;c|]


    let mid l r x =
        (l < x) && (x < r)


    let rec insert (tref:BTree ref) (x:int) : BTree =
        let tree = !tref
        match tree with
        | Node(a,None,p,l,m,r)
                        when !l = Empty
                        &&   x < a      ->  Node(x,Some a,p,l,m,r)
        | Node(a,b,p,l,m,r)
                        when x < a      ->  l := insert l x
                                            Node(a,b,p,l,m,r)
        | Node(a,None,p,l,m,r)
                        when !r = Empty
                        &&   x > a      ->  Node(a,Some x,p,l,m,r)

        | Node(a,b,p,l,m,r)
                        when x > a      ->  r := insert r x
                                            Node(a,b,p,l,m,r)
        | Node(a,Some b,p,l,m,r)
                        when !l = Empty
                        &&   !m = Empty
                        &&   !r = Empty ->  let m = median a b x
                                            let o = ref Empty
                                            l := Leaf(m.[0],None,o)
                                            r := Leaf(m.[2],None,o)
                                            o := Node(m.[1],None,p,l,ref Empty,r)
                                            !o
        | Node(a,Some b,p,l,m,r)
                        when !l = Empty
                        &&   x < a      ->  let parent = ref tree
                                            l := Leaf(x,None,parent)
                                            Node(a,Some b,p,l,m,r)
        | Node(a,Some b,p,l,m,r)
                        when !r = Empty
                        &&   x > b      ->  let parent = ref tree
                                            r := Leaf(x,None,parent)
                                            Node(a,Some b,p,l,m,r)
        | Node(a,Some b,p,l,m,r)
                        when !m = Empty
                        &&   mid a b x  ->  let parent = ref tree
                                            m := Leaf(x,None,parent)
                                            Node(a,Some b,p,l,m,r)
        | Node(a,Some b,p,l,m,r)
                        when mid a b x  ->  m := insert m x
                                            Node(a,Some b,p,l,m,r)
        | Leaf(a,None,p)
                        when x < a      ->  Leaf(x,Some a,p)
        | Leaf(a,None,p)
                        when x > a      ->  Leaf(a,Some x,p)
        | Leaf(a,Some b,p)              ->  rebuild tref x
        | Empty                         ->  failwith "Cannot insert into empty"
        | _                             ->  failwith "Invalid Tree"
    and rebuild (tref:BTree ref) (x:int) : BTree =
        let tree = !tref
        match tree with
        | Node(a,None,p,l,m,r)
                        when !m = Empty
                        && !r = Leaf(x,)
                        &&   x > a      ->  Empty
        | Node(a,None,p,l,m,r)
                        when x > a      ->  Node(a,Some x,p,l,m,r)
        | Node(a,Some b,parent,l,m,r)
                        when !m = Empty ->  let m = median a b x
                                            let p = ref Empty
                                            let lt = ref (Node(m.[0],None,p,l,ref Empty,ref Empty))
                                            let rt = ref (Node(m.[2],None,p,ref Empty,ref Empty,r))
                                            p := rebuild parent m.[1]
                                            !p
        | Node(a,b,p,l,m,r)
                        when !m = Empty
                                x < a   ->  m:= Leaf(x,None,tree)
                                            Node(a,b,p,l,child,r)
        | Leaf(a,Some(b),parent)        ->  let m = median a b x
                                            let l = ref (Leaf(m.[0],None,ref Empty))
                                            let r = ref (Leaf(m.[2],None,ref Empty))
                                            let p = ref (rebuild parent m.[1])
                                            Node(m.[1],None,p,l,ref Empty,r)
        | Node(a,b,p,l,m,Empty)
                        when x > a      ->  let child = Leaf(x,None,tree)
                                            Node(a,b,p,l,m,child)