也许最常见的两种自平衡树算法是红黑树和AVL树。为了在插入/更新后平衡树，两种算法都使用了旋转的概念，其中树的节点被旋转来执行重新平衡。

虽然在这两种算法中插入/删除操作都是O(log n)，但在红黑树重新平衡旋转的情况下，这是一个O(1)操作，而在AVL中，这是一个O(log n)操作，使得红黑树在重新平衡阶段的这方面更有效，这也是它更常用的原因之一。

红黑树在大多数集合库中使用，包括Java和Microsoft . net Framework提供的产品。

这只是你实现的选择——它们可以被实现为任何平衡树。各种选择都可比较，差别不大。因此，任何一个都一样好。

AVL trees have a maximum height of 1.44logn, while RB trees have a maximum of 2logn. Inserting an element in a AVL may imply a rebalance at one point in the tree. The rebalancing finishes the insertion. After insertion of a new leaf, updating the ancestors of that leaf has to be done up to the root, or up to a point where the two subtrees are of equal depth. The probability of having to update k nodes is 1/3^k. Rebalancing is O(1). Removing an element may imply more than one rebalancing (up to half the depth of the tree).

rb树是用二叉搜索树表示的4阶b树。b树中的4个节点会导致等效BST中的两层。在最坏的情况下，树的所有节点都是2节点，只有一条由3节点组成的链直到一个叶子。叶结点到根结点的距离是2logn。

从根节点到插入点，必须将4个节点改为2个节点，以确保任何插入都不会使叶子饱和。插入结束后，必须分析所有这些节点，以确保它们正确地表示4个节点。这也可以在树上完成。全球成本将是相同的。天下没有免费的午餐!从树中删除一个元素的顺序是相同的。

所有这些树都要求节点携带身高、体重、颜色等信息。只有展开树不受这些额外信息的影响。但大多数人都害怕伸展树，因为它们的结构杂乱无章!

最后，树还可以在节点中携带权重信息，从而实现权重平衡。可以应用各种方案。当一个子树包含的元素数量是另一个子树的3倍以上时，应该重新平衡。再平衡是通过单轮或双轮来完成的。这意味着最坏的情况是2.4logn。我们可以用2倍来代替3倍，这是一个更好的比例，但这可能意味着留下略少于1%的子树在这里和那里不平衡。棘手的!

哪种树最好?当然是AVL。它们的编码最简单，高度最差，接近logn。对于包含1000000个元素的树，AVL的高度最多为29,RB为40，权重为36或50，这取决于比例。

还有许多其他变量:随机性、添加、删除、搜索等。

这取决于使用方法。AVL树通常有更多的再平衡旋转。因此，如果您的应用程序没有太多的插入和删除操作，但对搜索的权重很大，那么AVL树可能是一个不错的选择。

map使用红黑树，因为它在节点插入/删除速度和搜索速度之间得到了合理的权衡。

更新2017-06-14:webbertiger在我评论后编辑它的答案。我应该指出，它的答案现在在我看来要好得多。但我保留了我的回答作为补充信息……

由于我认为第一个答案是错误的(更正:不再是两个了)，第三个答案的肯定是错误的。我觉得我有必要澄清一下……

2最流行的树是AVL和红黑(RB)。主要区别在于利用率:

AVL:如果咨询(读)的比例大于操作(修改)的比例更好。内存足迹比RB略小(由于着色所需的位)。 RB:一般情况下，在咨询(阅读)和操作(修改)之间取得平衡，或者更多的修改超过咨询，情况会更好。由于存储红黑旗，内存占用略大。

主要的区别在于颜色。你在RB树中比AVL有更少的重新平衡动作，因为着色使你有时可以跳过或缩短重新平衡动作，这有一个相对高的成本。由于着色的原因，RB树也有更高级别的节点，因为它可以在黑色节点之间接受红色节点(有~2倍以上的可能性)，这使得搜索(读取)效率有点低…但因为它是常数(2x)所以还是O(log n)

如果您考虑修改树的性能影响(显著性)VS咨询树的性能影响(几乎不显著性)，在一般情况下，更倾向于RB而不是AVL是很自然的。

之前的答案只涉及树的选择，红黑可能只是历史原因。

为什么不是哈希表呢?

类型只需要<操作符(比较)作为树中的键。然而，哈希表要求每个键类型都定义了一个哈希函数。对于泛型编程来说，将类型需求保持在最低限度是非常重要的，这样您就可以将它与各种类型和算法一起使用。

设计一个好的哈希表需要对它将要使用的上下文有深入的了解。它应该使用开放寻址，还是链接链接?在调整大小之前，它应该接受什么级别的负载?它应该使用昂贵的哈希来避免冲突，还是使用粗糙而快速的哈希?

因为STL不能预测哪个是应用程序的最佳选择，所以默认值需要更加灵活。树木“只是工作”，而且规模很好。

(c++ 11确实用unordered_map添加了哈希表。你可以从文档中看到，它需要设置策略来配置许多这些选项。)

其他的树呢?

红黑树提供快速查找和自我平衡，不像bst。另一位用户指出了它比自平衡AVL树的优势。

Alexander Stepanov (STL的创造者)说，如果他再次编写std::map，他将使用B*树而不是红黑树，因为它对现代内存缓存更友好。

从那时起，最大的变化之一就是缓存的增长。 缓存丢失的代价非常高，因此引用的局部性要高得多 重要的现在。的低局部性的基于节点的数据结构 参考，就没什么意义了。如果我现在在设计STL，我 会有不同的容器。例如，内存中 对于实现来说，B*树是比红黑树更好的选择 一个关联容器。——亚历山大·斯捷潘诺夫

地图应该总是用树吗?

另一种可能的映射实现是排序向量(插入排序)和二分搜索。这样效果会很好 用于不经常修改但经常查询的容器。 我经常在C中这样做，因为qsort和bsearch是内置的。

我需要使用地图吗?

缓存的考虑意味着使用std::list或std::deque而不是std:vector很少有意义，即使是在我们在学校学到的情况下(比如从列表中间删除一个元素)。 应用同样的推理，使用for循环对列表进行线性搜索通常比为一些查找而构建映射更有效和更干净。

当然，选择一个可读的容器通常比性能更重要。