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==