AVL vs Red-Black tree

["Daniel K. O." <danielosmari at gmail dot com>]

Hello everybody.

Some time ago I sent a mail to this mailing list, informing about
performance comparison of libstdc++'s RB tree against an equivalent
AVL tree, for maps, sets, etc. See http://stlavlmap.sourceforge.net

The two responses were (at least the ones I remember):

1) port the code to g++ 4, because the RB tree was optimized from
3.4's libstdc++.
2) there was a possibility for "hinted insertion" on an AVL tree to
not fit in the standard's complexity requirement.

More recently, on comp.lang.c++.moderated, I was informed that AVL
trees satisfy all requirements of the associative containers, as much
as RB trees. So now I finally had time and motivation to update the
code for 4.1.1. If anyone's interested, here's the diff against
stl_tree.h:
http://stlavlmap.sourceforge.net/tree-diff.txt
(before the diff I replaced all "_Rb_" occurrences by "_avl_")

As it can be seen, I just added std:: for some stuffs (as my code
doesn't reside in the std namespace), and renamed the _M_color member
to _M_bal_factor.

The AVL insertion/deletion routines in tree.cpp are very distinct from
libstdc++'s RB routines in tree.cc, so there's no point in diffing it;
but I tried to mimic indentation and variable naming.

As it can be seen (again) in my benchmark results, at
http://stlavlmap.sourceforge.net, the AVL tree is faster for some
operations, but never slower for the rest.

The test codes are very simplistic, and I won't claim they give
conclusive results. So I'm sending this e-mail to:
1) ask if anyone is interested in testing it; my system has too little
memory to create bigger trees, so my measurements may have too much
noise.
2) suggest it to be integrated into libstdc++, if the tests on other
environments confirm my measurements.



Thanks for your attention.

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