今天，小编带大家一起来学习平衡二叉树（AVL树）吧。以下就简称AVL树了。
想必能点开这篇博客的朋友都是极度深爱计算机的，那今天就让我们一起揭开AVL树的神秘面纱吧！
目录
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis。
AVL树是搜索二叉树的一种特殊形式。本质上还是一棵搜索二叉树，遵循着左小右大的原则。
但与普通搜索二叉树不同的是，它每个节点的左右子树高度差都不超过1。
为什么要这么设计呢？ 我们举个例子便理解了。
这里要是进行查找65这个数的时候，我们需要一遍遍的递归，直到这颗树的树底。但这样一棵树递归次数太多，高度低还好，如果一棵树太高，就有可能造成递归次数太多，引起栈溢出。
就算不会引起栈溢出，这种树有多高就递归几次的方式，效率也是极低的。
所以我们需要在保持左小右大的前提下，让树的高度尽可能的低，达到一种节点的左右子树高度差不大于1的效果，即是AVL树。
那以上图为例，AVL树就是这样：
这里，我们就能看出来了，要是找到65这个数子，我们只需要递归2次，而原树则需要5次。
所以，AVL树可以理解为是搜索二叉树的优化版本。
我们首先要知道节点怎么左旋转和右旋转。
以上图为例，将L右旋转的话，就是L的右子树变成A，L原来的右子树变成A的左子树即可。
与右旋转相反，将L左旋转，就是L左子树变成A，L原来的左子树变成A的右子树。
既然要实现AVL树，那么我们就需要用到几个参数。
1.struct AVLTree ，这是AVL树的结构体，结构体里除了装数据的val和连接左右子树的指针外，还应该有一个用来判断该节点左右子树高度差的参数bf。bf参数设为int类型，-1代表左子树高，0代表树一般高，1代表右子树高。同时也应注意：结构体的每个节点都应该是指针类型的，所以在一开始定义结构体变量的时候，就要定义一个指针类型的结构体。
2.bool judge_hight，这是一个bool类型的参数，用来判断这一次插入节点后，该节点的子树是否有长高的。judge_hight 初始化为true即可，因为第一次插入数据，树一定会长高。
下面，我们就可以创建AVL树了！
函数声明：void AVLTree_Insert(AVLTree* at, bool judge_hight);
AVL树元素的插入方式与搜索二叉树大体类似，但有些许不同：
假设我们现在有一个数据，按照左小右大的规则插入搜索二叉树后，当找到一个位置插入数据后，我们需要判断树是否长高了，这里就需要分为两大类了：
插入左子树和插入右子树。
如果数据是插入了节点a的左子树导致长高，那么我们就需要判断a的左右子树高度差（bf）这里分为三种情况：
bf = 0 左右子树平衡，将bf改为1即可。
bf = -1 右边高， 加入左节点，树就平衡了，bf改为0，judge_hight置为false。
bf = 1 左边高，需要调用函数来判断该节点a是否还平衡，之后judge_hight置为false。设调用的函数为：void Treebalance_left(AVLTree* at)。在这个函数里，我们就需要继续判断是插入了l的左节点还是右节点。
插入左子节点的含义是：节点插入a的左子树后，使a不再平衡，原因是a的左子树的左边变高。
以下三种均为插入左子节点的情况，这三种看似不同，其实一致，均是l的左边高。
图上看已经很清楚了， a的已经不平衡了，我们就需要进行右旋转a的左子节点来使a平衡。
相当于直接把l提到a的位置。
旋转后结果如图：
这里可以看出，a的bf改为0，l的bf改为0。
与插入左子节点相反，插入右子节点是指：节点a不平衡是因为左边高，而a左边高是因为a的左子节点的右边高。也就是在a的左子节点插入了右子树。
同理，以下三种均为插入右子节点的情况，即a不平衡，l的右边高。
对于a而言，这种也是不平衡的情况，那么我们需要先对l进行左旋转，再对n进行右旋转。
这里值得注意的是：l左旋转后n右旋转，其实就是使n先转到l的位置，再转到a的位置。
第一步：l左旋转（n转到l位置）
第二步：n右旋转（n转到a位置）
这里我们需要注意的是：此时a与l的bf值三棵树并不相同。为什么呢，因为一开始的时候三棵树n的左右子树高度并不相同。
下面给出n的bf值与a、l的bf值的规律：
| 第一棵 | 第二棵 | 第三棵 | |
| n的BF值 | 0 | 1 | -1 |
| a和l的BF值 | a=0 l=0 | a=-1 l=0 | a=0 l=1 |
我们需要注意的是，三棵树的旋转方式一样，但BF值不同，所以在代码里要先判断n的BF值再旋转。
数据插入右子树，我们也需要判断此时节点的平衡情况，再做下一步打算。同样的，也是先判断插入数据前节点的bf值来判断，也分三种情况：
BF=0：插入右子树后BF=-1
BF=1：插入右子树后，节点平衡，BF=0，judge_hight置为false。
BF=-1：插入右子树后节点可能不平衡，需要调用函数判断一下。之后judge_hight置为false。
可以设调用的函数为void Treebalance_right(AVLTree* at);这个函数里，我们要传入该节点的右子树，判断数据是插入它的左子节点还是右子节点。
以下三棵树均为插入右子节点的情况。三棵树平衡方式一样，均为l左旋转，使l转到a的位置。
l左旋转后：
以下三棵树均为插入左子节点的情况，旋转方式均为l右旋转后n左旋转，即n先跳到l位置后跳到a位置。
但是与插入左子树右子节点类似，要先判断n的BF值,写出相应的a与l旋转后的BF值再旋转。这里小编先给大家旋转完再判断BF值。（代码里一定要先判断！）
l右旋转（n跳到l的位置）
n左旋转（n跳到a的位置）
到这里,n的BF值与a、l的BF值的关系也就出来了。
| n的BF值 | 0 | 1 | -1 |
| a的BF值 | 0 | 0 | 1 |
| l的BF值 | 0 | -1 | 0 |
#define LH 1//左树高
#define NH 0//一般高
#define RH -1//右树高
typedef int AVLTreetype;
typedef struct Tree
{
AVLTreetype val;
struct Tree* leftchild, * rightchild;
int bf;//此节点子树的高度差
}*AVLTree, Tree;
void AVLTree_Insert(AVLTree& at, AVLTreetype n, bool& judge_hight);//插入AVL树
void AVLTreebalance_left(AVLTree& at);//判断左树是否平衡
void AVLTreebalance_right(AVLTree& at);//判断右树是否平衡
void L_Roll(AVLTree& at);//左旋
void R_Roll(AVLTree& at);//右旋
void AVLTree_Insert(AVLTree& at, AVLTreetype n, bool& judge_hight)//插入
{
if (at == NULL)
{
AVLTreeinit(at, n);
judge_hight = true;
return;
}
else
{
if (n == at->val)
{
cout << "\nHave Insert：" << n << endl;
judge_hight = false;
return;
}
else if (n < at->val)
{
if (at->leftchild)
{
AVLTree_Insert(at->leftchild, n, judge_hight);//递归
}
else// at->leftchild == NULL
{
AVLTreeinit(at->leftchild, n);
judge_hight = true;
}
if (judge_hight)
{
switch (at->bf)
{
case LH:
judge_hight = false;
AVLTreebalance_left(at);//判断是否平衡
break;
case NH:
at->bf = LH;
break;
case RH:
at->bf = NH;
judge_hight = false;
break;
}
}
}
else
{
if (at->rightchild)
{
AVLTree_Insert(at->rightchild, n, judge_hight);
}
else// at->rightchild == NULL
{
AVLTreeinit(at->rightchild, n);
judge_hight = true;
}
if (judge_hight)
{
switch (at->bf)
{
case RH:
judge_hight = false;
AVLTreebalance_right(at);
break;
case NH:
at->bf = RH;
break;
case LH:
at->bf = NH;
judge_hight = false;
break;
}
}
}
}
}
void AVLTreebalance_left(AVLTree& at)
{
AVLTree l = at->leftchild, lr = l->rightchild;
switch (l->bf)
{
case LH：
at->bf = l->bf = NH;
R_Roll(at);
break;
case RH:
switch (lr->bf)
{
case LH:
at->bf = RH;
l->bf = NH;
break;
case NH:
at->bf = l->bf = NH;
break;
case RH:
at->bf = NH;
l->bf = LH;
break;
}
L_Roll(at->leftchild);
R_Roll(at);
break;
}
}
void AVLTreebalance_right(AVLTree& at)//判断树右边是否平衡
{
AVLTree r = at->rightchild, rl = r->leftchild;
switch (r->bf)
{
case RH:
at->bf = r->bf = NH;/
L_Roll(at);
break;
case LH:
switch (rl->bf)
{
case LH:
at->bf = NH;
r->bf = RH;
break;
case NH:
at->bf = r->bf = NH;
break;
case RH:
at->bf = LH;
r->bf = NH;
break;
}
R_Roll(at->rightchild);
L_Roll(at);
break;
}
}
void L_Roll(AVLTree& at)//左旋
{
AVLTree r = at->rightchild;
at->rightchild = r->leftchild;
r->leftchild = at;
at = r;
}
void R_Roll(AVLTree& at)//右旋
{
AVLTree l = at->leftchild;
at->leftchild = l->rightchild;
l->rightchild = at;
at = l;
}小编呕心沥血之作，恳请点赞关注支持一下吧~