From: mark hahn <mchahn@...>
Date: 2001-11-27T04:18:49+09:00
Subject: [ruby-talk:26540] Re: ++operator and sorted hashes

It uses counts instead of red/black bits.  It counts read accesses on each
of left and right siblings, where writes are considered to include a read.

The red/black alogrithm does not balance based on key frequency statistics
as this algorithm does.  Also the red/black only keeps the tree balanced
within a factor of two where this one approaches perfect balancing.  The
execution cost is effectively the same as the red-black.

I did this for a course taught by Knuth in 1970.  At that time he said it
was unique.  I have no idea if it is now.

----- Original Message -----
From: "John Tromp" <tromp@cwi.nl>
Newsgroups: comp.lang.ruby
To: "ruby-talk ML" <ruby-talk@ruby-lang.org>; <undisclosed-recipients:>
Sent: Sunday, November 25, 2001 9:05 PM
Subject: [ruby-talk:26483] Re: ++operator and sorted hashes


> Mark Hahn wrote:
>
> >> miss the sortedTreeMap class from Java, which is a good general
> >> implementation of sorted maps.  I have an interesting algorithm for
> >> automatically balanced trees that I have been considering implementing
in
> >> Ruby.
> >
> > That sounds really interessting! Are you going to implement it ?
>
> And how does your algorithm differ from red-black trees?
>
> --
> regards,
> -John
>
>
> -----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
> http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
> -----==  Over 80,000 Newsgroups - 16 Different Servers! =-----
>