hubFS: THE place for F#

Red-Black Trees are a Data Structure.  They have algorithms associated with their use.  While there are many references on Red-Black Trees, a useful reference is Cormen, Lieserson and Rivest(1) (and note that the authors last initials combined are CLR; Nice).

Consider for a moment a binary tree(1).  The job of a binary tree is to provide for operations on dynamic sets of data.  These include search, min, max, etc.  The binary tree represents a reasonable data structure for many different sets of data to support these operations.  From (1) I'll quote:

. . .

The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property.

Let x be a node in a binary search tree.  If y is a node in the left subtree of x, then key[y] <= key[x].  If y is a node in the right subtree of x, then key[x] <= key[y].

. . .

The problem with binary trees, while they are useful in many applications, is that the "height" of the tree determines the running time of algorithms that operate on the tree.  So if a binary tree, at runtime, has a height that is nearly equal to the number of elements of the set that it describes, the binary tree provides little improvement in running time in the above mentioned operations.

The Red-Black tree attempts to overcome this difficulty without a priori knowledge of the set that is to be used.  The goal of the Red-Black tree is to provide for algorithms with O(lg n) running time, i.e. the worst case for any algorithm should complete after log n steps where n is the number of items in the set.  The implementation of a Red-Black tree is similar to a binary tree, but with one key difference.  Each node in the tree is given an additional attribute, color.  With a few simple rules for coloring, the Red-Black tree achieves balance, i.e. the height of the tree does not approach the count of the members of the set that it describes and therefore, the running times for operations on the tree are reduced.

In a recent thread, How do I?, The Armed Geometer asked for an example implementation of Red-Black Trees:

The Armed Geometer wrote:

How do I create the equivalent of a red-black tree in F# where each node has a key that is two floats: x,y and has a value that is four floats x1,y1,x2,y2 ? I would also like to be able to specify how the keys get compared so I can decide what is less than based on comparing y then x. Any ideas or examples you could point me to?

Basically I would like to see how you would re-create the functionality of C++'s std::map<point,segment> with an overloaded operator< for the class point.

Dr. Syme responded (please note that I've used the new CS2.0 addin for code coloring with the F# enhancements that Scott and I have done to color Dr. Syme's code; as of this writing, we are testing; coloring wasn't available to Dr. Syme as of his writing):

dsyme wrote:

First take a look at the 'set.fs' implementation of binary trees in the distribution. For example, binary trees for implementing sets are defined as follows:

type 'a tree = SetEmpty | SetNode of 'a * 'a tree * 'a tree * int

A red-black tree will usually carry a reb/black flag, e.g.

type color = R | B
type 'a tree = E | T of color * 'a tree * 'a * 'a tree

or use a boolean.  Samples on the web show examples of rebalancing such a tree using pattern matching, e.g.  http://www.msu.edu/course/lin/475/notes/hale-notes002.html, about half way down.

In F#, you have a number of choices as to how the comparer function is handled.  The design I like best (but which is not yet used in the Set and Map implementations, though we may move to it) is to store the comparison function as a value in the root node of the tree, and pass it down explicitly through the functions that implement the operations on the trees (e.g. 'add', which I'm not showing here as I'll get it wildly wrong :-) ).  You can then pass in the comparer as a function value when an tree is constructed.  You can also provided a constructor function that fills in this with the default value of Pervasives.compare, which is F#'s default structural comparison operator  and works over the 'default' comparison semantics associated with types via the IComparable interface.  For example.

type 'a comparer = 'a -> 'a -> int
type color = R | B
type ('a,'b) tree =
{ cf: 'a comparer;
  top: ('a,'b) node }

and ('a,'b) node = E | T of color * ('a,'b) node * 'a * 'b * ('a,'b) node

let empty_explicit cf = { cf=cf; top=E }
let empty = { cf=Pervasives.compare; top=E }

You would use this as follows:

/// This gets the string comparison implemented by
/// Pervasives.compare, which is case insensitive, culture neutral
let myTree1 : (string,int) tree = RBTree.empty

let case_sensitive s1 s2 = System.String.Compare(s1,s2,false)
let myTree2 : (string,int) tree = RBTree.empty_explicit case_sensitive

let case_insensitive s1 s2 = System.String.Compare(s1,s2,true)
let myTree3 : (string,int) tree = RBTree.empty_explicit case_insensitive

Finally, some people like using the 'functor' style, where you give the comparison operator once and for all and return a whole record of functions for use with trees specialized for that particular comparison operator.  See, for example, Set.Make in the distribution. I personally don't think this buys too much in practice.

Next, to get your floats, use something like

type fpair = float * float
type fquad = float * float * float * float

let cf (x1,y1) (x2,y2) =
  let c = compare y1 y2 in
  if c <> 0 then c
  else compare x1 x2

let myTree4 : (fpair,fquad) tree = empty_explicit cf

Finally, I think you were hinting at the case where the keys are just a logical projection from the data carried at each node of the tree (indeed sometimes both the key and value are just such a projection).  In this case you can change your tree structure to reflect this, parameterizing it by both key extraction and value extraction functions:

type 'a comparer = 'a -> 'a -> int
type('k,'v,'data) tree =
{ cf: 'k comparer;
  kf: ('data -> 'k);
  vf: ('data -> 'v);
  top: 'data node }

and 'data node = E | T of color * 'data node * 'data * 'data node

/// Simple trees just have data that is a key, value pair.
type ('k,'v) simpleTree = ('k,'v, ('k*'v)) tree

/// This one creates a simple tree where the data is just a
/// key, value pair and the keys are compared using structural
/// comparison.
// val empty : ('k,'v) simpleTree

let empty =
{ cf = (fun (k1,_) (k2,_) -> Pervasives.compare k1 k2);
  kf = (fun (k,v) -> k);
  vf = (fun (k,v) -> v);
  top=E }

/// This one creates a simple tree where the data is just a
/// key, value pair and the keys are compared using the explicit
/// comparison function.

// val empty_cf : ('k,'v) simpleTree

let empty_cf cf =
{ cf = (fun (k1,_) (k2,_) -> cf k1 k2);
  kf = (fun (k,v) -> k);
  vf = (fun (k,v) -> v);
  top=E }

/// This one is the most general: all three functions are given
/// explicitly. If you like you can accept an obejct model
/// interface as the input: this is normal practice once
/// multiple related function arguments are used to parameterize
/// a function.

let empty_kf_vf_cf (kf,vf,cf) =
{ cf = cf;
  kf = kf;
  vf = vf;
  top=E }

I would use three constructors rather than carrying a red/black tag:

type 'a t = E | R of 'a t * 'a * 'a t | B of 'a t * 'a * 'a t

However, RB-trees are less prevelant in functional programming. In OCaml, they are not significantly faster than AVL trees for the operations they support (e.g. add, remove). Moreover, RB-trees cannot implement some important operations (e.g. union) as efficiently as AVL trees because the information required to balance pairs of trees is not present.

I'd like to see the F# standard library include fast set theoretic operations, generic AVL trees and a balanced-binary-tree-based functional array data structure.

Cheers,
Jon.

Hi mstump,

There are a few forums that were designated "contributor-only" (for organizational and admin work) when we first started the site.  Andy (The Armed Geometer) had inadvertently posted this question to one of those forums.

Andy's original post and Dr. Syme's response are included in this thread in their entirety.  I should have made that clear when I wrote this.  My apologies for not calling that out appropriately.

---O