Here is a nice starting point for a generic rb tree structure in SML.
(* generic red-black-tree in Standard Jersey ML *)
type key = string
datatype color = R | B
datatype tree = E | T of (color * tree * key * tree)
fun rbmem (x, E) = false
| rbmem (x, T (_,a,y,b)) =
if x < y then rbmem (x,a)
else
if x > y then rbmem (x,b)
else
true
fun balance ( (B,T (R,T (R,a,x,b),y,c),z,d)
| (B,T (R,a,x,T (R,b,y,c)),z,d)
| (B,a,x,T (R,T (R,b,y,c),z,d))
| (B,a,x,T (R,b,y,T (R,c,z,d)))) = T (R,T (B,a,x,b),y,T (B,c,z,d))
| balance body = T body
fun insert (x,s) =
let fun ins E = T (R,E,x,E)
| ins (s as T (color,a,y,b)) =
if x < y then balance (color,(ins a),y,b)
else if x > y then balance (color,a,y,(ins b))
else s
val T (_,a,y,b) = ins s (* guaranteed to be non-empty *)
in T (B,a,y,b)
end
