青岛建设房地产招聘信息网站,专业微网站建设公司首选,网站推广页面设计,腾讯oss wordpress目录 AVL树的由来
AVL的实现原理
左单旋
右单旋
先左后右
先右后左
总结 AVL树的由来
查找#xff0c;无论在什么情况下都与我们息息相关。在我们学习数组阶段学习到了线性查找#xff0c;可是它的效率很低下#xff0c;又演变出来了二分查找#xff0c;它的效率非常…目录 AVL树的由来
AVL的实现原理
左单旋
右单旋
先左后右
先右后左
总结 AVL树的由来
查找无论在什么情况下都与我们息息相关。在我们学习数组阶段学习到了线性查找可是它的效率很低下又演变出来了二分查找它的效率非常之高可是缺点也很明显它必须是在有序的情况下才能完成快速查找。后来一种名为搜索二叉树的数据结构诞生它的效率同样也是出类拔萃但是在极端情况下它也会退化成一个链表。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
AVL的实现原理
首先AVL树必须具有一下两个特点
1它的左右子树都是AVL树
2左右子树的高度只差平衡因子不能超过绝对值1-1-0-1 而计算平衡因子的方法可以是左树高度减去右树高度也可以是右数高度减去左树高度这里我们
用到右树高度减左树高度 如果一棵搜索二叉树的高度是平衡的他就是AVL树如果它有n个节点其高度可保持在O(log_2 n)搜索时间复杂度可以保持在O(log_2n)。
那么既然要一颗搜索二叉树保持其左右子树绝对值的高度不超过1那么必然在插入的时候就要维持住它的特性当一边过高时我们需要对其进行调整使它满足这个特性。那么这里要用到的调整就是对高的子树进行旋转。
左单旋 那么这里是我们的一颗树此时可以看出它的右边已经过高那么现在要对它进行左单旋。先回顾一下搜索二叉树的特性左孩子比根节点要小右孩子比根节点要大根据这个特性我们可以看出如果让90来做这个这个根节点岂不是刚好可以又满足了搜索二叉树的特性树的高度也被调整过来了。 那么现在还有一种情况如果cur的左孩子不为空又该如何进行旋转呢 同样我们也可以根据搜索二叉树的特性curleft是一定比parent大的那么我们就可以让curleft去做parent的右边parent做cur的左边cur做新的根节点。
右单旋
同样右单旋和左单旋是一个原理这里我们就只对其右孩子存在的情况进行分析 根据搜索二叉树的原理curright一定比parent小那么我就可以让curright去左parent的左边parent做cur的右边cur做新的根
先左后右
那么现在有一种更复杂的情况 这样一颗树如果只是单纯的进行左旋或者右旋都无法解决问题那么这个时候就需要进行两次旋转才能符合AVL树的条件。根据平衡因子可以得出这棵树是左边偏高所以我们可以让cur来做parentcurright做cur先交换一下角色 当角色交换完之后我们可以根据左单旋的性质对40这颗子树进行旋转。旋转之后在对整棵树进行一个右单旋 经过两次旋转之后的树就又会符合AVL树的性质了。
先右后左
那么既然有左边高的树一定会有右边高的树那么此时我们同样可以进行两次旋转来调整 同样我们可以先调整位置让cur成为parentcurleft成为parent 然后在根据右旋的特性让cur的右边成为parent的左边parent成为cur的右边cur成为新的根 第一次右旋调整结束之后我们继续往上更新接下来进行左旋同样根据左旋的性质cur的leift做parent的右边parent做cur的左边cur做新的根当这一次调整结束之后这棵树又会重新符合条件 总结
有人可能会疑惑如果一边高出更多的情况应该怎么处理答案是这种情况是不会出现的。因为有一个平衡因子在控制着高度使这棵树左右高度不会超过2如果一边高出很多那说明在前面对树进行调整的时候就已经出了问题所以上面的4中旋转适用所有的情况。
