News for hackers. Stuff that matters.
Re:Left-leaning Red-Black Trees (2008) [pdf] by YAYERKA on Monday April 06, 2015 @01:51PM (#9329522)
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

There are no comments on this comment yet.