std :: map自動平衡本身

Question

我知道STL map/set的主流實現使用黑紅色的樹。 我的問題是：這些實現是否在插入/刪除元素時自動平衡樹？

如果不是，那麼當元素被排序並插入時，它將始終附加到最右邊的位置。最壞的查找成本是O（n）。

那麼，黑紅樹自動平衡自身呢？

Answer 1

看看insert和erasestd :: map操作。

這是保證這些操作的最糟糕的複雜性是對數。

事實上，使用哪種類型的樹來實現std :: map並不重要。但是這棵樹必須提供插入,擦除和一些其他操作的必要的複雜性。基本上它意味着樹必須是平衡的（當然，當元素被插入或移除時自動平衡自身）。

對於std :: set也是如此。

Answer 2

是的。紅黑樹執行節點旋轉以確保樹保持平衡

Answer 3

是的。在每次插入後的紅黑樹中，如果樹不平衡，樹中的一些元素將移動到新位置。