Red black trees

[Sean Kelly]

Craig Black wrote:
> Sounds like you have plenty of good candidates.  However, I have written a 
> C++ template that has been used and tested extensively.  It is quite simple 
> so it could be ported very quickly if necessary.
> 
> It uses the "AA tree" algorithm.  An AA tree a simplified red-black tree 
> that is much easier to code.  The drawback is that it is supposed to be a 
> little slower than a full red-black tree implementation.  But for some 
> reason all my benchmarks show that it is faster than Microsoft's std::set 
> implementation.

If you're testing against VS 2005 that may be somewhat related to 
checked iterators, depending on how you're doing the testing.  The 
checking occurs even in release builds.


Sean