我知道STL map / set的主流实现使用黑红树.
我的问题是：插入/删除元素时这些实现是否也自动平衡树？

如果没有,那么当元素被排序和插入时,它将始终附加到最右边的位置.最差的查找成本是O(n).

那么,黑红树自动平衡了吗？

解决方法:

看看insert和erase std :: map操作.

保证这些操作的最差复杂性是对数的.

事实上,使用哪种树来实现std :: map并不重要.但是这棵树必须为插入,擦除和其他一些操作提供必要的复杂性.基本上它意味着树必须平衡(当然,当元素插入或移出时自动平衡).

对于std :: set也是如此.