c++ - std::map 是否自动平衡自身

Question

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

如果不是，那么在对元素进行排序和插入时，它将始终附加到最右边的位置。最差的查找成本是 O(n)。

那么，黑红树会自动平衡吗？

Answer 1

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

Answer 2

看一下插入和擦除 std::map操作。

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

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

对于std::set也是如此。

Answer 3

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