引入
上一篇中已经介绍了二叉搜索树（BST），在二叉搜索树的复杂度分析中，我们提到，二叉搜索树的算法复杂度与其拓扑结构（具体来说是其树的深度）有关。当 BST 最为「平衡」时，查找、删除、插入的算法为 O(\log{n})，而最不平衡情况下，算法复杂度为 O(n)。
当节点数 n 增长时，O(\log{n}) 的算法相对于 O(n) 的算法在运算次数上增长较慢，性能更优。
因此，我们希望按照更加「平衡」的方式构建二叉树。那么，能否让二叉树一层一层地「铺满」，构建出一个完全二叉树？可以的，但是这样的插入算法较为复杂。我们下面介绍一种比较容易实现的解决平衡二叉树的算法——AVL 树，它是由两位俄罗斯数学家 G. M. Adelson-Velsky 和 Evgenii Landis 在 1962 年发明的。
定义
怎样的一棵树可以被称为高度平衡的呢？
一棵 BST 若要成为平衡二叉树，应满足：
- 其左子树和右子树深度之差绝对值不超过 1
- 其左子树和右子树也是平衡二叉树
这是一个具有递归特征的定义。值得注意的是，从定义上说，空树也属于一种特殊的平衡二叉树。
引入平衡因子 (Balance Factor, BF) 的概念，平衡因子是指二叉树上一个节点的左子树与右子树的深度之差。一棵平衡二叉树，其任意节点上的平衡应为 – 1、0 或 1。
根据平衡二叉树的定义，下面给出一些例子，节点左上角标注的是当前节点的平衡因子：
图一是一个平衡二叉树，它满足平衡二叉树的定义。图二不是平衡二叉树，其原因并不是不满足平衡因子的条件，而是因为它不满足 BST 的构成条件，这提醒我们平衡二叉树首先要是一棵 BST。图三满足平衡二叉树的构成条件。图 4 中的节点 (8) 平衡因子为 3，不满足平衡二叉树的要求。
实现原理
概述
AVL 树的实现原理是，在构建 BST 时，时刻对 BST 进行「监督」，即每插入一个节点，便检查插入操作是否破坏了 BST 的平衡性。
如果当前的插入操作破坏了平衡性，那么要找出最小不平衡子树，对其执行某种「旋转」操作来调整其中节点的连接关系，使之重新平衡。
这里所说的最小不平衡子树，指的是以离插入节点最近，且平衡因子绝对值大于 1 的节点为根的子树。（注意：是离插入节点最近，而不是离根节点最近）
那么问题的关键就是，如何进行这种「旋转」调整，使得树始终保持平衡？下面将进行叙述。
根据插入操作发生位置的不同，可以将需要进行调平的情况分成下面四类（记最小不平衡子树的根节点为 N）：
- 情况①：对 N 的左儿子的左子树进行插入之后（左 – 左插入）
- 情况②：对 N 的左儿子的右子树进行插入之后（左 – 右插入）
- 情况③：对 N 的右儿子的左子树进行插入之后（右 – 左插入）
- 情况④：对 N 的右儿子的右子树进行插入之后（右 – 右插入）
下面是四种情况的图示：
可以看出情况①和情况④是对称的，情况②和情况③是对称的，所以在理解上实际只需要理解两种情况，但是在编程时要区分四种情况。
我们先统领性地讲一下针对情况①④和情况②③采用的调平方法：
- 情况①④（即左 – 左和右 – 右），通过单旋转进行调平。
- 情况②③（即左 – 右和右 – 左），通过双旋转进行调平。
下面具体介绍两种旋转方法。
单旋转
单旋转可以用于处理情形①和情形④，其中情形①需要右旋（顺时针旋转）调平，情形④需要左旋（逆时针旋转）调平。下面通过两个实例来理解这里提到的右旋和左旋。
首先看上图的上半部分。向原 BST 中插入节点 (6) 时破坏了 BST 的平衡，标为红色节点 (8) 处为最小不平衡子树的根节点（显然，节点 (6) 是对节点 (8) 左儿子的左子树进行插入，符合情形①）。将以节点 (8) 为根节点的最小不平衡子树「取出」，我们发现，如果对这棵子树进行一次右旋（顺时针旋转），让节点 (7) 成为根节点，节点 (6) 和节点 (8) 成为节点 (7) 的左右子节点，将其放回原 BST，即可保持 BST 的平衡。
同样的，对于情形④，对最小不平衡子树进行一次左旋（顺时针旋转），便可保持 BST 平衡。
下面给出一个更加形式化的操作说明：
如上图，对于情况①，标为红色的 n_2 为其最小不平衡子树的根节点，为了使 BST 重新平衡，将其进行一次右旋，使得 X 抬高一层，Z 下降一层，同时 Y 作为 n_1 的右子树被转移给 n_2 作为左子树。情况④是对称的，不再赘述。
通过单次左旋或右旋，即可调整情况①④导致的不平衡。
双旋转
单次旋转已经可以处理一部分的不平衡，但是针对情况②③，却是无效的，这里用形式化的表示来说明这种无效的情况：
可见，对于情况②，一次旋转并不能消除不平衡。情况③与情况②对称，可想而知结果相同。
对此，需要借助左 – 右双旋转或右 – 左双旋转，下面是一个实例。
节点 (3) 的插入破坏了节点 (4) 处的平衡，节点 (4) 为最小不平衡子树的根节点。如图所示，先执行左旋，再执行右旋，即可通过两次旋转纠正不平衡。
下面给出形式化的操作图示：
代码实现
搞清楚了如何进行通过「旋转」进行调平，便可以写出 AVL 树的代码了。
单旋转
/* 向左单旋转 */
static Position SingleRotateWithLeft(Position K2)
{
Position K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;
K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
K1->Height = Max(Height(K1->Left), K2->Height) + 1;
return K1;
}
/* 向右单旋转 */
static Position SingleRotateWithRight(Position K1)
{
Position K2;
K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;
K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;
K2->Height = Max(Height(K2->Right), K1->Height) + 1;
return K2;
}
双旋转
/* 左 - 右双旋转 */
static Position DoubleRotateWithLeft(Position K3)
{
K3->Left = SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}
/* 右 - 左双旋转 */
static Position DoubleRotateWithRight(Position K1)
{
K1->Right = SingleRotateWithLeft(K1->Right);
return SingleRotateWithRight(K1);
}
插入操作
/* 向 AVL 中插入节点 */
AvlTree Insert(ElementType X, AvlTree T)
{
if (T == NULL)
{
T = malloc(sizeof(struct AvlNode));
if (T == NULL)
FatalError("Out of space!!!");
else
{
T->Element = X;
T->Height = 0;
T->Left = T->Right = NULL;
}
}
else if (X < T->Element)
{
T->Left = Insert(X, T->Left);
if (Height(T->Left) - Height(T->Right) == 2)
if (X < T->Left->Element)
T = SingleRotateWithLeft(T);
else
T = DoubleRotateWithLeft(T);
}
else if (X > T->Element)
{
T->Right = Insert(X, T->Right);
if (Height(T->Right) - Height(T->Left) == 2)
if (X > T->Right->Element)
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
参考资料
[1] 程杰. 大话数据结构 [M]. 清华大学出版社: 北京, 2011:328-341.
[2] (美)Mark Allen Weiss. 数据结构与算法分析: C 语言描述 [M]. 机械工业出版社: 北京, 2017:80-89.
[3] Vamei(张腾飞). 纸上谈兵: AVL 树 [EB/OL].https://www.cnblogs.com/vamei/archive/2013/03/21/2964092.html,2013-3-21.
