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 | E -> failwith "bad value"
in T (B,a,y,b)
let rec member x = function
| E -> false
| T (_, left, y, right) ->
x = y || (x < y && member x left) || (x > y && member x right)
dHlwZSBjb2xvciA9IFIgfCBCCnR5cGUgJ2EgdHJlZSA9IEUgfCBUIG9mIGNvbG9yICogJ2EgdHJlZSAqICdhICogJ2EgdHJlZQoKbGV0IGJhbGFuY2UgPSBmdW5jdGlvbgogICAgICAgfCBCLCBUIChSLCBUIChSLGEseCxiKSwgeSwgYyksIHosIGQKICAgICAgIHwgQiwgVCAoUiwgYSwgeCwgVCAoUixiLHksYykpLCB6LCBkCiAgICAgICB8IEIsIGEsIHgsIFQgKFIsIFQgKFIsYix5LGMpLCB6LCBkKQogICAgICAgfCBCLCBhLCB4LCBUIChSLCBiLCB5LCBUIChSLGMseixkKSkgLT4gVCAoUiwgVCAoQixhLHgsYiksIHksIFQoQixjLHosZCkpCiAgICAgICB8IGMsIGEsIHgsIGIgICAgICAgICAgICAgICAgICAgICAgICAtPiBUIChjLCBhLCB4LCBiKQoKbGV0IGluc2VydCB4IHMgPQogICAgICAgbGV0IHJlYyBpbnMgPSBmdW5jdGlvbgogICAgICAgICAgICAgICB8IEUgICAgICAgICAgICAgICAgICAgICAgICAgLT4gVCAoUixFLHgsRSkKICAgICAgICAgICAgICAgfCBUIChjLGEseSxiKSBhcyBzICAgICAgICAgIC0+CiAgICAgICAgICAgICAgICAgICBpZiB4IDwgeSB0aGVuCiAgICAgICAgICAgICAgICAgICAgICBiYWxhbmNlIChjLCBpbnMgYSwgeSwgYikKICAgICAgICAgICAgICAgICAgIGVsc2UgaWYgeCA+IHkgdGhlbgogICAgICAgICAgICAgICAgICAgICAgYmFsYW5jZSAoYywgYSwgeSwgaW5zIGIpCiAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICBzCiAgICAgICAgaW4gbGV0IFQgKF8sYSx5LGIpIC0+IGlucyBzIHwgRSAtPiBmYWlsd2l0aCAiYmFkIHZhbHVlIgogICAgICAgIGluIFQgKEIsYSx5LGIpCgpsZXQgcmVjIG1lbWJlciB4ID0gZnVuY3Rpb24KICAgICAgICAgICAgfCBFIC0+IGZhbHNlCiAgICAgICAgICAgIHwgVCAoXywgbGVmdCwgeSwgcmlnaHQpICAgICAgICAtPgogICAgICAgICAgICAgICAgIHggPSB5IHx8ICh4IDwgeSAmJiBtZW1iZXIgeCBsZWZ0KSB8fCAoeCA+IHkgJiYgbWVtYmVyIHggcmlnaHQp