What is a Map?
Before learning the data structure used by a map, let us have an overlook of map.
Map is the part of the STL library that stores key value pairs in it and no two values have the same keys but the different keys can store similar values. The map stores keys in sorted order.
These are some funtions which map uses with their Time Complexities:
- insert() – Time Complexity O(Log N)
- delete() – Time Complexity O(Log N)
- erase() – Time Complexity O(Log N)
- find() – Time Complexity O(Log N)
Which Data Structure is used by Map?
Now coming to the point that which data structure is used by map. The internal implementation of map is self-balancing Binary Tree. There are generally two methods for implementing a self-balancing binary tree:
These are the two methods but
For map’s internal implementation it uses Red-Black Tree.
To balance the tree after an insertion/deletion 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 an 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 is more commonly used.
What is Red-Black Tree?
A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black) which is used to ensure that the tree remains balanced during insertions and deletions.
To learn more about the Red-Black tree please refer to the article on “Red-Black Tree“
Red-Black Tree Diagram
