[jstimpfle]

I've implemented a red-black tree a while ago and wrote a post about it: http://jstimpfle.de/blah/rbtree/main.html

Technically it's been a solid implementation and the post probably contains a few helpful bits. But I overengineered the implementation by splitting in too many source files, and relying on source code generation.

A much cleaner "no bullshit" version of it now lives as part of my current project: https://github.com/jstimpfle/astedit . I've also added augmentation facilities (not heavily tested). I think it's pretty good, I just might open up the internals even more than they already are.

(I think the std::map approach from STL definitely has merits, especially when one needs just an associative container, quickly. But it's not a very efficient nor flexible approach.)

That project also has a text rope implementation that uses the red-black tree. I think a rope is much like a B-tree, but I might be wrong.

Also have a look at the linux kernel rbtree implementation. But I think it's not easily usable outside the linux tree.