Re:Left-leaning Red-Black Trees (2008) [pdf]
by amelius on Monday April 06, 2015 @12:41PM
(#9329045)
I'm wondering, are there any efficient immutable (i.e., purely functional) implementations out there?
[ Parent
| on HN ]
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
Re:Left-leaning Red-Black Trees (2008) [pdf]
by deskglass on Monday April 06, 2015 @01:11PM
(#9329222)
If you mean functional red-black trees in general, then there's http://matt.might.net/articles/red-black-delete/