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

by

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.

More Related Contents:

  1. How to choose between map and unordered_map?
  2. c++ push reference node to stl list
  3. How can I use std::maps with user-defined types as key?
  4. How to retrieve all keys (or values) from a std::map and put them into a vector?
  5. Const map element access
  6. Why does the C++ STL not provide any “tree” containers?
  7. How to find if a given key exists in a C++ std::map
  8. Looking for C++ STL-like vector class but using stack storage
  9. In STL maps, is it better to use map::insert than []?
  10. Is there a way to access the underlying container of STL container adaptors?
  11. Is the order of iterating through std::map known (and guaranteed by the standard)?
  12. std::map emplace without copying value
  13. Relative performance of std::vector vs. std::list vs. std::slist?
  14. A proper way to create a matrix in c++
  15. Efficiency of the STL priority_queue
  16. How can I sort an STL map by value?
  17. Using std::map where V has no usable default constructor
  18. How can I make the map::find operation case insensitive?
  19. How can I copy one map into another using std::copy?
  20. STL map containing references does not compile
  21. Order Statistic Tree in C++
  22. C++ inserting unique_ptr in map
  23. Initializing a static std::map in C++
  24. How to get a random element from a C++ container?
  25. LRU cache design
  26. c++ sort keeping track of indices [duplicate]
  27. Reorder vector using a vector of indices [duplicate]
  28. Super high performance C/C++ hash map (table, dictionary) [closed]
  29. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  30. Obtain container type from (its) iterator type in C++ (STL)

Leave a Comment