AVL vs Red-Black tree

[Daniel K. O.]

On 2/15/07, Paolo Carlini <pcarlini@suse.de> wrote:
> Please be patient, thanks.

Well, any response is better than none. :)


> There are lots of issues here. First, you
> should include a pointer to the discussion on comp.lang.c++.moderated
> coming to the conclusion that AVL trees are 100% ok from the conformance
> point of view (in case, detail why your specific version is).

Oh, I forgot to include the link in my original message. My bad.
http://tinyurl.com/36lnro

See John Potter's responses. The relevant part:
"Yes an AVL tree may perform more rotations to rebalance after an
erase than an RB tree.  [...]  However, the requirements are amortized
across all possible locations.  Because of the amortization, the AVL
tree will still do a constant number of operations after erase.  The
constant may be greater than that for the RB, but it will still be a
constant. [...] It does satisfy
the standard."

If needed I can enumerate all the insertion and deletion requirements
from the standard, and cite more authoritative sources that assert the
AVL tree properties that satisfy the requirements.

Also, if that's relevant, I can describe with more details the
implementation (not that I think the comments for the RB routines are
any clearer). I don't know if it's recommended to incorporate too much
text into the source files.


> Second,
> you should know that this kind of large, ABI-breaking change, can only
> be suited for the next ABI, so-called v7, thus no hurry for current GCC
> mainline, where we are staying with 6.x.

Sure. But ABI breakage could be avoided by simply changing the body of
the functions in tree.cc; unless of course the extra bit required by
an AVL tree node could cause some problem.


> Last but not least, from a
> legal point of view, before the GCC project can even think accepting
> large contributions, a copyright assignment must be on file

Now that's some interesting point: what's considered a "large,
significant contribution"?
I wrote all the code (that is, 2 routines, plus some small changes to
the others) around the libstdc++ implementation, so I would consider
it a derived minor contribution.
But that's no problem, I'm willing to do the paperwork if needed.


Thanks for your attention.

-- 
Daniel K. O.
"The only way to succeed is to build success yourself"