What is a TreeMap? A self-balancing binary search tree. In modern languages, this is normally implemented as a Red-black tree. TreeMap Time Complexity Java TreeMap Java has collection library support (java.util.TreeMap) for TreeMap. C++ TreeMap C++’s std::map is a red-black tree TreeMap Implementation. Note that name is rather tricky here. std::map is TreeMap(ordered) and the more common hashmap is actually std::unordered_map.