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

I've implemented a red-black tree a while ago and wrote a post about it: http://jstimpfle.de/blah/rbtree/main.html 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 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.