[plt-scheme] Red black trees in PLT Scheme

From: Carl Eastlund (carl.eastlund at gmail.com)
Date: Wed Jul 22 02:51:55 EDT 2009

On Wed, Jul 22, 2009 at 2:46 AM, Marek Kubica<marek at xivilization.net> wrote:
> On Tue, 21 Jul 2009 21:11:38 -0400
> Dave Herman <dherman at ccs.neu.edu> wrote:
>> 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
> Yes, this is the SML version with pattern matching. I'd like to go
> without pattern matching at first, so I can implement it like in CLRS,
> reimplement it with pattern matching and have a good comparison.
> regards,
> Marek

Pattern matching is not the only difference here -- CLRS presents
mutable trees, right?  Okasaki's are immutable, so rather than mutate
an existing tree you build a new one, reconstructing only the changed
nodes.  So be careful, in your comparison, about which aspects of the
trees are making the difference in your code.


Posted on the users mailing list.