Red-Black Tree in F#

RedBlackTree.fsx

// Inspired by: http://jng.imagine27.com/articles/2011-06-28-141124_purely_functional_types_red_black_trees_in_qi.html

type TreeNode<'a> = { Key: int; Val: 'a }
    
type Color = Red | Black

type Tree<'a> = { Color: Color; LTree: Tree<'a> option; TreeNode: TreeNode<'a>; RTree: Tree<'a> option; }

let makeTreeBlack tree = 
    match tree with
    | None -> None
    | Some t -> Some { t with Color = Color.Black }

let rec getMember (node : TreeNode<'a>) (tree : Tree<'a> option) =
    match tree with
    | None -> false
    | Some t when node.Key < t.TreeNode.Key -> getMember node t.LTree
    | Some t when node.Key > t.TreeNode.Key -> getMember node t.RTree
    | _ -> true

let balance (tree : Tree<'a> option) =
    match tree with
    | Some { Color = Color.Black; LTree = Some { Color = Color.Red; LTree = Some { Color = Color.Red; LTree = a; TreeNode = x; RTree = b }; TreeNode = y; RTree = c }; TreeNode = z; RTree = d }
    | Some { Color = Color.Black; LTree = Some { Color = Color.Red; LTree = a; TreeNode = x; RTree = Some { Color = Color.Red; LTree = b; TreeNode = y; RTree = c } }; TreeNode = z; RTree = d }
    | Some { Color = Color.Black; LTree = a; TreeNode = x; RTree = Some { Color = Color.Red; LTree = Some { Color = Color.Red; LTree = b; TreeNode = y; RTree = c }; TreeNode = z; RTree = d } }
    | Some { Color = Color.Black; LTree = a; TreeNode = x; RTree = Some { Color = Color.Red; LTree = b; TreeNode = y; RTree = Some { Color = Color.Red; LTree = c; TreeNode = z; RTree = d } } } -> 
        Some { Color = Color.Red; LTree = Some { Color = Color.Black; LTree = a; TreeNode = x; RTree = b }; TreeNode = y; RTree = Some { Color = Color.Black; LTree = c; TreeNode = z; RTree  = d; } }
    | _ -> tree

let rec insertEx (node : TreeNode<'a>) (tree : Tree<'a> option) =
    match tree with
    | None -> Some { Color = Color.Red; LTree = None; TreeNode = node; RTree = None }
    | Some t when node.Key < t.TreeNode.Key -> balance(Some { t with LTree = insertEx node t.LTree })
    | Some t when node.Key > t.TreeNode.Key -> balance(Some { t with RTree = insertEx node t.RTree })
    | _ -> tree

let insert (node : TreeNode<'a>)  (tree : Tree<'a> option)=
    makeTreeBlack (insertEx node tree)

// Some code to build a tree...

let t = seq { for i in 1 .. 10000 -> { Key = i; Val = i } }
|> Seq.fold (fun a i -> insert i a) None