AVL树
平衡二叉查找树（Self-balancing binary search tree）通常是指一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且任意节点的左右两个子树都是一棵平衡二叉树（即严格的平衡二叉查找树，“严格”二字体现在任意节点的左右子树高度差不超过1），平衡二叉树有多种实现方法（红黑树、AVL、替罪羊树、Treap、伸展树等）本篇随笔分析的AVL树（AVL树是根据它的发明者G. M. Adelson-Velskii和E. //代码效果参考：http://www.zidongmutanji.com/zsjx/447097.html
M. Landis命名的），是在二叉查找树的基础上一个优化版本（AVL树是严格的二叉查找树，而红黑树不是，红黑树是非严格的二叉查找树，红黑树有自己的一套规则来保证整棵树接近平衡）AVL树的特点：
1.本身首先是一棵二叉查找树
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值不超过1，也就是说，AVL树，本质上是带了平衡功能的二叉查找树
如果读者关于二叉查找树还不了解可以看一下这篇随笔：二叉查找树（查找、插入、删除）
AVL树的作用
AVL树解决了二叉查找树可能出现的极端情况，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定，但是在某些极端情况下
（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，例如在在删除时，
我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，使得它的操作时间复杂度增加
例如下面这种情况：
AVL树的特性让二叉搜索树的节点实现平衡(balance)：节点相对均匀分布，而不是偏向某一侧
AVL树节点的定义：
1 typedef struct AVLTreeNode
2 {
3 int data;
4 int height; //节点的高度
5 struct BSTreeNode left;//左子树
6 struct BSTreeNode right;//右子树
7
8 }AVLTree;
与一般的二叉查找树的节点相比多了一个参数，节点的高度（网上有些博客是把平衡因子加在了节点的定义里面，笔者不太建议这样做）
预备知识
为了读者能更好了理解AVL树的操作，在继续往下看之前需要搞清楚几个概念
高度、深度和平衡因子
（1）深度——从上往下数
节点的层次（节点的深度）：从根开始定义，根为第1层，根的子节点为第2层，以此类推；（这里说根节点为第1层，其他博客可能把根节点定义成第0层，两种记法都没有错，都可以用来描述树的性质，只需要标注（>0）或者(>=0)做一个区分和解释即可），本篇随笔记根节点为第1层（也可以说成根节点的深度为1）
树的深度：树中节点的最大层次
（树的深度 = 叶子节点的深度）
（2）高度——从下往上数
关于高度，有的文章中将"空二叉树的高度定义为-1"，本篇随笔采用维基百科上的定义：空二叉树的高度为0，因为高度是从下往上数，所以叶子节点的高度为1
（树的高度 = 根节点的高度）
（3）平衡因子
某结点的左子树与右子树的高度或深度(高度深度都可以，本篇随笔使用深度来计算平衡因子)差即为该结点的平衡因子（BF,Balance Factor），平衡二叉树（AVL树）上所有结点的平衡因子只可能是 -1，0 或 1
从上面的节点的定义可以看出，节点中存储的是节点的高度，而不是平衡因子
下图中就标注了所有节点的平衡因子
（平衡因子计算时左子树 - 右子树 和 右子树 - 左子树 都可以，因为判断树是否平衡的条件是：每个结点的左右子树的高度之差的绝对值不超过1，只不过判断失衡以后还要判断是哪一种失衡，这就需要根据情况来选择是左-右还是右-左了）
-
1、查找节点
在 AVL树 中查找与在 二叉查找树 中查找完全一样，因为AVL树总是保持平衡的，树的结构不会由于查询而改变，这里就不再赘述了
实现代码：
1 / 查找特定值 /
2 void SearchData(int targ, BSTree nod)
3 {
4 if (nod != NULL)
5 {
6 if (nod->data == targ)
7 {
8 printf("查找值存在，值为%d\n", nod->data);
9 }
10 else if (nod->data > targ)
11 {
12 SearchData(targ, nod->left); //递归查找左子树
13 }
14 else if (nod->data [span style="color: rgba(0, 0, 0, 1)"> targ)
15 {
16 SearchData(targ, nod->right); //递归查找右子树
17 }
18 }
19 else if (nod == NULL)
20 {
21 printf("查找值不存在\n");
22 }
23 }
View Code
2、插入节点（递归实现）
先梳理一下步骤
先来实现搜索最低失衡节点，搜索最低失衡节点是从新插入的节点（也就是叶子节点）往上搜索（也可以说成从新增结点开始向根部回溯），搜索到的第一个平衡因子>1（|左子树高度-右子树高度|>1）的节点，作为最低失衡节点，因为是从新插入的节点往上搜索，二叉树的搜索是单向的（结构体成员中只有左右子树），单独使用一个函数来实现逆向搜索实现起来并不方便，这里就把搜索最低失衡节点的操作放到递归实现的插入操作中
这里没有像上一篇随笔：二叉查找树（查找、插入、删除）——C语言那样先手动输入的一个二叉平衡树（因为这里要考虑节点的高度，输入不太方便），干脆就从空二叉树开始插入
实现代码：
/ 获取节点高度，空树的高度为0 /
int GetNodeHeight(AVLTree nod)
{
if (nod != NULL) //若不为空子树
{
if (nod->left == NULL nod->right == NULL) //若为叶子节点
{
return 1;
}
else if (GetNodeHeight(nod->right) > GetNodeHeight(nod->left)) //若右子树高度较高
{
return (nod->right)->height + 1;
}
else //若左子树高度较高
{
return (nod->left)->height + 1;
}
}
else //若为空子树
{
return 0;
}
}
/ 添加新节点（包含搜索最低失衡节点和调整树操作） /
AVLTree AddNewNode(AVLTree nod, int NewData)
{
AVLTree p = NULL;
if (nod == NULL)
{
if ((nod = (AVLTree )malloc(sizeof(AVLTree))) == NULL) //创建新节点
{
printf("内存不足");
exit(0);
}
nod->data = NewData;
nod->left = NULL;
nod->right = NULL;
nod->height = GetNodeHeight(nod);
}
else if (NewData > nod->data)
{
nod->right = AddNewNode(nod->right, NewData);
nod->height = GetNodeHeight(nod);
if (GetNodeHeight(nod->right) - GetNodeHeight(nod->left) > 1) //右子树高度 - 左子树高度
{
}
return nod;
}
else if (NewData data)
{
nod->left = AddNewNode(nod->left, NewData);
nod->height = GetNodeHeight(nod);
if (GetNodeHeight(nod->left) - GetNodeHeight(nod->right) > 1) //左子树高度 - 右子树高度
{
}
return nod;
}
else if (NewData == nod->data)
{
printf("不允许插入重复值");
exit(0);
}
return nod;
}
（若二叉树中只有根节点，那么这个根节点也是叶子节点）
在上面的代码中已经实现了插入新节点并且搜索最低失衡节点的功能，这里可以用前序遍历二叉树并打印节点高度来判断插入节点函数是否正确（上面预留的调整二叉树函数的位置）
遍历二叉树：
1 / 前序遍历AVL树，并打印节点高度 /
2 void PreOrder_Traverse(AVLTree nod)
3 {
4 if (nod != NULL)
5 {
6 printf("data = %d height = %d\n", nod->data, nod->height);
7
8 PreOrder_Traverse(nod->left);
9 PreOrder_Traverse(nod->right);
10 }
11 }
测试插入函数（保证每次插入新节点后的二叉树都是二叉平衡树）
测试数据图解：
测试结果：
搞清楚了各个节点的高度，平衡因子的计算也比较方便了，下面就是AVL树的核心操作“旋转”，不同的失衡情况有不同的旋转方式，一共有四种节点失衡情况，如下图
不同失衡情况下的示例二叉树，如下图（读者可能会发现“最低失衡节点的左子树的左子树还有非空节点”这个判断依据，对第二组图适用，但对于第一组图不太合适）
或者是
（LL型和RR型的操作相对简单）
第一种：LL型
LL型失衡，调整二叉树需要两步
第一步：将失衡节点的左子树的右子树 变成 失衡节点的左子树
第二步：失衡节点 变成 失衡节点未发生操作前左子树的右子树
只看上面的叙述有点绕，下面为实现代码和图片示例
实现代码：
1 / LL型旋转 /
2 AVLTree LL_Rotation(AVLTree nod)
3 {
4 AVLTree temp;
5 temp = nod->left; //临时保存nod的左子树
6
7 nod->left = nod->left->right; //将失衡节点的左子树的右子树 变成 失衡节点的左子树
8 temp->right = nod; //失衡节点 变成 temp的右子树
9
10 nod->height = GetNodeHeight(nod); //更新节点高度
11 temp->height = GetNodeHeight(temp);
12
13 return temp;
14 }
LL型旋转图解
GIF图：
（图片来源：
LL型失衡测试：
测试数据：
测试结果：
第二种：RR型
RR型的操作和基本相同，只是方向相反，这里就不再赘述了
实现代码：
1 / RR型旋转 /
2 AVLTree RR_Rotation(AVLTree nod)
3 {
4 AVLTree *temp;
5 temp = nod->right; //临时保存nod的右子树
6
7 nod->right = nod->right->left;
8 temp->left = nod;
9
10 nod->height = GetNodeHeight(nod); //更新节点高度
11 temp->height = GetNodeHeight(temp);
12
13 return temp;
14 }
View Code
第三种：LR型
LR型失衡的操作相比于LL型失衡操作相对要复杂一点，需要旋转两次才能恢复平衡
第一步：对失衡节点的左子树进行RR型旋转
第二步：对失衡节点进行LL型旋转
因为之前已经写好了LL型和RR型的旋转，这里直接用就可以了，实现代码如下
