What’s a Map?
Earlier than studying the info construction utilized by a map, allow us to have an overlook of map.
Map is the a part of the STL library that shops key worth pairs in it and no two values have the identical keys however the totally different keys can retailer related values. The map shops keys in sorted order.
These are some funtions which map makes use of with their Time Complexities:
- insert() – Time Complexity O(Log N)
- delete() – Time Complexity O(Log N)
- erase() – Time Complexity O(Log N)
- discover() – Time Complexity O(Log N)
Which Knowledge Construction is utilized by Map?
Now coming to the purpose that which information construction is utilized by map. The interior implementation of map is self-balancing Binary Tree. There are usually two strategies for implementing a self-balancing binary tree:
These are the 2 strategies howeverÂ
For map’s inner implementation it makes use of Crimson-Black Tree.Â
To stability the tree after an insertion/deletion each algorithms use the notion of rotations the place the nodes of the tree are rotated to carry out the re-balancing. Whereas in each algorithms the insert/delete operations are O(log N), within the case of Crimson-Black tree re-balancing rotation is an O(1) operation whereas with AVL that is an O(log N) operation, making the Crimson-Black Tree extra environment friendly on this side of the re-balancing stage and one of many doable causes that’s extra generally used.
What’s Crimson-Black Tree?
A red-black tree is a form of self-balancing binary search tree the place every node has an additional bit, and that bit is commonly interpreted as the colour (pink or black) which is used to make sure that the tree stays balanced throughout insertions and deletions.
To study extra in regards to the Crimson-Black tree please consult with the article on “Crimson-Black Tree“
Crimson-Black Tree Diagram
