[plt-scheme] Red black trees in PLT Scheme

Hi,

I am currently trying to implement red black trees in Scheme as they
are in Introduction to Algorithms (CLRS), 2nd edition (see source code
attached).

I know that this code is not nice and definitely not functional (Eli
suggested to use match which I will do once I get this working
correctly) and full of mutable state, but I thought it might be a nice
exercise to see how it looks in Scheme.

But unfortunately, I ran into some problem and I am not sure whether it
is not a problem with the algorithm in the book itself (sorry to all
those who don't have access to the book, but there is no publicly
available version of this).

I am creating a tree that looks like this:

     *4*
 *3*     *5*
2           6

where the *bold* numbers represent black nodes (I can also provide
scans of my sketches on paper, but posting images on a mailing list
isn't usually a good idea).

Now I am removing the 2 node:

     *4*
 *3*     *5*
            6

This works fine, because it does not trigger any rb-delete-fixup
operations, when I try to delete 3 it fails, because it calls
(rb-delete-fixup T x) with x being (void) (this should be CLRS, Case IV
according to the Java applet mentioned in the header). Playing the
algorithm on paper this should be correct, since z is 3, y is also 3
and x is the right node of 3, which is (void), the book calls it NIL[T].
Attaching that to the parent node of 3 works (set-rb-node-left!)
correctly, but then the algorithm does a (rb-delete-fixup T x) and tries
to access the parent of (void)/NIL[T] which, of course fails.

Could anyone have a look at this and tell me what the problem is? I
thought about introducing a temporary node where x is, so that the
parent-getting succeeds, but this does not feel like a good solution.

Oh, I also implemented GraphViz dot output, so you can let GraphViz
visualize the trees that get created; it already helped me with
debugging rb-insert.

Thanks in advance!

regards,
Marek
-------------- next part --------------
A non-text attachment was scrubbed...
Name: redblack.scm
Type: text/x-scheme
Size: 11107 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20090721/13fdff37/attachment.bin>