我知道STL map/set的主流实现使用的是黑红树。 我的问题是:这些实现是否也在插入/删除元素时自动平衡树？
如果不是，那么元素排序插入时，总是追加到最右边的位置。最差的查找成本是 O(n)。
那么，黑红树会自动平衡吗？
最佳答案
是的。红黑树进行节点轮换，保证树保持平衡
关于c++ - std::map 是否自动平衡自身，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41312329/
我知道STL map/set的主流实现使用的是黑红树。 我的问题是:这些实现是否也在插入/删除元素时自动平衡树？
如果不是，那么元素排序插入时，总是追加到最右边的位置。最差的查找成本是 O(n)。
那么，黑红树会自动平衡吗？
最佳答案
是的。红黑树进行节点轮换，保证树保持平衡
关于c++ - std::map 是否自动平衡自身，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41312329/