std::map 是否自动平衡自身

Question

我知道STLmap/set的主流实现使用黑红树。 我的问题是：当 inserting/deleting 个元素时，这些实现是否也会自动平衡树？

如果不是，那么元素排序插入时，总是追加到最右边。最差的查找成本是 O(n)。

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

Answer 1

是的。红黑树进行节点轮换，保证树保持平衡

Answer 2

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

Answer 3

看看 insert and erase std::map 操作。

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

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

std::set也是如此。