data-structures - 平衡二叉搜索树的比较

Question

我已经阅读了一些关于自平衡二叉树的问答，但我对所有这些都不太熟悉。

我认识的第一个是 AVL，第二个是红黑树。

有一点我不太明白：根据一些书籍和文章，AVL 执行搜索的速度比红黑树快一点，嗯，这是可以理解的。

1. 那么红黑树相对于 AVL 的优势是什么？

2. 在 AVL 中，可能在每次插入之后，我们都必须检查平衡，但在红黑树中，我们不必经常做类似的事情，对吧？

PS：我搜索了类似的东西，但我没有得到令人满意的答案。希望有朋友可以给我详细的自平衡树对比。

Answer 1

AVL树具有以下性质：从每个节点来看，左右子树的高度差最多为2。

另一方面，在红黑树中，任何节点的左子树或右子树的高度最多是另一棵树高度的两倍。也就是说，它们最多相差 2 倍。

这直观地表明，平均而言，在 AVL 树中查找确实更快。

但是，在插入或删除节点时，我们必须更频繁地重新平衡 AVL 树，以保持更严格的高度不变量（另一方面，红黑树中的重新平衡在算法上要复杂得多）。这意味着在实践中，红黑树的性能可能比 AVL 树好得多，尤其是当它经常更改时。