一、什么是平衡二叉树
平衡二叉树（Balance Factor Tree，简称 AVL树）是一个特殊的二叉树，它可以是空树。如果不为空，它任一节点左、右子树高度差的绝对值不超过 1，即 |BF(T)| ≤ 1。其中，BF 是指 平衡因子（Balance Factory）：\(BF(T) = h_{L} - h_{R}\)，其中 \(h_{L}\) 和 \(h_{R}\) 分别为 T 的左、右子树的高度。
二叉搜索树节点不同插入次序，将导致不同的深度和平均查找长度 ASL。
给定节点数为 n 的 AVL树 的最大高度为 \(log_{2}N\)
平衡二叉树最大深度为 \(O(log_{2}N)\)，平均查找长度/查找的时间复杂度为 \(O(log_{2}N)\)
二、AVL树的表示
typedef int ElementType;
typedef struct AvlNode *AvlTree;
typedef struct AvlNode *Positon;
struct AvlNode
{
ElementType Element; // AVL树的元素
AvlTree Left; // AVL树的左儿子节点
AvlTree Right; // AVL树的右儿子节点
int Height; // AVL树的高度
};
三、获取AVL树的高度
/**
* @brief 获取指定节点在AVL树中的高度
*
* @param P 待查询的节点
* @return int 返回指定节点在AVL树中的高度
*/
int Height(Positon P)
{
if(P == NULL)
{
return -1;
}
else
{
return P->Height;
}
}
四、平衡二叉树的调整
从插入点往回找到第一个不平衡节点，调整以该节点为根的子树。每次调整的对象都是“最小不平衡子树”。
4.1、平衡二叉树LL旋转
由于在节点 A 的左孩子节点 B 的左子树 \(B_{L}\) 上插入了新节点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。
为了使树平衡，我们把 \(B_{L}\) 和 C 上移一层，并把 A 和 \(A_{R}\) 下移一层。这时，我们需要把 B 作为新的树根。在原二叉树中，B < A，于是在新树中，A 变成了 B 的右儿子，\(B_{L}\) 和 \(A_{R}\) 仍然分别是 B 的左儿子和 A 的右儿子。子树 \(B_{R}\) 包含原树中介于 A 和 B 之间的那些节点，我们可以将它放在新树中 A 左儿子位置上。
/**
* @brief LL左旋
*
* @param K2 原树的树根
* @return Positon 新树的树根
*/
Positon SingleRotateWithLeft(Positon K2)
{
Positon 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;
}
4.2、平衡二叉树RR旋转
由于在节点 A 的右孩子节点 B 的右子树 \(B_{R}\) 上插入了新节点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。
为了使树平衡，我们把 \(B_{R}\) 和 C 上移一层，并把 A 和 \(A_{L}\) 下移一层。这时，我们需要把 B 作为新的树根。在原二叉树中，B > A，于是在新树中，A 变成了 B 的左儿子，\(A_{L}\) 和 \(B_{R}\) 仍然分别是 A 的左儿子和 B 的右儿子。子树 \(B_{L}\) 包含原树中介于 A 和 B 之间的那些节点，我们可以将它放在新树中 A 的右儿子位置上。
/**
* @brief RR旋转
*
* @param K1 原树的树根
* @return Positon 新树的树根
*/
Positon SingleRotateWithRight(Positon K1)
{
Positon K2;
K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;
K1->Height = Max(Height(K1->Left),Height(K1->Right)) + 1;
K2->Height = Max(K1->Height,Height(K2->Right)) + 1;
return K2;
}
4.3、平衡二叉树的LR旋转
为了使树平衡，我们把 C 作为根节点，这迫使 B 成为 C 的左儿子，A 成为 C 的右儿子，\(B_{L}\) 和 \(A_{R}\) 仍然分别是 B 的左儿子和 A 的右儿子。子树 \(C_{L}\) 包含原树中小于 C 但是比 B 大的那些节点。因此，我们可以将它放在新树中 B 右儿子位置上。子树 \(C_{R}\) 包含原树中大于 C 但是比 A 小的那些节点。因此，我们可以将它放在新树中 A 左儿子位置上。
/**
* @brief LR旋转
*
* @param K3 原树的树根
* @return Positon 新树的树根
*/
Positon DoubleRotateWithLeft(Positon K3)
{
K3->Left = SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}
4.4、平衡二叉树的RL旋转
为了使树平衡，我们把 C 作为根节点，这迫使 A 成为 C 的左儿子，B 成为 C 的右儿子，\(A_{L}\) 和 \(B_{R}\) 仍然分别是 A 的左儿子和 B 的右儿子。子树 \(C_{L}\) 包含原树中小于 C 但是比 A 大的那些节点。因此，我们可以将它放在新树中 A 右儿子位置上。子树 \(C_{R}\) 包含原树中大于 C 但是比 B 小的那些节点。因此，我们可以将它放在新树中 B 左儿子位置上。
/**
* @brief RL旋转
*
* @param K1 原树的树根
* @return Positon 新树的树根
*/
Positon DoubleRotateWithRight(Positon K1)
{
K1->Right = SingleRotateWithRight(K1->Right);
return SingleRotateWithRight(K1);
}
五、向AVL树插入节点
/**
* @brief 向AVL树中插入节点
*
* @param X 待插入的元素
* @param T 待操作的AVL树
* @return AvlTree 返回指向AVL树根节点的指针
*/
AvlTree Insert(ElementType X, AvlTree T)
{
if(T == NULL) // 如果树为空，则创建根节点
{
T = (AvlTree)malloc(sizeof(struct AvlNode));
if(T == NULL)
{
printf("创建根节点失败！\n");
}
else
{
T->Element = X;
T->Height = 0;
T->Left = T->Right = NULL;
}
}
else
{
if(X < T->Element) // 如果X比当前节点小，则递归插入当前节点的左子树
{
T->Left = Insert(X, T->Left);
if(Height(T->Left) - Height(T->Right) == 2) // 新插入的节点使AVL树不平衡了
{
if(X < T->Left->Element) // 如果新插入的节点在被破化者的左子树的左子树上
{
T = SingleRotateWithLeft(T); // LL旋转
}
else // 如果新插入的节点在被破化者的左子树的右子树上
{
T = DoubleRotateWithLeft(T); // LR旋转
}
}
}
else if(X > T->Element) // 如果X比当前节点大，则递归插入当前节点的右子树
{
T->Right = Insert(X,T->Right);
if(Height(T->Right) - Height(T->Left) == 2) // 新插入的节点使AVL树不平衡了
{
if(X > T->Right->Element) // 如果新插入的节点在被破化者的右子树的右子树上
{
T = SingleRotateWithRight(T); // RR旋转
}
else // 如果新插入的节点在被破化者的右子树的左子树上
{
T = DoubleRotateWithRight(T); // RL旋转
}
}
}
// 如果相等的话，这里不做处理
}
T->Height = Max(Height(T->Left),Height(T->Right)); // 更新树的高度
return T;
}