Balancing a C++ set

Question

As C++ sets are implemented in binary trees, if we insert items in incremental or decremental order, then the set would be more a list than a tree. Is there any method to balance the tree AFTER items are inserted?

Answer 1

C++ sets (i.e. std::set) are usually implemented as red-black trees. They are self balancing.

However it is implemented, your suggestion that the set would become more like a list cannot happen, because the standard makes complexity guarantees which cannot be fulfilled by a list.

Answer 2

Although the standard imposes no restrictions on the implementation, it's usually a red-black tree. So the library deal with it well, and don't worry about it

Look this problem