为什么avl树比红黑树搜索更快？

我已经在几个地方看过它，avl树搜索速度更快，但无法理解。据我所知：红黑树的最大高度= 2 * log（N + 1） AVL树的高度= 1.44 *徽标（N + 1）为什么avl树比红黑树搜索更快？

是否因为AVL较短？

2011-05-20 paseena

阅读关于数据结构的一本书。但是如果我正确地记得（从头顶开始），AVL树近似于比RB树更加接近完美平衡，以插入AVL的代价比RB更昂贵。 – 2011-05-20 21:18:48

是的，因为它更短，因此从上到下节点更少。也许一张照片会有所帮助：http://en.wikipedia.org/wiki/File:AVL_Tree_Rebalancing.svg – 0x4f3759df 2011-05-20 21:19:47

是的。

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

由于AVL树包装得更紧密（即它具有较低的最大高度），这意味着比红黑色案件更接近根部的项目更多。

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

来源

2011-05-20 21:21:35 Andrei

+1好解释 – cnicutar 2011-05-20 21:26:33

一个很好的解释。我只能添加一些数字：AVL树中节点深度的最大差异是1，在R-B树中，一个节点可以比另一个节点深两倍（深度是节点和根之间的距离）。但是R-B树中的插入和删除最多需要3次旋转，而AVL树可能需要与树深相等的旋转次数。（旋转是平衡树木中的基本操作，在这里我不会描述它） – 2013-06-11 07:31:16

如果输入键几乎是上升/下降，AVL树比红黑树好，因为那样我们就必须做单旋转（左 - 左或右 - 右情况）以添加此元素。而且，由于树会紧密平衡，搜索也会更快。

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

总体而言，它取决于输入序列，这将决定如何倾斜，我们的树，和performed.For刀片式密集使用红黑树和搜索集约利用AVL操作。

来源

2012-12-02 10:23:47 Decipher

AVL树和RBTree确实有各自的优点和缺点。如果你已经学会了他们的工作方式，你会更好地理解这一点。

AVL在插入操作略高于RBTree更快，因为会涉及插入最多一个旋转，虽然可能有两个用于RBTree。

RBTree只需要删除最多三个旋转，但这不是在AVL保证。所以它可以比AVL更快地删除节点。

然而，首先，他们都有严格的对数树高。

拿起任何树，这使得AVL“平衡”保证高度的两个子子树之间的差为一个，这就是说，直观的财产，整个树是刚性的平衡。

但是，当涉及到一个RBTree时，由于RBTree的属性只能保证树的深度不会大于节点总数的对数的两倍，所以规则可能变得“松散”。

我这里还有一些事实，可以更精确：

AVL树的高度严格小于：1.44log（N + 2）-0.328 （约）

为红色黑树的高度最大为2log（N + 1）

有关详细信息，请参阅https://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures。

来源

2013-06-11 06:01:11 Determinant

为什么avl树比红黑树搜索更快？

回答

相关问题