1. 背景
因为二叉排序树在平衡的情况下查询效率最佳，AVL树让二叉排序树节点变动后维持平衡（左子树高度-右子树高度 差的绝对值<2）
2. 算法原理
根据节点的平衡因子及插入结果，实际修正二叉树，把不平衡消灭最初时刻
2.1 关于旋转
左旋：子树以右孩子为轴心，整体左旋转，旋转后的状态：原根的右孩子成为新根，原根成为新根的左孩子，新根的原左孩子成为其新左孩子的右孩子（中序遍历顺序未变）
右旋：子树以左孩子为轴心，整体右旋转，旋转后的状态：原根的左孩子成为新根，原根成为新根的右孩子，新根的原右孩子成为其新右孩子的左孩子（中序遍历顺序未变）
2.2 出现不平衡时，调整的原则是
根节点和它孩子必须符号相同（即都是左高或右高，根节点和它的左或右孩子的bf要么都是正数，要么都是负数）。符号一致直接旋转，不一致则需两次操作（即双旋）
(注：出现双旋转时，左孩子或右孩子所在子树需要先旋转，并不会遵守符号相同原则，这一步可以称作符号适配)
2.3 造成不平衡的情况分类及调整方案(4类)
LL（左子树高，左孩子的左子树高）
调整方案：直接右旋转 + bf修正
LR（左子树高，左孩子的右子树高）
调整方案：右孩子子树左旋 => 右旋转 + bf修正
RR（右子树高，右孩子的右子树高）
调整方案：直接左旋转 + bf修正
RL（右子树高，右孩子的左子树高）
调整方案：左孩子子树右旋转 => 左旋转 + bf修正
2.2 其它
==下面只整理了插入操作相关原理==
二叉树中的节点有一个平衡因子（bf，值为常量-1，0，1）分别标识本节点为根的子树当前是右高，等高，左高
插入操作附带更新tag（ taller）来判断某节点是否长高
插入函数的递归调用回溯时，会根据所在节点的bf值决定是否调整二叉树（旋转）及更新bf值
（注：一些细节见代码注释）
3. 代码实现
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 平衡因子(bf)的值
#define LH 1
#define EH 0
#define RH -1
typedef struct BiTNode {
int data;
int bf;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void L_Rotate(BiTree *);
void R_Rotate(BiTree *);
bool InsertAVL(BiTree *, int, bool *);
void LeftBalance(BiTree *);
void RightBalance(BiTree *);
void traverse_mid(BiTree);
// 左旋转
void L_Rotate(BiTree *P)
{
BiTree R;
R = (*P)->rchild;
(*P)->rchild = R->lchild;
R->lchild = *P;
*P = R;
}
// 右旋转
void R_Rotate(BiTree *P)
{
BiTree L;
L = (*P)->lchild;
(*P)->lchild = L->rchild;
L->rchild = *P;
*P = L;
}
// 左调整
void LeftBalance(BiTree *P)
{
// 执行到此函数说明本子树的bf已经变为2（并没有显示赋值2，且左孩子树高
// 左孩子不可能为EH，只可能是LH或RH，因为如果是EH，则上一次EH时就已经是不平衡的了
BiTree L, Lr;
L = (*P)->lchild;
switch (L->bf)
{
// 匹配手绘图中的LL，右旋处理
case LH:
(*P)->bf = L->bf = EH;
R_Rotate(P);
break;
// 匹配手绘图中的LR，双旋处理
case RH:
Lr = L->rchild;
// 根据Lr的bf修改平衡因子(下面这些bf修改建议亲自手绘下面3种情况来理解, 不需要硬记)
// 先修改bf，不影响旋转
switch (Lr->bf)
{
// 匹配LRB
case LH:
(*P)->bf = RH;
L->bf = EH;
break;
// 匹配LRA
case EH:
(*P)->bf = L->bf = EH;
break;
// 匹配LRC
case RH:
(*P)->bf = EH;
L->bf = LH;
break;
}
Lr->bf = EH;
L_Rotate(&(*P)->lchild);
R_Rotate(P);
}
}
// 右调整
void RightBalance(BiTree *P)
{
BiTree R, Rl;
R = (*P)->rchild;
switch (R->bf)
{
case RH:
(*P)->bf = R->bf = EH;
L_Rotate(P);
break;
case LH:
Rl = R->lchild;
switch (Rl->bf)
{
// 匹配RLB
case LH:
(*P)->bf = EH;
R->bf = RH;
break;
// 匹配RLA
case EH:
(*P)->bf = R->bf = EH;
break;
// 匹配RLC
case RH:
(*P)->bf = LH;
R->bf = EH;
break;
}
Rl->bf = EH;
R_Rotate(&(*P)->rchild);
L_Rotate(P);
}
}
// 插入函数
bool InsertAVL(BiTree *P, int e, bool *taller)
{
if (!*P) {
printf("insert %d\n", e);
*P = (BiTree)malloc(sizeof(BiTNode));
(*P)->bf = EH;
(*P)->data = e;
(*P)->lchild = (*P)->rchild = NULL;
*taller = true;
}
else {
if (e == (*P)->data) {
*taller = false;
return false;
}
if (e < (*P)->data) {
// 插入失败肯定是上面这种找到了匹配的节点
if (! InsertAVL(&(*P)->lchild, e, taller)) {
return false;
}
if (*taller) { // 大画数据结构中的这个表达式有一处刊误
switch ((*P)->bf)
{
// 左子树插入成功
case LH:
printf("At %d bf now %d after insert %d LeftBalance\n", (*P)->data, (*P)->bf, e);
LeftBalance(P); // 原来左高，现左长高，则不平衡，调整
*taller = false; // 未长高（不平衡已经消除）
break;
case EH:
(*P)->bf = LH; // 原来平衡，现左长高，则左高
*taller = true; // 长高
break;
case RH:
(*P)->bf = EH; // 原来右高，现左长高，则平衡
*taller = false; // 未长高
break;
}
}
}
else {
if (! InsertAVL(&(*P)->rchild, e, taller)) {
return false;
}
if (*taller) {
// 右子树插入成功
switch ((*P)->bf)
{
case LH:
(*P)->bf = EH; // 原来左高，现右长高，则平衡
*taller = false; // 未长高
break;
case EH:
(*P)->bf = RH; // 原来平衡，现右长高，则右高
*taller = true; // 长高
break;
case RH:
printf("At %d bf now %d after insert %d RightBalance\n", (*P)->data, (*P)->bf, e);
RightBalance(P); // 原来右高，现右长高，则调整
*taller = false; // 未长高(不平衡已经消除)
break;
}
}
}
}
return true;
}
void traverse_mid(BiTree T)
{
if (!T)
return;
traverse_mid(T->lchild);
printf("%d[%d] ", T->data, T->bf);
traverse_mid(T->rchild);
}
int main(void)
{
// 标识树是否长高
bool taller;
int i;
int a[10] = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
BiTree T = NULL;
for (i=0; i<10; i++) {
InsertAVL(&T, a[i], &taller);
traverse_mid(T); putchar('\n');
}
printf("finally正序遍历:\n");
traverse_mid(T); putchar('\n');
return 0;
}
output
[root@8be225462e66 c]# gcc avl.c && ./a.out
insert 3
3[0]
insert 2
2[0] 3[1]
insert 1
At 3 bf now 1 after insert 1 LeftBalance
1[0] 2[0] 3[0]
insert 4
1[0] 2[-1] 3[-1] 4[0]
insert 5
At 3 bf now -1 after insert 5 RightBalance
1[0] 2[-1] 3[0] 4[0] 5[0]
insert 6
At 2 bf now -1 after insert 6 RightBalance
1[0] 2[0] 3[0] 4[0] 5[-1] 6[0]
insert 7
At 5 bf now -1 after insert 7 RightBalance
1[0] 2[0] 3[0] 4[0] 5[0] 6[0] 7[0]
insert 10
1[0] 2[0] 3[0] 4[-1] 5[0] 6[-1] 7[-1] 10[0]
insert 9
At 7 bf now -1 after insert 9 RightBalance
1[0] 2[0] 3[0] 4[-1] 5[0] 6[-1] 7[0] 9[0] 10[0]
insert 8
At 6 bf now -1 after insert 8 RightBalance
1[0] 2[0] 3[0] 4[-1] 5[0] 6[1] 7[0] 8[0] 9[0] 10[0]
finally正序遍历:
1[0] 2[0] 3[0] 4[-1] 5[0] 6[1] 7[0] 8[0] 9[0] 10[0]
[root@8be225462e66 c]#