Re: AVL vs Red-Black tree

[Gabriel Dos Reis <gdr at cs dot tamu dot edu>]

Benjamin Kosnik <bkoz@redhat.com> writes:

| Just a follow-up to what Paolo said...
| 
| > 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.
| 
| I'd be more interested in looking at this if you could provide
| performance measurements based on libstdc++'s own performance
| testsuite. Ie, "make check-performance."

Fully agreed.  Matt Austern and others at AT&T implemented a framework
for binary trees -- it can instantiate to several kind of binary
trees.  They did some measurements and the conclusion is that most
many tests, RB trees tend to outform all others.  
I have been told the paper they wrote was prompted by the suggestion
that some form of splay trees might be better.

So, yes, we need numbers on some "rerepsentative" uses.

-- Gaby