C++标准库中是否有任何红黑树或avl树实现？

Question

就像multiset是STL中的二叉搜索树实现一样，是否有任何可用的RB树或AVL树实现？

Answer 1

通常情况下，你不会实现multiset作为二叉树。使用一个会破坏标准的性能保证，因为树可能看起来像一个没有O（logN）插入和删除的链表。

典型地，std::set/std::multiset/std::map/std::multimap被实现为RB树，因为它具有这些性能保证。但这并不是必需的。该标准仅保证容器在不同操作中的性能，并且如何实现该操作取决于实施。

如果你想保证你使用的是RB树，你需要检查你的实现，推出你自己的，或者得到一个保证它是RB树的第三方库。