C++標準庫中是否有任何紅黑樹或avl樹實現？

Question

就像multiset是STL中的二叉搜索樹實現一樣，是否有任何可用的RB樹或AVL樹實現？

Answer 1

通常情況下，你不會實現multiset作爲二叉樹。使用一個會破壞標準的性能保證，因爲樹可能看起來像一個沒有O（logN）插入和刪除的鏈表。

典型地，std::set/std::multiset/std::map/std::multimap被實現爲RB樹，因爲它具有這些性能保證。但這並不是必需的。該標準僅保證容器在不同操作中的性能，並且如何實現該操作取決於實施。

如果你想保證你使用的是RB樹，你需要檢查你的實現，推出你自己的，或者得到一個保證它是RB樹的第三方庫。