红黑树比起AVL树具体更高效在什么地方呢?

发布网友 发布时间：2022-04-28 23:08

我来回答

共3个回答

热心网友 时间：2022-06-24 23:36

优化了我的avl实现，AVL插入和删除并不像教科书上说的，需要回溯到根节点，两种情况下可以直接退出向上回溯：

插入更新时：如果当前节点的高度没有改变，则停止向上回溯父节点。

删除更新时：如果当前节点的高度没有改变，且平衡值在[-1,1]区间则停止回溯。

最终结论，优化过的avl和linux的rbtree放在一起，avl真的和rbtree差不多，avl也并不总需要回溯到根节点，虽然旋转次数多于rbtree，但是rbtree保持平衡除了旋转外还有重新着色的操作，即便不旋转也在拼命的重新着色，且层数较高，1百万个节点的rbtree层数和1千万个节点的avl相同。

所以查询，删除，插入全部放在一起来看，avl树和rbtree差不多。

红黑树属于平衡二叉树。
说它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1。
但红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(n)，这有数学证明。所以它算平衡树，只是不严格。不过严格与否并不影响数据结构的复杂度。
不用严格控制高度，使得插入效率更高。

1.查找

显然，avl树要比红黑树更平衡，因此avl树的查找效率更高。

2.插入

不论是avl树还是红黑树，旋转的时间复杂度都是O(1)

对于avl树，旋转的时候，需要找到第一个不平衡节点，这就需要我们维护一个平衡因子，每一次插入，旋转，删除等操作，都要更新从跟节点到被修改节点这个路径上的平衡因子。。。最差情况下，需要O(logn)的时间复杂度。。。

热心网友 时间：2022-06-24 23:37

对于红黑树，除了旋转外，最差情况下也需要O(logn)的时间复杂度来调整平衡，注意这只是极端情况下，比如父节点和伯父节点都是红色，曾祖父节点也是红色，这个时候，就要递归的去平衡父节点，然而，采用自顶向下的方法（就是如果一个节点的两个子节点都是红色，就把这个节点变成红色，它的两个子节点变成黑色），减少了多次旋转操作，但也使得调整颜色的操作时间复杂度最差情况下是O(logn)。但这仅仅是很少的情况，所以红黑树的插入操作统计上比avl树要好。。。

热心网友 时间：2022-06-24 23:37

对于avl树，删除意味着某个子树深度减少，这个时候，我们找到第一个不平衡的点，像插入操作那样进行旋转，使得子树平衡，然后，递归的使它的祖先节点也平衡。。。

对于红黑树，也是只有个别情况才会递归平衡父节点，它发生在：兄弟节点是黑色，两个侄儿也是黑色。当兄弟节点是红色的时候，转化为兄弟节点是黑色的情况处理，当两个侄儿有红色节点的时候，则在常数时间内就可以达到平衡。所以，删除操作红黑树的平均效率也比avl树高。