Re: AVL vs Red-Black tree

[Benjamin Kosnik <bkoz at redhat dot com>]

> 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.

Of course, there is Ami Tavory's work that is now in libstdc++ and 
included as part of the libstdc++ performance testsuite that attempts to 
qualify this....

See "Tree-Like-Based Containers"
http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/assoc_performance_tests.html

From this, we see that text insert/text find are good with rb tree but 
text find/locality not so good with rb tree.

Thus, our meta-point that these data structures need more 
configurability... it was heartening to see the boost SOC tree work take 
a look at this research.

best,
benjamin