AVL树的实现及原理

目录

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来做parent，curright做cur，先交换一下角色

当角色交换完之后，我们可以根据左单旋的性质对40这颗子树进行旋转。旋转之后在对整棵树进行一个右单旋

经过两次旋转之后的树就又会符合AVL树的性质了。

先右后左

那么既然有左边高的树一定会有右边高的树，那么此时我们同样可以进行两次旋转来调整

同样我们可以先调整位置，让cur成为parent，curleft成为parent

然后在根据右旋的特性，让cur的右边成为parent的左边，parent成为cur的右边，cur成为新的根

第一次右旋调整结束之后，我们继续往上更新，接下来进行左旋，同样根据左旋的性质，cur的leift做parent的右边，parent做cur的左边，cur做新的根，当这一次调整结束之后，这棵树又会重新符合条件

总结

有人可能会疑惑，如果一边高出更多的情况应该怎么处理，答案是这种情况是不会出现的。因为有一个平衡因子在控制着高度使这棵树左右高度不会超过2，如果一边高出很多，那说明在前面对树进行调整的时候就已经出了问题，所以上面的4中旋转适用所有的情况。