type color = R | B
type 'a tree = E | T of color * 'a tree * 'a * 'a tree
 
let balance = function
       | B, T (R, T (R,a,x,b), y, c), z, d
       | B, T (R, a, x, T (R,b,y,c)), z, d
       | B, a, x, T (R, T (R,b,y,c), z, d)
       | B, a, x, T (R, b, y, T (R,c,z,d)) -> T (R, T (B,a,x,b), y, T(B,c,z,d))
       | c, a, x, b                        -> T (c, a, x, b)
 
let insert x s =
       let rec ins = function
               | E                         -> T (R,E,x,E)
               | T (c,a,y,b) as s          ->
                   if x < y then
                      balance (c, ins a, y, b)
                   else if x > y then
                      balance (c, a, y, ins b)
                   else
                      s
        in let T (_,a,y,b) = ins s
        in T (B,a,y,b)
 
let rec mem x = function
            | E -> false
            | T (_, y, left, right)        ->
                 x = y || (x < y && mem x left) || (x > y && mem x right)

dHlwZSBjb2xvciA9IFIgfCBCCnR5cGUgJ2EgdHJlZSA9IEUgfCBUIG9mIGNvbG9yICogJ2EgdHJlZSAqICdhICogJ2EgdHJlZQoKbGV0IGJhbGFuY2UgPSBmdW5jdGlvbgogICAgICAgfCBCLCBUIChSLCBUIChSLGEseCxiKSwgeSwgYyksIHosIGQKICAgICAgIHwgQiwgVCAoUiwgYSwgeCwgVCAoUixiLHksYykpLCB6LCBkCiAgICAgICB8IEIsIGEsIHgsIFQgKFIsIFQgKFIsYix5LGMpLCB6LCBkKQogICAgICAgfCBCLCBhLCB4LCBUIChSLCBiLCB5LCBUIChSLGMseixkKSkgLT4gVCAoUiwgVCAoQixhLHgsYiksIHksIFQoQixjLHosZCkpCiAgICAgICB8IGMsIGEsIHgsIGIgICAgICAgICAgICAgICAgICAgICAgICAtPiBUIChjLCBhLCB4LCBiKQoKbGV0IGluc2VydCB4IHMgPQogICAgICAgbGV0IHJlYyBpbnMgPSBmdW5jdGlvbgogICAgICAgICAgICAgICB8IEUgICAgICAgICAgICAgICAgICAgICAgICAgLT4gVCAoUixFLHgsRSkKICAgICAgICAgICAgICAgfCBUIChjLGEseSxiKSBhcyBzICAgICAgICAgIC0+CiAgICAgICAgICAgICAgICAgICBpZiB4IDwgeSB0aGVuCiAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlIChjLCBpbnMgYSwgeSwgYikKICAgICAgICAgICAgICAgICAgIGVsc2UgaWYgeCA+IHkgdGhlbgogICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZSAoYywgYSwgeSwgaW5zIGIpCiAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICBzCiAgICAgICAgaW4gbGV0IFQgKF8sYSx5LGIpID0gaW5zIHMKICAgICAgICBpbiBUIChCLGEseSxiKQoKbGV0IHJlYyBtZW0geCA9IGZ1bmN0aW9uCiAgICAgICAgICAgIHwgRSAtPiBmYWxzZQogICAgICAgICAgICB8IFQgKF8sIHksIGxlZnQsIHJpZ2h0KSAgICAgICAgLT4KICAgICAgICAgICAgICAgICB4ID0geSB8fCAoeCA8IHkgJiYgbWVtIHggbGVmdCkgfHwgKHggPiB5ICYmIG1lbSB4IHJpZ2h0KQ==