AVL是(Adelson-Velskii 和 Landis) 在1962年的论文中提出的解决二叉树不平衡的一种数据结构.
为什么需要AVL
在BST中, 如果我们按照顺序插入元素, 那么BST会形成最坏的情况: 退化为链表, 那么就失去了原本的O(logN)的时间复杂度, 转而变为O(N)的时间复杂度. 如下图所示:
造成这个问题的原因是因为: 我们的BST发生了不平衡的情况. AVL数据结构就是为了解决这个问题.
如何保证树的平衡
很简单的一种情况, 我们让每个节点的左右子树都具有相同的高度, 这种想法不要求树的深度. 因此设想一下, 某个节点的左右子树都很深, 这样该节点的左右子树实际上都是一个链表.
另一种平衡条件要求每个节点都左右子树都必须有相同的高度, 但该方式太严格, 难以使用.
AVL的平衡要求
AVL要求每个节点都左子树和右子树的高度最多相差为1. (如果没有左右子树, 高度为1).
AVL平衡基础
节点高度
前面提到AVL的平衡要求, 因此需要对每个节点进行高度的标注 (编程上每个节点的结构都需要附带一个高度值). 如下图所示
根据AVL的性质, 左边的二叉树是AVL树, 右边的则不是AVL树, 因为不满足AVL平衡要求.
根据图就可以看出来, 节点的高度计算为: s(h) = max(s.left.h, s.right.h) + 1
平衡因子
前面提到了AVL树存在节点高度, 有了节点高度, 就可以据此 计算出来平衡因子.
平衡因子的计算为 s(f) = abs(s.left.h - s.right.h), 有了平衡因子, 就可以判断当前节点是否满足AVL的性质, 如果 s(f) > 1 则不平衡, 此时需要进行处理. 处理的方式也成为 AVL旋转
AVL旋转
在进行AVL旋转之前, 先要搞清楚什么情况会导致二叉树不平衡.
对二叉树的添加和删除会破坏树的平衡性, 此时就需要进行旋转了. 不过AVL的旋转添加和删除都会导致, 因此我们将从添加操作开始引出AVL树的旋转算法, 在删除操作的时候可以复用这些旋转算法.
以前面图中展示的平衡二分搜索树为例, 此时往该树中添加元6, 就得到了一棵新的二分搜索树, 不过它是不平衡的 (8这个节点平衡因子大于1), 如图所示:
对于二叉树来说, 任意节点最多有两个字节点, 因此高度不平衡时, 该节点的两棵子树高度差为2 (添加和删除每次都是一个节点, 同时本次不平衡的时候就会执行旋转操作).
这样不平衡的情况就分为以下4种情形
LL (左儿子的左子树)
如图所示, 插入节点6造成了8所在的节点不平衡, 这种情况叫做LL
对于LL, 需要进行一次旋转来保证AVL的性质.
那么怎么进行旋转呢?
对于插入节点6来说, 插入路径是 6 <- 7 <- 8 <-5 , 因此不平衡的情况也只会发生在这条路径上, 只要沿着该路径向上回溯, 通过计算平衡因子看是否满足AVL性质, 如果出现不满足的节点, 就进行一次旋转,旋转过程如图:
从图上可以看出旋转过程涉及8和7两个节点, 发生不平衡的节点是8, 通过旋转操作后对于同样在路径上的5来说平衡因子是满足AVL要求的, 因此并不需要旋转.
我们把上面描述的旋转过程成为 右旋转
旋转可以描述为:
8->Left = 7->Right
7->Right = 8
RR (右儿子的右子树)
和LL相对应的一种情况是RR, 对于RR情况的修复操作称为左旋转, 具体方式和LL的右旋转相差不大, 如图:
旋转可以描述为:
Y->Right = X->Left
X->Left = Y
单旋转总结
前面提到的LL和RR两种单旋转，属于对称的旋转，有时候也叫它们为单旋转，这一小节通过一个完整的插入示例来对单旋转整体来做一个总结。
插入节点4的时候依旧保持BST以及AVL的性质，插入节点5后以2为节点的右子树高度为3，左子树高度为1，因此引发了一次左旋转，旋转之后满足AVL的性质，同时也满足BST的性质。
下图描述了另一种情况，插入节点11后，根节点3和节点4都不平衡了，但由于向上回溯，因此首先会对节点4进行旋转，而旋转后节点3和4都满足了AVL性质，此时3就不需要处理了。
因此在编程的时候需要格外注意：由旋转引起的局部变化，树的其余部分需要知道该变化。
LR
前面描述的LL和RR情况都是插入的元素在不平衡节点的左侧的左侧以及右侧的右侧。
但由于每个节点都有两个子节点，因此插入的元素有可能在不平衡节点的左侧的右侧以及右侧的左侧，这两种情况的旋转称为LR和RL，也叫做双旋转。
来看一种LR的情况，如下图所示，三个节点的大小关系为 k1 < k2 < k3，从图中可以看出，使用前面描述的LL和RR情况旋转后都不能满足大小关系。因此对于LR的情况，单纯的左旋转和右旋转都不能满足。
对于LR情形，为了解决这个问题，就需要使用左-右双旋转。来看对于上图，通过左-右双旋转旋转后得到的样子：
此时是满足前面描述的大小关系的，那么左-右双旋转具体是如何操作的呢？通过下面这张图来说明：
首先对k3的左节点k1进行左旋转，得到一个旋转结果后在对k3进行右旋转，经过两次旋转后，得到一棵新树，这棵树是满足AVL性质的，同时也满足BST的性质。
LR的旋转过程可以描述为：
// 左旋转
k1.right= k2.left
k2.left = k1
// 右旋转
k3.left = k2.right
k2.right = k3
RL
RL和LR的左-右双旋转差不多，通过右-左双旋转调整插入元素在节点的右子树的左子树，如下图所示：
首先对k3节点进行右旋转，得到一个新的旋转结果后，在对k1进行左旋转，经过两次旋转后，新的树满足AVL以及BST的性质。
RL的旋转过程可以描述为：
//右旋转
k3.left =k2.right
k2.right = k3
//左旋转
k1.right = k2.left
k2.left = k1
