我在avl树搜索速度更快但无法理解的几个地方阅读过它。据我了解:红黑树的最大高度 = 2*log(N+1) AVL 树的高度 = 1.44*logo(N+1)
是因为AVL更短吗?
我在avl树搜索速度更快但无法理解的几个地方阅读过它。据我了解:红黑树的最大高度 = 2*log(N+1) AVL 树的高度 = 1.44*logo(N+1)
是因为AVL更短吗?
是的。
查找项目所需的步骤数取决于项目与根之间的距离。
由于 AVL 树封装得更紧密(即它的最大高度较低),这意味着比红黑情况下更多的项目更靠近根。
超紧的包装也意味着 AVL 树在插入元素时需要更多的工作。任何应用程序的最佳选择取决于它是插入密集型还是搜索密集型......
如果输入键几乎是升序/降序,AVL 树比红黑树要好,因为那时我们必须进行单次旋转(左-左或右-右大小写)来添加此元素。此外,由于树将是紧密平衡的,因此搜索也会更快。
但是对于随机选择的输入键,RBTree 更好,因为与 AVL 相比,它们需要更少的旋转来插入。
总的来说,它取决于输入序列,这将决定我们的树的倾斜程度以及执行的操作。对于插入密集型使用红黑树,对于搜索密集型使用 AVL。
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。