我已经阅读了一些关于自平衡二叉树的问题和答案，但并不是全部都很熟悉。
我知道的第一个是AVL，第二个是红黑树。
有一些我不太理解的地方：根据一些书籍和文章，AVL树可以比红黑树搜索稍微快一点，这是可以理解的。
那么红黑树相对于AVL树的优势是什么？
在AVL树中，可能需要在每次插入之后检查平衡，而在红黑树中我们不必频繁地做这样的事情，对吗？
PS： 我在SO上搜索了类似的内容，但是没有得到满意的答案。 希望一些朋友能给我一个关于自平衡树的详细比较。
平衡二叉搜索树的比较
3
- Alcott
1个回答
2
一棵AVL树具有以下特性：从每个节点开始，左右子树的高度差最多为2。
另一方面，在红黑树中，任何节点的左或右子树的高度最多是另一棵树的两倍。也就是说，它们之间最多相差一个因子2。
这直观地表明，在AVL树中查找平均确实更快。
然而，在插入或删除节点时，我们必须更频繁地重新平衡AVL树，以保持更严格的高度不变量（另一方面，在红黑树中重新平衡的算法要复杂得多）。这意味着在实践中，红黑树可能比AVL树表现得更好，尤其是在经常改变时。
另一方面，在红黑树中，任何节点的左或右子树的高度最多是另一棵树的两倍。也就是说，它们之间最多相差一个因子2。
这直观地表明，在AVL树中查找平均确实更快。
然而，在插入或删除节点时，我们必须更频繁地重新平衡AVL树，以保持更严格的高度不变量（另一方面，在红黑树中重新平衡的算法要复杂得多）。这意味着在实践中，红黑树可能比AVL树表现得更好，尤其是在经常改变时。
- Konrad Rudolph
4
谢谢你的回答。你的意思是，红黑树唯一优于AVL树的地方在于红黑树执行更少的重新平衡操作，并且如果我们需要频繁进行更新（插入/删除），那么使用红黑树会更加方便？ - Alcott
@Alcott 实际上是这样的。在实践中，红黑树在大多数情况下优于AVL树。AVL树在构建树后仅用于查找的情况下表现更好。但在这种情况下，您根本不需要自平衡树：由于它是静态的，可以手动平衡一次。 - Konrad Rudolph
我知道B树在数据库领域很流行，我也读了几篇关于B树在数据库中应用的文章，但我仍然不太明白数据是如何在磁盘上排列以及如何保持B树结构在磁盘上？ - Alcott
@Alcott => 新问题。简短的回答是：B树具有更好的引用局部性。其他方面与主存储器基本相同。 - Konrad Rudolph
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接