std :: map自动平衡本身

Question

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

如果不是，那么当元素被排序并插入时，它将始终附加到最右边的位置。最坏的查找成本是O（n）。

那么，黑红树自动平衡自身呢？

Answer 1

看看insert和erasestd :: map操作。

这是保证这些操作的最糟糕的复杂性是对数。

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

对于std :: set也是如此。

Answer 2

是的。红黑树执行节点旋转以确保树保持平衡

Answer 3

是的。在每次插入后的红黑树中，如果树不平衡，树中的一些元素将移动到新位置。