Comment by wjakob

What's wrong with red-black trees? :) Since you mention C++: you do realize that std::map will typically be implemented with one?