10

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

是因为AVL更短吗?

4

3 回答 3

17

是的。

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

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

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

于 2011-05-20T21:21:35.903 回答
5

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

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

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

于 2012-12-02T10:23:47.733 回答
1

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

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

于 2013-06-11T06:01:11.837 回答