优化了我的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)的时间复杂度。。。