Does std::map auto balance itself

Question

I know that mainstream implementations of STL map/set use black-red trees. My question is: do these implementations also auto-balance the tree when inserting/deleting elements?

If not, then when the elements are sorted and inserted, it will always append to the rightmost place. The worst lookup cost is O(n).

So, does the black-red tree auto-balance itself?

Answer 1

Take a look at the insert and erase std::map operations.

It is guaranteed that the worst complexity for these operations is logarithmic.

In fact it is not important which type of a tree is used to implement an std::map. But this tree must provide necessary complexity for insert, erase and some other operations. Basically it means that the tree must be balanced (and, of course, auto-balance itself when elements are inserted into or removed from).

The same is true for an std::set.

Answer 2

Yes. Red-black trees perform node rotations to ensure that the tree remains balanced