#light

type Tree<'a> =
   | Node of 'a * Tree<'a> * Tree<'a>
   | Leaf

let rec add tree value =
   match tree with
   | Leaf -> Node(value, Leaf, Leaf)
   | Node(i, l, r) when value < i -> Node(i, add l value, r)
   | Node(i, l, r) when value > i -> Node(i, l, add r value)
   | _ -> tree

let rec remove tree value =
   let rec successor tree =
      match tree with
      | Node(i, Leaf, _) -> i
      | Node(_, l, _) -> successor l

   match tree with
   | Node(i, l, r) when value < i -> Node(i, remove l value, r)
   | Node(i, l, r) when value > i -> Node(i, l, remove r value)
   | Node(i, Leaf, Leaf) when i = value -> Leaf
   | Node(i, l, Leaf) when i = value -> l
   | Node(i, Leaf, r) when i = value -> r
   | Node(i, l, r) when i = value ->
      //find in-order successor (left-most child of right subtree):
      let j = successor r
      Node(j, l, remove r j)

let rec search tree value =
   match tree with
   | Leaf -> None
   | Node(i, l, _) when value < i -> search l value
   | Node(i, _, r) when value > i-> search r value
   | _ -> Some value

let rec traverse tree = seq {
   match tree with
   | Leaf -> ()
   | Node(i, l, r) ->
      yield! traverse l
      yield i
      yield! traverse r
}

let sort x = x |> Seq.fold add Leaf |> traverse
 

next: red-black tree