平衡二叉树
为了避免树的高（深）度增长过快，降低二叉排序树的性能，规定在插入和删除节点时，要保证任意节点的左、右子树高度差的绝对值不超过 1，称这样的二叉排序树为平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称 AVL 树。
AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
按发明者来命名的情况很常见，典型的还有 KMP、RSA 等。
节点定义左、右子树的高度差为该节点的平衡因子 BF(Balanced Factor)，则平衡二叉树所有节点的平衡因子只可能为 -1、0、1。只要有一个节点的平衡因子的绝对值大于 1，该二叉排序树就是不平衡的。
由此，平衡二叉树可定义为或是一棵空树，或是具有如下特征：其左、右子树均为平衡二叉树，并且左、右子树高度差的绝对值不超过 1。
平衡二叉树是二叉排序树平衡化的结果，它仍属于二叉排序树，二叉排序树的各种性质和操作同样适用于平衡二叉树。
由于要存储节点的平衡因子，所以平衡二叉树的树节点定义相较于一般排序树需增加 bf 变量。
// 平衡二叉树 AVL
typedef struct BBSTNode
{
TElemType data;
struct BBSTNode *lchild, *rchild;
int bf; //平衡因子
} BBSTNode, *BBSTree;平衡二叉树的插入
再平衡基本思想
相比于二叉排序树的插入，平衡二叉树在插入新节点时，需要确保二叉树的平衡。
二叉排序树保证平衡的基本思想如下：
(1) 首先检查插入路径上的节点是否因为此次插入导致不平衡（检查平衡因子）；
(2) 如果导致了不平衡，则先找到 插入路径上离插入节点最近的的平衡因子的绝对值大于 1 的节点 p；
(3) 然后对以 p 为根的子树，在保证二叉排序树特性的前提下，调整相关节点的位置关系，使其重新达到平衡。
注意：
每次失衡后调整的对象都是最小不平衡子树，即 以插入路径上离插入节点最近的的平衡因子的绝对值大于 1 的节点 p 为根 的子树
再平衡调整规则
具体地，失去平衡后进行调整的规律有如下四种：
(1) LL 平衡旋转（单向右旋） 在节点 p 的左孩子(L)的左子树(L)上插入新节点，使 p 的平衡因子由 1 增为 2（左高），导致以 p 为根的子树失去平衡。
此时需一次右旋，将 p 的左孩子 s 向右上旋转代替 p 作为该子树的根，p 向右下旋转成为 s 的右孩子，原来 s 的右子树作为 p 的左子树；
单向右旋后，S(旋转后的根) 和 P(旋转后的根的右孩子) 的平衡因子均变为 0，树的高度不变
(2) RR 平衡旋转（单向左旋） 在节点 p 的右孩子(R)的右子树(R)上插入新节点，使 p 的平衡因子由 -1 减为 -2（右高），导致以 p 为根的子树失去平衡。
此时需一次左旋，将 p 的右孩子 s 向左上旋转代替 p 作为该子树的根，p 向左下旋转成为 s 的左孩子，原来 s 的左子树作为 p 的右子树；
单向左旋后，S(旋转后的根) 和 P(旋转后的根的左孩子) 的平衡因子均变为 0，树的高度不变
(3) LR 平衡旋转（双向旋转，先左后右） 在节点 p 的左孩子(L)的右子树(R)上插入新节点，使 p 的平衡因子由 1 增为 2（左高），导致以 p 为根的子树失去平衡。
此时需两次旋转，先左旋 p 的左子树，将 p 的左孩子 s 的右子树的根 c 向左上旋转代替 s；再右旋以 p 根的子树，将左旋后的 c 向右上旋转代替 p 作为该子树的根；
此种情形导致失衡的因素是 p 左孩子 s 的右子树，如果单纯的右旋，s 的右子树会变成 p 的左子树，它仍然是影响平衡的因素，子树的平衡因子由 2 变成 -2（右高），依旧不平衡。
图中深色块之一为新插入导致失衡的节点，可以看到 C 上的插入位置会影响旋转后树的形态，也就是会影响相关节点的平衡因子的变化。
(4) RL 平衡旋转（双向旋转，先右后左） 在节点 p 的右孩子(R)的左子树(L)上插入新节点，使 p 的平衡因子由 -1 减为 -2（右高），导致以 p 为根的子树失去平衡。
此时需两次旋转，先右旋 p 的右子树，将 p 的右孩子 s 的左子树的根 c 向右上旋转代替 s；再左旋以 p 根的子树，将右旋后的 c 向左上旋转代替 p 作为该子树的根；
此种情形导致失衡的因素是 p 右孩子 s 的左子树，如果单纯的左旋，s 的左子树会变成 p 的右子树，它仍然是影响平衡的因素，子树的平衡因子由 -2 变成 2（左高），依旧不平衡。
图中深色块之一为新插入导致失衡的节点，与 LR 相对称，在 RL 中 C 上的插入位置也会影响旋转后树的形态，也就是会影响相关节点的平衡因子的变化。
上述四种情形，(1) 和 (2) 对称，(3) 和 (4) 对称，另外，容易发现无论哪种再平衡情形，进行旋转调整后，新的子树的深度和原来一致。
因此，当平衡二叉树因为新插入节点而失去平衡时，仅需要对最小不平衡子树 进行平衡旋转处理即可，印证了之前的再平衡的基本思想。
因为经过旋转处理后的子树深度和插入节点之前相同，因此不影响插入路径上所有祖先节点的平衡度。
平衡树插入算法描述
平衡二叉排序树 BBST 上新插入一个节点 e 的递归算法描述：
(Ⅰ) BBST 为空树，则新节点 e 作为 BBST 的根节点，树的深度增 1；
(Ⅱ) 新节点 e 的关键字和 BBST 根节点关键字相同，则不插入，树深度不变
(Ⅲ) 新节点 e 的关键字小于 BBST 根节点关键字，而且 BBST 左子树中不存在和 e 相同关键字的节点，则将新节点 e 插在 BBST 左子树上，并且当插入后左子树深度增加 (+1)时，有如下三种情形：
(1) BBST 根节点的平衡因子为 -1（右高）：则将根节点平衡因子改为 0，BBST 的深度不变；
(2) BBST 根节点的平衡因子为 0（等高）：则将根节点平衡因子改为 1，BBST 的深度增加 1；
(3) BBST 根节点的平衡因子为 1（左高）：
若 BBST 左子树的平衡因子为 1 (LL)，则需要单向右旋处理，并将（新）根节点（原 s）及其右子树（原 p）的平衡因子更新为 0，树的深度不变；
若 BBST 左子树的平衡因子为 -1 (LR)，则需要先左旋后右旋处理，并将（新）根节点（原 c）的平衡因子更新为 0，而其左、右子树（原s、p）的平衡因子要根据左孩子的右子树（原 c）的平衡因子判断，树的深度不变；
(Ⅳ) 新节点 e 的关键字大于 BBST 根节点关键字，而且 BBST 右子树中不存在和 e 相同关键字的节点，则将新节点 e 插在 BBST 右子树上，并且当插入后右子树深度增加 (+1)时，有如下三种情形：
(1) BBST 根节点的平衡因子为 1（左高）：则将根节点平衡因子改为 0，BBST 的深度不变；
(2) BBST 根节点的平衡因子为 0（等高）：则将根节点平衡因子改为 -1，BBST 的深度增加 1；
(3) BBST 根节点的平衡因子为 -1（右高）：
若 BBST 右子树的平衡因子为 -1 (RR)，则需要单向左旋处理，并将（新）根节点（原 s）及其左子树（原 p）的平衡因子更新为 0，树的深度不变；
若 BBST 右子树的平衡因子为 1 (RL)，则需要先右旋后左旋处理，并将（新）根节点（原 c）的平衡因子更新为 0，而其左、右子树（原p、s）的平衡因子要根据右孩子的左子树（原 c）的平衡因子判断，树的深度不变；
注意：
平衡二叉树是递归结构，并且我们每次只对最小不平衡子树进行调整，所以在更新子树根节点的平衡因子时，只需要更新参与旋转的子树根（节点关键字和指针发生变化）的平衡因子即可，其余部分在旋转时都作为整体处理，平衡因子不受影响。
平衡插入算法实现
再平衡的基本操作是子树旋转，于是提取出原子操作左旋和右旋。
// 以 *p 为根的子树左旋
void L_Rotate(BBSTree *p)
{
BBSTNode *s = (*p)->rchild;
(*p)->rchild = s->lchild;
s->lchild = (*p);
(*p) = s;
}
// 以 *p 为根的子树右旋
void R_Rotate(BBSTree *p)
{
BBSTNode *s = (*p)->lchild;
(*p)->lchild = s->rchild;
s->rchild = (*p);
(*p) = s;
}左平衡 LeftBalance，对应算法描述 (Ⅲ)(3) 的情形，解决左子树插入导致失衡的问题，右平衡 RightBalance 刚好与左平衡对称。
void LeftBalance(BBSTree *p)
{
BBSTNode *s = (*p)->lchild;
switch(s->bf)
{
case 1: // LL
(*p)->bf = 0;
s->bf = 0;
R_Rotate(p);
break;
case -1: // LR
BBSTNode *t = s->rchild;
switch(t->bf)
{
case 1: // 插在 C 的左子树上
(*p)->bf = -1;
s->bf = 0;
break;
case 0:
(*p)->bf = 0;
s->bf = 0;
break;
case -1: // 插在 C 的右子树上
(*p)->bf = 0;
s->bf = 1;
break;
}
L_Rotate(&s);
R_Rotata(p);
break;
}
}于是，平衡二叉树在插入实现即如下：
// 插入
// taller 变量用于标识以 *T 为根的子树是否长高
Status InsertAVL(BBSTree *T, TElemType key, int *taller)
{
if ((*T) == NULL)
{
(*T) = (BBSTNode *)malloc(sizeof(BBSTNode));
(*T)->data = key;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->bf = 0; // 只有根
(*taller) = 1;
return 0;
}
else
{
if (key == (*T)->data)
{
(*taller) = 0; // 已存在不需要插入
return -1;
}
else if (key < (*T)->data)
{
if (InsertAVL(&((*T)->lchild), key, taller) == -1)
return -1; // 已存在没插入
if (*taller) // 插入新元素后，检查树是否长高，以便于计算bf，进而进行平衡调整
{
switch ((*T)->bf)
{
case 1: // 原本是左高，现在左边又插入新节点，不再平衡,需要调整
LeftBalance(T); // 左平衡
(*taller) = 0;
break;
case 0: // 原本是同高，现在左边又插入新节点，因此变成左高
(*T)->bf = 1;
(*taller) = 1;
break;
case -1: // 原本是右高，现在左边又插入新节点，因此变成同高
(*T)->bf = 0;
(*taller) = 0;
break;
}
}
}
else
{
if (InsertAVL(&((*T)->rchild), key, taller) == -1)
return -1; // 已存在没插入
if (*taller) // 检查树是否长高，以便于计算bf，进而进行平衡调整
{
// 与左插情形相反
switch ((*T)->bf)
{
case 1: // 原本是左高，现在右边又插入新节点，因此变成同高
(*T)->bf = 0;
(*taller) = 0;
break;
case 0:
(*T)->bf = -1;
(*taller) = 1; // 长高
break;
case -1:
RightBalance(T); // 右平衡
(*taller) = 0;
break;
}
}
}
return 0;
}
}平衡二叉树的删除
平衡二叉树的删除和二叉查找树的删除操作情况一致，也分为三种情况：
(1) 被删节点是叶子节点；
(2) 被删节点只有左或右子树；
(3) 被删节点既有左子树又有右子树；
当然，和插入一样，平衡二叉树在删除节点后也需要平衡检验和再平衡。对于删除操作进行的再平衡可以理解为：对左或右子树的删除操作相当于对右或左子树的插入，然后根据插入时的各种情况进行相应的旋转即可。
平衡二叉树的查找分析
平衡二叉树的旋转再平衡的可行性在于它的实质仍然是排序树中使用中序前驱或后继代替自己，以确保二叉排序树的根本性质。
平衡二叉树旋转之后，新的根节点的平衡因子一定是 0，因为正常平衡树失衡时左右高度差一定是 2，因此旋转之后一增一减刚好消除。
平衡二叉树上的查找过程和排序树一样，因此在查找工程中和给定值进行的关键字比较的个数不超过树的高度。
假设以 \(n_h\) 表示给定高度为 \(h\) 的平衡树中含有的最少节点数。显然有
$$
n_0 = 0\\
n_1 = 1\\
n_2 = 2\\
n_h = n_h-1 + n_h-2 + 1\\
$$
此时，平衡树中所有非叶子节点的平衡因子均为 1 或 -1。
反之，通过该结论也可以求解，给定节点数的平衡树的查找所需要进行的最大比较次数或者平衡树的最大高度。
将该递推公式再往前推两步：
$$
n_3 = 4\\
n_4 = 7\\
n_5 = 12\\
$$
于是，可以得到，含有 12 个节点的平衡树查找某节点所需要进行的关键字最大比较次数为 5；
或者说，高度为 5 的平衡树最少含有 12 个节点。
可以证明含有 n 个节点的平衡二叉树的最大深度为 \(0(log_2 n)\)。
扩展
折半查找的判定树是一棵平衡二叉树。
根据折半查找定义，每次把一个数组从中间分割时，总是把数组分割为节点数相差不超过 1 的两个数组，从而使得到的判定树的两棵子树的高度差的绝对值不超过 1，因此它是一棵平衡二叉树。