Red black trees

[Craig Black]

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.

Anyway, I could do it in D if you are intereseted but I won't bother if you 
already have a solution.

-Craig