简介

平衡因子：节点的平衡因子为其左子树与右子树的高度差。

AVL树也叫平衡二叉树，是一种自平衡的二叉查找树。它的的递归定义如下：

根节点左右子树的平衡因子的绝对值小于等于1。
其左右子树均为AVL树。

还有另一种解释：AVL树的所有节点的平衡因子的绝对值小于等于1。

为了保证二叉树的平衡，当某个节点的平衡因子的绝对值大于1时，就会触发旋转操作。

旋转之后虽然树的结构会发生改变，但元素的顺序没有发生改变。旋转之后仍然是一颗二分查找树。AVL树的核心便是用树的旋转的方法对二分查找树进行优化。

右旋和左旋

根（root）：被旋转的两颗子树的父节点。
转轴（pivot）：旋转后新的父节点。

左旋和右旋是平衡过程中最基础的操作。

右旋的操作大概为：

将根作为转轴的右儿子。
转轴原本的右儿子作为根的左儿子。

左旋的操作同理。

AVL树

旋转

AVL中树的旋转除了右旋与左旋（LL，RR），还有LR和RL的情况。

首先要明白为什么会出现LR和RL的情况（以上图为例）：

子树深度 $h_a = h_b = h_c = h_p-1$ 。
如果在子树B中插入一个节点，变成了 $h_a=h_c=h_b-1=h_p-2$ 。
此时子树P是平衡的不需要旋转，需要对树R进行右旋操作，旋转后 $h_a = h_c = h_b-1 = h_r-2$ 。
对于新的树P，左右子树显然处于失衡状态，又需要对树P进行左旋操作，回到了刚插入的状态。

如果使用LR操作便可以避免上面的问题，LR操作大概为：

先对左子树进行左旋（可能会触发RL，递归下去即可）。
再进行右旋。

RL操作同理。

其他

AVL树的操作与二分查找树类似，唯一的区别便是在插入与删除之后，如果某个节点的平衡因子的绝对值大于1，会对这颗子树进行旋转操作。这里就不过多讲解。

由于旋转的操作为常数复杂度，且AVL树总是保持平衡的，所以AVL树在查询，插入，删除上的复杂度均为 $O(log_n)$ 。

但是由于其平衡条件非常严格，所以插入时可能会进行大量的旋转操作，产生较大常数。所以AVL多用于修改较少，查询较多的场合。