Why is std::map implemented as a red-black tree?

c++ dictionary data-structures stl binary-search-tree
Denis Gorodetskiy picture Denis Gorodetskiy · Mar 13, 2011 · Viewed 89.5k times · Source

Why is std::map implemented as a red-black tree?

There are several balanced binary search trees (BSTs) out there. What were design trade-offs in choosing a red-black tree?

Answer

Chris Taylor picture Chris Taylor · Mar 13, 2011

Probably the two most common self balancing tree algorithms are Red-Black trees and AVL trees. To balance the tree after an insertion/update both algorithms use the notion of rotations where the nodes of the tree are rotated to perform the re-balancing.

While in both algorithms the insert/delete operations are O(log n), in the case of Red-Black tree re-balancing rotation is an O(1) operation while with AVL this is a O(log n) operation, making the Red-Black tree more efficient in this aspect of the re-balancing stage and one of the possible reasons that it is more commonly used.

Red-Black trees are used in most collection libraries, including the offerings from Java and Microsoft .NET Framework.

Related questions

How to choose between map and unordered_map?

Suppose I wanted to map data with a string as the key. What container should I have chosen, map or unordered_map? unordered_map takes up more memory so let's suppose memory isn't an issue, and the concern is speed. …

Read More
How to find if a given key exists in a C++ std::map

I'm trying to check if a given key is in a map and somewhat can't do it: typedef map<string,string>::iterator mi; map<string, string> m; m.insert(make_pair("f","++--")); pair<mi,…

Read More
How can I loop through a C++ map of maps?

How can I loop through a std::map in C++? My map is defined as: std::map< std::string, std::map<std::string, std::string> > For example, the above container holds data like this: m["name1"]["…

Read More