[plt-scheme] Red black trees in PLT Scheme

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.

--Carl