[plt-scheme] Red black trees in PLT Scheme

On Wed, 22 Jul 2009 02:51:55 -0400
Carl Eastlund <carl.eastlund at gmail.com> wrote:

> 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.

Well, the comparison would be more like code size and elegance,
although doing some benchmarking would help me to see how much faster a
mutable data structure would be.

regards,
Marek