Is there a standard library for Red-Black Trees in C++? [duplicate]

Just like multiset is a Binary Search Tree implementation in STL, is there any RB tree or AVL tree implementation available?

Solution 1:

Normally you would not implement a multiset as a binary search tree. Using one would break the performance guarantees of the standard as the tree could wind up looking like a linked list which does not have O(logN) insert and removals.

Typically std::set/std::multiset/std::map/std::multimap are implemented as a RB tree as it has those performance guarantees. This is not required though. The standard only guarantees the performance of the container in different operations and it is up to the implementation how to achieve that.

If you want to guarantee you are using an RB tree you either need to check your implementation, roll your own, or get a third party library that guarantees it is a RB tree.

Solution 2:

From what I was told on my post is No, there is not a standard C++ library yet for Red-Black Trees as of today, January 10th, 2022.