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

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

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

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

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

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

也许最常见的两种自平衡树算法是红黑树和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，这取决于比例。

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

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

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

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

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

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

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

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

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