平衡二叉搜索树的比较
我读过一些关于自平衡二叉树的问答，但我不太熟悉所有这些。
我认识的第一个是AVL，第二个是红黑树。
有一点我不太明白：根据一些书籍和文章，AVL可以比红黑树执行搜索快一点，嗯，这是可以理解的。
那么红黑树相对于AVL的优势是什么？
在AVL中，可能在每次插入后，我们都必须检查平衡性，但在红黑树中我们不必经常做这样的事情，对吧？
附： 我搜索类似的东西，但没有得到满意的答案。 希望有朋友能给我详细的自平衡树对比。
I've read some Q&As about self-balancing binary trees, but I'm not quite familiar with all of them.
The first one of them I got to know is AVL, the second is Red-Black tree.
There are something I don't quite understand: according to some books and articles, AVL can perform searching a little bit faster than Red-Black tree, well, this is understandable.
Then what's Red-Black tree's edge over AVL?
In AVL, probably after each insertion, we have to check for balance, but in Red-Black tree we don't have to do something like that frequently, right?
PS:
I search SO for something similar, but I didn't get satisfying answer.
Hope some friends can give me a detailed comparison of self-balancing trees.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
AVL树具有以下性质：从每个节点来看，左子树和右子树的高度差最多为2。
另一方面，在红黑树中，任意节点的左子树或右子树的高度节点最多是另一棵树高度的两倍。也就是说，它们最多相差 2 倍。
这直观地表明，平均而言，AVL 树中的查找速度确实更快。
然而，当插入或删除节点时，我们必须更频繁地重新平衡 AVL 树，以保持更严格的高度不变性（另一方面，红黑树中的重新平衡在算法上要复杂得多）。这意味着在实践中，红黑树的性能可能比 AVL 树好得多，特别是当它经常更改时。
An AVL tree has the following property: from each node, the difference in height of the left and the right subtree is at most 2.
In a red-black tree, on the other hand, the height of the left or right subtree of any node is at most twice the height of the other tree. That is, they differ at most by a factor of 2.
This shows intuitively that lookup is indeed faster in an AVL tree on average.
However, when inserting or deleting a node, we have to rebalance the AVL tree more often, to preserve the much stricter height invariant (on the other hand, rebalancing in a red-black tree is algorithmically much more complicated). This means that in practice, a red-black tree may perform much better than an AVL tree, in particular when it’s often changed.