Skip to content

Instantly share code, notes, and snippets.

@neoGeneva
Created June 30, 2011 11:13
Show Gist options
  • Save neoGeneva/1056026 to your computer and use it in GitHub Desktop.
Save neoGeneva/1056026 to your computer and use it in GitHub Desktop.
Red-Black Tree in F#
// 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)
@neoGeneva
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment