threaded red-black tree

Lex Stein stein at
Mon Sep 15 01:48:29 EDT 2003

Hi, No one responded to my question several weeks ago about a purely
functional implementation of a threaded, red-black tree. My message was
sent about the same time as that flurry of silly emails about "how to
respond to homework questions". Was my message not responded to because it
was classified as a homework question? I assure you this is officework,
not homework. I ended up porting Okasaki's red-black tree implementation;
hacking it apart with a bunch of mutation for the threading of the list
through the tree. However, I'm still missing a deletion function and I
haven't been able to find a prototype (Okasaki's red-black tree module
lacks delete). My study of the RB-tree deletion routine in CLR hasn't yet
yielded an adaptation for a functional environment. Any advice would be
much appreciated.


Lex Stein           
stein at        cell: 617-233-0246

More information about the Haskell-Cafe mailing list