[plt-scheme] Red black trees in PLT Scheme

No time to look into this closely, but you should check out this  
version of red-black trees. It's way, way simpler:

     http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp99

Dave

On Jul 21, 2009, at 1:28 PM, Marek Kubica wrote:

> 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<redblack.scm>_________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme