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

Question

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

如果没有，那么当元素排序和插入时，它总是追加到最右边的位置。最差的查找成本是 O(n)。

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

Answer 1

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

可以保证这些操作的最坏复杂度是对数的。

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

对于std::set也是如此。