This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: AVL vs Red-Black tree
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"