data-structures - 为什么 avl 树的搜索速度比红黑树快？

Question

我在avl树搜索速度更快但无法理解的几个地方阅读过它。据我了解：红黑树的最大高度 = 2*log(N+1) AVL 树的高度 = 1.44*logo(N+1)

是因为AVL更短吗？

score 17 · Accepted Answer

是的。

查找项目所需的步骤数取决于项目与根之间的距离。

由于 AVL 树封装得更紧密（即它的最大高度较低），这意味着比红黑情况下更多的项目更靠近根。

超紧的包装也意味着 AVL 树在插入元素时需要更多的工作。任何应用程序的最佳选择取决于它是插入密集型还是搜索密集型......

score 5 · Accepted Answer

如果输入键几乎是升序/降序，AVL 树比红黑树要好，因为那时我们必须进行单次旋转（左-左或右-右大小写）来添加此元素。此外，由于树将是紧密平衡的，因此搜索也会更快。

但是对于随机选择的输入键，RBTree 更好，因为与 AVL 相比，它们需要更少的旋转来插入。

总的来说，它取决于输入序列，这将决定我们的树的倾斜程度以及执行的操作。对于插入密集型使用红黑树，对于搜索密集型使用 AVL。

score 1 · Accepted Answer

AVL 树和 RBTree 各有优缺点。如果您已经了解了它们的工作原理，您会更好地理解这一点。

AVL 在插入操作中比 RBTree 稍快一些，因为插入时最多会涉及一次旋转，而 RBTree 可能有两次。

RBTree 在删除中最多只需要三个轮换，但这在 AVL 中并不能保证。所以它可以比 AVL 更快地删除节点。

然而，最重要的是，它们都具有严格的对数树高。

随便挑一个子树，让AVL“平衡”的属性保证了两个子子树的高度差最多为1，也就是说，直观地说，整棵树是刚性平衡的。

但是对于RBTree，规则可能会变得“宽松”，因为RBTree的属性只能保证树的深度不大于节点总数的对数的两倍。

以下是一些可能更准确的事实：

AVL 树的高度严格小于：1.44log(n+2)-0.328（大约）

红黑树的高度最多为 2log(n+1)

3 回答 3