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 for this kind of data structure is handled. The design most people tend to over time (but which is not yet used in the Set and Map implementations, though is used for F# hash tables, though in an object-oriented setting - see collections.fs in the distribution) 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 provide 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

Some people also 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 associated with that particular comparison operator. See, for example, Set.Make in the distribution.

For example, to build a tree structure where the key is a pair of floats and the value is a quadruple of 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, the most general approach is where both the keys and value are just a logical projection from the data carried at each node of the tree. 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 

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

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


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