[plt-scheme] Red black trees in PLT Scheme

If "code size" and "elegance" are your *primary* criteria, then
Okasaki's paper explains very clearly why his version will win hands
down.  (It is a truly beautiful presentation, and his reduction of all
four invariant-violating cases to one has a "God's Book" feel to it.)

Shriram

On Wed, Jul 22, 2009 at 3:01 AM, Marek Kubica<marek at xivilization.net> wrote:
> 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
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>