为什么 avl 树搜索速度比红黑树快？
我在几个地方读过 avl 树搜索速度更快，但无法理解。据我了解： 红黑树的最大高度 = 2*log(N+1) AVL树的高度 = 1.44*logo(N+1)
是因为AVL比较短吗？
I have read it in a couple of places that avl tree search faster, but not able to understand. As I understand :
max height of red-black tree = 2*log(N+1)
height of AVL tree = 1.44*logo(N+1)
Is it because AVL is shorter?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的。
找到某个项目所需的步数取决于该项目与根之间的距离。
由于 AVL 树包装得更紧密（即它的最大高度较低），这意味着比红黑情况有更多的项目更靠近根。
额外的紧密包装也意味着 AVL 树在插入元素时需要更多的工作。
任何应用程序的最佳选择取决于它是插入密集型还是搜索密集型......
Yes.
The number of steps required to find an item depends on the distance between the item and the root.
Since the AVL tree is packed tighter (i.e. it has a lower max height) it means more items are closer to the root than in the red-black case.
The extra tight packing also means the AVL tree requires more work when inserting elements.
The best choice for any app depends on whether it is insert intensive or search intensive...
如果输入键几乎是升序/降序，AVL 树比红黑树更好，因为这样我们就必须进行单次旋转（左左或右右情况）来添加此元素。此外，由于树将紧密平衡，搜索也会更快。
但对于随机选择的输入键，RBTree 更好，因为与 AVL 相比，它们需要更少的旋转来插入。
总的来说，它取决于输入序列，这将决定我们的树的倾斜程度以及执行的操作。对于插入密集型使用红黑树，对于搜索密集型使用 AVL。
AVL tree is better than red-black tree if the input key is almost ascending/descending because then we would have to do single rotation(left-left or right-right case) to add this element. Also, since the tree would be tightly balanced, the search would also be faster.
But for randomly selected input key, RBTree are better since they require less rotation for insertion in comparison to AVL.
Overall, it depends on the input sequence, which would decide how tilted our tree is, and the operation performed.For insert-intensive use Red-Black Tree and for search-intensive use AVL.
AVL树和RBTree确实有各自的优点和缺点。如果您已经了解了它们的工作原理，您会更好地理解这一点。
AVL 在插入操作中比 RBTree 稍快，因为插入时最多涉及一次旋转，而 RBTree 可能有两次旋转。
RBTree 在删除时最多只需要 3 次旋转，但在 AVL 中并不能保证这一点。所以它可以比AVL更快地删除节点。
然而，最重要的是，它们都有严格的对数树高。
选取任意一个子树，AVL“平衡”的性质保证两个子子树的高度差最多为1，也就是说，直观上，整棵树是刚性平衡的。
但对于 RBTree 来说，规则可能变得“宽松”，因为 RBTree 的属性只能保证树的深度不大于节点总数对数的两倍。
以下是一些可能更准确的事实：
请参阅 https:// en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structs 了解详细信息。
AVL tree and RBTree do have respective advantages as well as disadvantages. You'll perceive that better if you've already learned how they work.
AVL is slightly faster than RBTree in insert operation because there would be at most one rotation involved in insertion, while there may be two for RBTree.
RBTree only require at most three rotations in deletion, but this is not guaranteed in AVL. So it can delete nodes faster than AVL.
However, above all, they both have strict logarithmic tree height.
Pick up any subtree, the property that makes AVL "balanced" guarantees that the difference of height between two child subtrees is at most one, which is to say, intuitively, the whole tree is rigidly balanced.
But when it comes to an RBTree, the rule becomes likely "looser", since property of RBTree can only guarantee the depth of a tree is not larger than twice as the logarithm of the total number of nodes.
Here're some facts that may be more precise:
See https://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures for detailed information.