我在几个地方读到过avl树搜索更快，但无法理解。据我所知： 红黑树的最大高度 = 2 * log(N + 1) AVL树的高度 = 1.44 * log(N + 1)
这是因为AVL树更矮吗？
为什么AVL树在搜索方面比红黑树更快？
10
- paseena
2
阅读一本关于数据结构的书。但如果我记得没错的话，AVL树比红黑树更接近完美平衡，但插入一个元素到AVL树中的代价比插入到红黑树中显著地更高。 - user2100815
是的，因为它更短，所以从上到下的节点较少。也许一张图片会有帮助：http://en.wikipedia.org/wiki/File:AVL_Tree_Rebalancing.svg - patrick
3个回答
17
是的。
查找一个元素所需的步骤数量取决于该元素与根节点之间的距离。
由于AVL树更加紧密（即其最大高度较低），这意味着比红黑树更多的元素更接近根节点。
这种额外的紧密性也意味着在插入元素时，AVL树需要更多的工作。任何应用程序的最佳选择取决于它是否面向插入或搜索...
- Andrei
1
1很好的解释。我只能加一些数字：在AVL树中，节点深度之间的最大差值为1，在R-B树中，一个节点可以比另一个节点深两倍（深度为节点与根之间的距离）。但是在R-B树中插入和删除最多需要3次旋转，而AVL树可能需要旋转次数等于树的深度。（旋转是平衡树中的基本操作，我不会在此描述） - Anton Guryanov
5
如果输入键值近乎升序/降序，则AVL树比红黑树更好，因为我们只需要进行单旋转（左-左或右-右情况）就可以添加此元素。此外，由于树会保持紧密平衡，因此搜索速度也会更快。
但是对于随机选择的输入键，红黑树更好，因为它们相对于AVL树需要更少的旋转来插入元素。
总的来说，这取决于输入序列，它将决定我们的树有多倾斜以及所执行的操作。对于插入密集型使用红黑树，对于搜索密集型使用AVL树。
- Decipher
1
AVL树和RB树都有各自的优缺点。如果您已经了解它们的工作原理，您会更好地理解这一点。
在插入操作中，AVL比RBTree稍快，因为插入最多涉及一个旋转，而RBTree可能涉及两个旋转。
RBTree只需要最多三次旋转就能删除节点，但AVL不能保证这一点。因此，它可以比AVL更快地删除节点。
然而，最重要的是，它们都有严格的对数树高。
选择任何子树，使AVL“平衡”的属性保证两个子树之间高度差最多为1，也就是说，整棵树是严格平衡的。
但是对于RBTree而言，规则变得更加“松散”，因为RBTree的属性只能保证树的深度不大于节点总数的对数的两倍。
以下是可能更精确的一些事实：
AVL树的高度严格小于：1.44log（n + 2）-0.328（近似值）
红黑树的高度最多为2log（n + 1）
在插入操作中，AVL比RBTree稍快，因为插入最多涉及一个旋转，而RBTree可能涉及两个旋转。
RBTree只需要最多三次旋转就能删除节点，但AVL不能保证这一点。因此，它可以比AVL更快地删除节点。
然而，最重要的是，它们都有严格的对数树高。
选择任何子树，使AVL“平衡”的属性保证两个子树之间高度差最多为1，也就是说，整棵树是严格平衡的。
但是对于RBTree而言，规则变得更加“松散”，因为RBTree的属性只能保证树的深度不大于节点总数的对数的两倍。
以下是可能更精确的一些事实：
AVL树的高度严格小于：1.44log（n + 2）-0.328（近似值）
红黑树的高度最多为2log（n + 1）
请查看https://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures以获取详细信息。
- Determinant
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接