AVL四种平衡方法
平衡二叉树（AVL）
一、基本概念简述
平衡二叉树 (Balanced Binary Tree 或Height-Balanced Tree)又称AVL树。
它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。
平衡因子 BF（Balance Factor）：该节点的左子树的深度减去它的右子树的深度。
平衡二叉树上的所有平衡因子只可能是 -1、0和1，即只要一个结点平衡因子的绝对值大于1，则该二叉树不平衡。
关键字（key） ：是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。若此关键字可唯一地标识一个记录，则此关键字为主关键字，反之，用以识别若干记录的关键字称为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。
动态查找表特点：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
二叉排序树 (Binary Sort Tree)：又称二叉查找树(ADL)
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值；
它的左、右子树也分别为二叉排序树。
（AVL树与ADL树都可以是一颗空树）
假设a为由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点）。
单向右旋平衡处理： 由于在 *a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以 *a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。
单向左旋平衡处理： 由于在 *a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以 *a为根的子树失去平衡，则需进行一次向左的逆时针旋转操作。
双向旋转（先左后右）平衡处理： 由于在 *a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以 *a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
双向旋转（先右后左）平衡处理： 由于在 *a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以 *a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。
二、问题及实现
用C语言实现AVL树的四种平衡处理。
要求：用尽可能短的讲解把问题的本质讲得通俗易懂。
四种平衡处理：单向左旋，单向右旋，先左后右双向旋转，先右后左双向旋转。
代码实现：
// AVL树(C语言): C语言实现的AVL树。
#include <stdio.h>
#include <stdlib.h>
#define HEIGHT(p) ((p==NULL)?0:(((Node*)(p))->height)) //预处理宏定义指令
#define MAX(a,b) ((a)>(b)?(a):(b) )
#define TBL_SIZE(a) ( (sizeof(a)) / (sizeof(a[0])) ) //预处理指令，求数组元素个数
typedef int Type;
typedef struct AVLTreeNode{ //定义一个AVL树的结构体
Type key; // 关键字(键值)，用来对AVL树的结点进行排序
int height; //树中的最大层次
struct AVLTreeNode *left; // 左孩子
struct AVLTreeNode *right; // 右孩子
}Node, *AVLTree; //Node为结构的对象，*AVLTree为指向结构的指针
/* 由于指针类型可以在被指向类型不完整定义的情况下定义，
因此可以用在结构体定义的内部定义struct AVLTreeNode *对象 */
int avltree_height(AVLTree tree); // 获取AVL树的高度
void preorder_avltree(AVLTree tree);// 前序遍历"AVL树"
void inorder_avltree(AVLTree tree);// 中序遍历"AVL树"
void postorder_avltree(AVLTree tree);// 后序遍历"AVL树"
void print_avltree (AVLTree tree, Type key, int direction); //打印AVL树
Node* avltree_search(AVLTree x, Type key);// (递归实现)查找"AVL树x"中键值为key的节点
Node* avltree_minimum(AVLTree tree);// 查找最小结点：返回tree为根结点的AVL树的最小结点。
Node* avltree_maximum(AVLTree tree);// 查找最大结点：返回tree为根结点的AVL树的最大结点。
Node* avltree_insert(AVLTree tree, Type key);// 将结点插入到AVL树中，返回根节点
Node* avltree_delete(AVLTree tree, Type key);// 删除结点(key是节点值)，返回根结点
void destroy_avltree(AVLTree tree);// 销毁AVL树
// C 语言: AVL树
static int arr[]= {16,3,7,11,9,26,18,14,15}; //为每个结点赋初值
void main()
{
int i,ilen;
AVLTree root=NULL; //先将AVL树的根结点赋值为空
printf("初始树的高度: %d\n", avltree_height(root));
printf("依次添加: ");
ilen = TBL_SIZE(arr); //计算结点个数
for(i=0; i<ilen; i++) //根据计算的结点个数来插入根结点
{
printf("%d ", arr[i]);
root = avltree_insert(root, arr[i]);
}
printf("\n实现二叉排序树:");
printf("\n前序遍历: ");
preorder_avltree(root);
printf("\n中序遍历: ");
inorder_avltree(root);
printf("\n后序遍历: ");
postorder_avltree(root);
printf("\n");
printf("AVL树的高度: %d\n", avltree_height(root));
printf("最小值: %d\n", avltree_minimum(root)->key);
printf("最大值: %d\n", avltree_maximum(root)->key);
printf("处理完成后AVL树的详细信息: \n");
print_avltree(root, root->key, 0);
i = 9;
printf("\n删除根节点: %d", i);
root = avltree_delete(root, i);
printf("\n删除完成后AVL树的详细信息: \n");
print_avltree(root, root->key, 0);
printf("\n旋转操作的正确性证明：\n树的高度: %d", avltree_height(root));
printf("\n中序遍历: ");
inorder_avltree(root);
destroy_avltree(root); // 销毁二叉树
}
int avltree_height(AVLTree tree) // 获取AVL树的高度
{
return HEIGHT(tree);
}
void preorder_avltree(AVLTree tree) // 前序遍历"AVL树"
{
if(tree != NULL)
{
printf("%d ", tree->key);
preorder_avltree(tree->left);
preorder_avltree(tree->right);
}
}
void inorder_avltree(AVLTree tree) //中序遍历"AVL树"
{
if(tree != NULL)
{
inorder_avltree(tree->left);
printf("%d ", tree->key);
inorder_avltree(tree->right);
}
}
void postorder_avltree(AVLTree tree) // 后序遍历"AVL树"
{
if(tree != NULL)
{
postorder_avltree(tree->left);
postorder_avltree(tree->right);
printf("%d ", tree->key);
}
}
Node* avltree_search(AVLTree x, Type key) //查找"AVL树x"中键值为key的结点(递归实现)
{
if (x==NULL || x->key==key)
return x;
if (key < x->key) //若key小于树的根结点，则在左子树中查找
return avltree_search(x->left, key);
else //若key大于树的根结点，则在右子树中查找
return avltree_search(x->right, key);
}
Node* avltree_minimum(AVLTree tree) //查找最小结点：返回tree为根结点的AVL树的最小结点。
{
if (tree == NULL)
return NULL;
while(tree->left != NULL)
tree = tree->left;
return tree;
}
Node* avltree_maximum(AVLTree tree) //查找最大结点：返回tree为根结点的AVL树的最大结点。
{
if (tree == NULL)
return NULL;
while(tree->right != NULL)
tree = tree->right;
return tree;
}
static Node* left_left_rotation(AVLTree k2) //LL：左左对应的情况(右单旋转)。
{
AVLTree k1; //定义一个指向结构体的变量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 Node* right_right_rotation(AVLTree k1) // RR：右右对应的情况(左单旋转)。
{
AVLTree k2;//定义一个指向结构体的变量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 Node* left_right_rotation(AVLTree k3) // LR：左右对应的情况(左双旋转)。
{
k3->left = right_right_rotation(k3->left); //先将K3的左子树进行RR(左单旋转)
return left_left_rotation(k3); //最后返回再LL(右单旋转)后的根节点
}
static Node* right_left_rotation(AVLTree k1) // RL：右左对应的情况(右双旋转)。
{
k1->right = left_left_rotation(k1->right);//先将K1的左子树进行LL(右单旋转)
return right_right_rotation(k1);//最后返回再RR(左单旋转)后的根节点
}
static Node* avltree_create_node(Type key, Node *left, Node* right) // 创建AVL树结点。
{
Node* p;//定义一个指向结构体的指针变量p
if ((p = (Node *)malloc(sizeof(Node))) == NULL) //若给p分配结构体长度的动态存储区为空
return NULL;
p->key = key; //将函数形参中的key赋值给结构体中的键值变量
p->height = 0; //为结构体中的高度变量赋初值为0
p->left = left; //将函数形参中的left赋值给结构体中的左孩子变量
p->right = right; //将函数形参中的right赋值给结构体中的右孩子变量
return p; //返回这个结构体
}
Node* avltree_insert(AVLTree tree, Type key) //将结点插入到AVL树中，并返回根节点
{
if (tree == NULL) //若初始AVL树的结点为空
{
// 新建结点
tree = avltree_create_node(key, NULL, NULL); //key为插入的结点的键值
if (tree==NULL)
{
printf("错误，创建AVL树结点失败!\n");
return NULL;
}
}
else if (key < tree->key) //若插入的结点值小于树中原本的键值，将key插入到左子树中
{
tree->left = avltree_insert(tree->left, key);//递归调用，将插入的结点放入左子树中
// 插入结点后，若AVL树失去平衡，则进行相应的调节。
if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2) //若BF=2
{
if (key < tree->left->key) //若是在某结点左子树根结点的左子树上插入
tree = left_left_rotation(tree); //则执行LL(单向右旋)
else
tree = left_right_rotation(tree); //否则执行LR(先左后右双向旋转)
}
}
else if (key > tree->key) //若插入的结点值大于树中原本的键值，将key插入到右子树中
{
tree->right = avltree_insert(tree->right, key);//递归调用，将插入的结点放入右子树中
// 插入节点后，若AVL树失去平衡，则进行相应的调节。
if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)//若BF=-2
{
if (key > tree->right->key)//若是在某结点右子树根结点的右子树上插入
tree = right_right_rotation(tree);//则执行RR(单向左旋)
else
tree = right_left_rotation(tree);//否则执行RL(先右后左双向旋转)
}
}
else //若添加的值在树中已经存在
{
printf("添加失败：不允许添加相同的节点！\n");
}
tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
return tree; // 返回这棵树的根节点
}
static Node* delete_node(AVLTree tree, Node *z) //删除结点
{
if (tree==NULL || z==NULL) //根为空或者没有要删除的节点，直接返回NULL。
return NULL;
if (z->key < tree->key) // 待删除的节点在左子树中
{
tree->left = delete_node(tree->left, z);
// 删除结点后，若AVL树失去平衡，则进行相应的调节。
if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)//若BF=-2
{
Node *r = tree->right;//将右子树赋值给待删除的结点r
if (HEIGHT(r->left) > HEIGHT(r->right)) //若此结点(右子树的)左子树的高度大于右子树
tree = right_left_rotation(tree); //进行RL处理(先右后左双向旋转)
else //左子树高度小于右子树
tree = right_right_rotation(tree);//进行RR处理(左向单旋)
}
}
else if (z->key > tree->key)// 待删除的结点在右子树中
{
tree->right = delete_node(tree->right, z);
// 删除结点后，若AVL树失去平衡，则进行相应的调节。
if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
{
Node *l = tree->left;
if (HEIGHT(l->right) > HEIGHT(l->left))
tree = left_right_rotation(tree);
else
tree = left_left_rotation(tree);
}
}
else // tree是对应要删除的结点。
{
if ((tree->left) && (tree->right))// tree的左右孩子都非空
{
if (HEIGHT(tree->left) > HEIGHT(tree->right))
{
Node *max = avltree_maximum(tree->left);//在左子树中查找最大值赋值给max
tree->key = max->key;
tree->left = delete_node(tree->left, max);
//删除左子树中的max结点并返回树的根结点
}
else //若左子树的高度小于右子树
{
Node *min = avltree_maximum(tree->right);//在右子树中找最大值赋值给min
tree->key = min->key;
tree->right = delete_node(tree->right, min);
//删除右子树中的min结点并返回树的根结点
}
}
else //若左右孩子中含有空子树
{
Node *tmp = tree; //将结点值tree赋值给结构体指针变量tmp
tree = tree->left ? tree->left : tree->right;
free(tmp);
}
}
return tree;
}
Node* avltree_delete(AVLTree tree, Type key)//将结点从AVL树中删除，并返回根节点
{
Node *z;
if ((z = avltree_search(tree, key)) != NULL)
tree = delete_node(tree, z);
return tree;
}
void destroy_avltree(AVLTree tree) //递归销毁AVL树
{
if (tree==NULL)
return ;
if (tree->left != NULL)
destroy_avltree(tree->left);
if (tree->right != NULL)
destroy_avltree(tree->right);
free(tree);
}
void print_avltree(AVLTree tree, Type key, int direction) //tree是AVL树的结点；key是结点的键值；
{
if(tree != NULL)
{
if(direction==0) // tree是根结点
printf("%2d is root\n", tree->key, key);
else // tree是分支结点
printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");
print_avltree(tree->left, tree->key, -1);
print_avltree(tree->right,tree->key, 1);
}
}
/*
* direction 为0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。
*/
运行结果:
三、相关知识点补充：
1.求数组元素的个数
int c1=sizeof(a1)/sizeof(char);//总长度/单个元素的长度 char型
int c2=sizeof(a2)/sizeof(a2[0]);//总长度/第一个元素的长度 int型
写到这里，可以考虑一下，下面的c3，c4值应该是多少
void foo3(char a3[3])
{
int c3=sizeof(a3);//c3==?
}
void foo4(char a4[])
{
int c4=sizeof(a4);//c4==?
}
是的，c3不等于3。这里函数参数a3已不再是数组类型，而是蜕变成指针，相当于char* a3，仔细想想就不难明白，我们调用函数foo3时，程序不会在栈上分配一个大小为3的数组！数组是“传址”的，调用者只需将实参的地址传递过去，所以a3自然为指针类型（char*），c3的值也就为4。
2.->称为指向运算符
如果p指向一个结构体变量stu，则以下三种用法等价：
- stu.成员名（如stu.num）;
- (*p).成员名（如(*p).num);
- p->成员名（如p->num）。
3.内存的动态分配
全局变量是分配在内存的静态存储区的，非静态的局部变量（包括形参）是分配在内存的动态存储区的，这个存储区是一个称为栈（stack）的区域。
C语言还允许建立内存动态分配区域，以存放一些临时用的数据，这些数据不必在程序的声明部分定义，也不必等到函数结束时才释放，而是需要随时开辟，不需要随时释放。这些数据是临时存放在一个特别的自由存储区，称为堆（heap）区，可根据需要向系统申请所需大小的空间。因未在声明部分定义它们为变量或数组，所以不能通过变量名或者数组名去引用这些数据，只能通过指针来引用。
通过系统提供的库函数来实现对内存的动态分配：
(1).malloc函数
函数原型：
void *malloc(unsigned int size);
//在内存的动态存储区分配一个长度为size的连续空间。
(2).calloc函数
函数原型：
void *calloc(unsigned n,unsigned size);
//在内存的动态存储区分配n个长度为size的连续空间。
(3).free函数
函数原型：
void free(void *p);
//释放指针变量p所指向的动态空间。
(4).realloc函数
函数原型：
void *realloc(void *p,unsigned int size);
//将p所指向的动态空间大小改变为size，p值不变。
若已经通过malloc函数或者calloc函数获得了动态空间，想改变其大小，可使用realloc函数进行重新分配。这四个函数的声明均在stdlib.h头文件中。
4.另辟蹊径： 根据平衡二叉树的性质可知平衡二叉树的四种旋转处理主要为解决由于插入和删除结点造成的（高度差）平衡因子为2或者-2的问题。只要为以平衡因子为2或者-2为根结点的子二叉排序树重新找一个根结点并建立新的子二叉排序树，从而使得二叉排序树中的平衡因子都为1、0和-1即可。所以问题的关键就在于如何找到重新建立的子二叉排序树的根结点，即序列中的第一个结点。
除了以上四种旋转平衡处理外，这里还有另一种理解AVL树平衡处理的方法，在这里引入三条规则：
规则一： 某结点的平衡因子为2时，把以该结点为根的树采用中序遍历的方法遍历后可得到一个递增的子序列，同时看该结点左孩子的平衡因子。
若左孩子的BF=1，（即插入导致失衡的是该结点左孩子的左孩子）则取该左孩子结点，将其移动到子序列的最前面，得到一个新的序列，对该序列构建二叉排序树；
若左孩子的BF=-1，（即插入导致失衡的是该结点左孩子的右孩子）则取该左孩子的右孩子结点，将其移动到子序列的最前面，得到一个新的序列，对该序列构建二叉排序树；
规则二： 某结点的平衡因子为-2时，把以该结点为根的树采用中序遍历的方法遍历后可得到一个递增的子序列，同时看该结点右孩子的平衡因子。
若右孩子的BF=1，（即插入导致失衡的是该结点右孩子的左孩子）则取该右孩子的左孩子结点，将其移动到子序列的最前面，得到一个新的序列，对该序列构建二叉排序树；
若右孩子的BF=-1，（即插入导致失衡的是该结点左孩子的右孩子）则取该右孩子结点，将其移动到子序列的最前面，得到一个新的序列，对该序列构建二叉排序树；
规则三： （用于删除结点）
(1)若删除的是叶子结点，直接删除，且自底向下查看树中的平衡因子。若发现存在平衡因子为2时，采用规则一进行调整，若平衡因子为-2，则采用规则二进行调整；
(2)若非叶子结点，首先用该结点左子树的最大值（或右子树的最小值）代替该结点，然后在二叉排序树中删掉最大值（或最小值）。同样，自底向下查看树中的平衡因子，若存在平衡因子为2，采用规则一进行调整，若平衡因子为-2，则采用规则二进行调整。（这里的首先采用的是二叉排序树非叶子结点的删除方法）
5.递归与迭代的区别
递归从始至终贯穿这个程序，在这里便给出递归与迭代的区别：
1.递归:程序调用自身的编程技巧称为递归,是函数自己调用自己。一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量。递归的能力在于用有限的语句来定义对象的无限集合。
2.迭代:利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话,迭代就是A不停的调用B。
3.递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换，能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出。
4.简单地说，递归是重复调用函数自身实现循环；迭代是函数内某段代码实现循环。而迭代与普通循环的区别是：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。
5.递归循环中，遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。当然很多情况都是多种循环混合采用，这要根据具体需求。
四.讲述与答辩
根据平衡二叉树的性质可知平衡二叉树的四种旋转处理主要为解决由于插入和删除结点造成排序二叉树的（高度差）平衡因子的绝对值大于1的问题。而解决这个问题的关键首先就在于如何找到由于插入新结点而导致失衡的最小子树根结点的指针，其次可根据四种旋转变换调整结点之间的链接关系从而使失衡的最小子树恢复平衡。
单项左旋解决的是由于某结点右子树根结点的右子树上插入新的结点从而导致子树失衡的问题；
单项右旋解决的是由于某结点左子树根结点的左子树上插入新的结点从而导致子树失衡的问题；
先左后右双向旋转解决的是由于某结点左子树的右子树上插入新的结点从而导致子树失衡的问题；
先右后左双向旋转解决的是由于某结点右子树的左子树上插入新的结点从而导致子树失衡的问题。
在这里我只给出了平衡旋转处理完成之后的AVL树，关于平衡二叉树四种动态旋转的具体过程，想要彻底搞清楚的话建议书面过几遍或者给别人讲解一遍(毕竟...我就是这样做的...)。如果感兴趣的话还可以在这个网站里自己动手操作一遍，动态的旋转方式更易于理解四种旋转的本质。
下面给出链接：
数据结构和算法动态可视化
……又是一次赶鸭子上架的过程
确实，大部分学生还是需要被鞭策的
现在的主动也只是为了在以后拥有选择的权利
Emmm终于可以开始玩别的啦~