为什么说是“改良”，其实标题的二叉树指的是搜索二叉树，它虽然可以缩短查找的效率，但如果数据已经有序或接近有序的话二叉树就会退化成单支树，这样查找元素的话反而会效率低下。因此，为了解决这个问题，AVL树就得以出现，它的特征是：当向二叉搜索树插入新结点后，如果能保证每个结点的左右子树高度差的绝对值不超过1（调整后的），即可降低树的高度，进而减少搜索频率，提高效率。
一、AVL树简介
一棵AVL树具有以下性质：1.它的左右子树都是AVL树 2.左右子树高度之差（简称平衡因子）的绝对值不超过1。但后续我们为了方便研究，平衡因子通常是右子树高度-左子树高度。
那么如果我要插入一个数据，那会影响哪些结点的平衡因子呢？答案是其部分祖先，为什是部分呢？插入后，平衡因子会更新，若插入右子树，平衡因子++，插入在左子树，平衡因子--（其父节点的平衡因子变化规律），但是再向上找其祖先的平衡因子就不一定会变化，若父节点只有右子树，此时将数据插入左子树，那么其祖先的平衡因子不会变化。（因为其子树的高度没有变化）所以我们说是影响部分祖先。
我们来列举以下情况来分析，什么情况下需要向上更新祖先平衡因子什么时候又不需要。
假设我们现在插入了一个新结点后，其父节点parent平衡因子为0，1/-1，2/-2
第一种情况，说明我插入的位置一定是父节点左右子树中缺少的那个位置（若parent有左（右）那么一定插入的是右（左））此时parent的子树高度没变化，故不需要找祖先。
第二种情况，说明插入前的parent一定是0（不可能是2/-2，因为这样的情况就不满足AVL树的定义了），故插入后parent会多了左（右）子树，高度也会变化，需要找祖先。
第三种情况，说明parent更新前是1/-1，若其有左（右）子树的话会继续插入到其左（右）子树，高度也会增加，也需要找祖先。但此时已经违反了AVL的规则了，需要进行旋转，我们稍后会用代码实现。
我们先进行其结点的封装，因为AVL树的本质也是二叉搜索树，所以我们用之前的模板即可，这里还需要加工一下，用一个新的容器——map，map的本质虽然也是二叉搜索树，但它每个结点的存放是key-value类型（他们被一个pair的类封装又重命名为first和second）（类似于查字典的功能，一一对应），与其相似的还有一个容器set，它的底层就是我们熟悉的二叉搜索树了（有关set和map的封装作者会在下篇或下下篇总结）
接下来，我们看看平衡因子的更新
while (parent)
{
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)
{
break;//第一种情况
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur=parent;
parent = parent->_parent;//向上找祖先
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//不平衡了，需要旋转
}
else
{
assert(false);
}
}注意：这段代码是放在结点插入的函数中且是在插入操作之后进行的，因为平衡因子改变的原因就是进行了插入操作。
二、AVL树的旋转
AVL树的旋转分为四类
1.右右插入——左单旋
我们来看下面这个情景
我们给几个数据命名一下：30——parent，60——subR，b——subRL，那么左单旋的思路就是：subRL变成parent的右，parent变成subR的左，subR变成parent，但实际代码实现时需要考虑很多情况，比如subR为空时情况又是怎样的。
代码如下：
void rotatel(Node*parent)
{
Node*subR=parent->_right;
Node*subRL=subR->_left;
parent->_right=subRL;
if(subRL)//如果不为空才能调整其父节点
subRL->_parent=parent;
Node*Parentparent=parent->_parent;//记录根结点的父节点，因为不确定调整的是整棵树还是一部分子树
subR->left=parent;
parent->_parent=subR;//每次调整后别忘调整其父节点
if(Parentparent==nullptr)//说明调整的是整棵树，那么新的根就是subR
{
_root=subR;
subR->_parent=nullptr;//别忘置空，因为此时subR父节点还是parent
}
else//调整的是子树
{
if(parent==Parentparent->_left)
{
Parentparent->_left=subR;
}
else
{
Parentparent->_right=subR;
}
subR->_parent=Parentparent;
}
parent->_bf=subR->_bf=0;
}
2.左左插入——右单旋 （左单旋的镜像）
代码与左单选是类似的，在此我们直接呈现代码
void rotater(Node*parent)
{
Node*subL=parent->_left;
Node*subLR=subL->_right;
parent->_left=subLR;
if(subLR)
subLR->_parent=parent;
Node*Parentparent=parent->_parent;
subL->_right=parent;
parent->_parent=subL;
if(Parentparent==nullptr)
{
_root=subL;
subL->_parent=nullptr;
}
else
{
if(parent==Parentparent->left)
{
Parentparent->_left=subL;
}
else
{
Parentparent->_right=subL;
}
subL->_parent=Parentparent;
}
parent->_bf=subL->_bf=0;
}有了两个旋转的函数，我们就可以初步完善之前的插入代码了，我们选择摘取前面的一部分填写
else if (parent->_bf == 2 || parent->_bf == -2)
{
//不平衡了，需要旋转
//利用平衡因子判断旋转方式，默认右-左
if(parent->_bf == 2&&cur->_bf==1) //左旋
rotatel(parent);
else if(parent->_bf == -2&&cur->_bf==-1)//右旋
rotater(parent);
}接下来我们就要介绍一些稍微复杂的情况了
3.右左双旋——新节点插入较高右子树的左侧
我们假设以下情景：（注：下面说的所有 ab高度相同，cd高度相同，但ab比cd高一层）
如果abc均为空，d为70，此时如果把数据插入到d的左或右都满足上面的左单旋实现平衡，但如果我插入的位置是b或者c呢？如果通过左单旋进行旋转，发现其并不能达到平衡的效果。我们引进一个新的旋转方式——右左双旋。
我们先看最简单一只情况，假设此时abcd均为空，在90左插入60.（按前面的道理我们知道，无论是左旋还是右旋都无法平衡）接下来的操作：60变成30的右边，90变成60的右边，此时我们发现进行这种操作后情况符合左单旋的情况了，所以在此基础上再来一次左单旋即可（如果在左边同理），第一步的操作我们也叫右单旋（右左双旋中的右单旋）。
上面最简单的情况是不足以说明右单旋的原理的，看下面的情况，假设abcd均存在（bc是新插入的数据，如果插入在d的左右就符合左单旋的情形了，故插在60左右），右单旋的原理就是：60变成30的右，90变成60的右，c变成90的左，其他不变。至此，右单旋结束
下一步，左单旋，结果如下：
其实我们发现，在进行右左双旋之后，如果以60为中心，30为左，90为右，那么该操作的结果就是把中间的左给了左的右，中间的右给了右的左。
幸运的是，这里我们可以复用前面的函数，套一层就好了，代码如下：
void rotaterl(Node*parent)
{
rotater(parent->_right);//右旋以90为中心
rotatel(parent);
}但这个双旋的难处在于其平衡因子的调整，我们假设现在树的情形是，abcd均存在且还要再bc间选择一个地方插入。经分析，插在b和c对于30和90来说两次的平衡因子是不一样的，所以我们需要先知道其插入的位置才能确定平衡因子。很明显，看60那个位置的平衡因子就可以了。
但，如果插入的数据是60呢（也就是abcd均不存在），看结果我们知道最后的平衡因子都是0，所以这个情况比较简单。因此我们还要分情况讨论。
插入后，如果subRL（60）的平衡因子是1说明插在了c下，-1就是b下，0就是60本身是插入的数据。
上面的代码只是实现了结点关系的转换并没有对平衡因子进行修改，所以我们需要完善一下代码。
void rotaterl(Node*parent)
{
Node*subR=parent->_right;
Node*subRL=subR->_left;
int bf=subRL->_bf;
//在旋转之前进行变量的存储以便于对后续平衡因子的修改
rotater(parent->_right);//右旋以90为中心
rotatel(parent);
if(bf==0)
{
subR->_bf=0;
subRL->_bf=0;
parent->_bf=0;
}
else if(bf==1)//插在了c侧
{
parent->_bf=-1;
subR->_bf=0;
subRL->_bf=0;
}
else if(bf==-1)//插在了b侧
{
parent->_bf=0;
subR->_bf=1;
subRL->_bf=0;
}
else
{
assert(false);
}
}4.左右双旋—新节点插入较高左子树的右侧
与右左双旋类似，这边直接上代码加旋转流程图
void rotatelr(Node*parent)
{
Node*subL=parent->_left;
Node*subLR=subL->_right;
int bf=subLR->_bf;
rotatel(parent->left);
rotater(parent);
if(bf==0)
{
parent->_bf=0;
subL->_bf=0;
subLR->_bf=0;
}
else if(bf==-1)
{
parent->_bf=1;
subL->_bf=0;
subLR->_bf=0;
}
else if(bf==1)
{
parent->_bf=0;
subL->_bf=-1;
subLR->_bf=0;
}
else
{
assert(false);
}
}
三、AVL树的验证
上面我们完善了AVL树，但其外表本质还是二叉搜索树，如果按中序遍历输出结果上和正常的二叉搜索树没有区别，无法验证其内部的高度是否平衡。因此我们需要验证其平衡性进而区分出他们的区别。很明显，区分二者最明显的方法就是利用平衡因子。
int _height(Node*root)
{
if(root==nullptr)
return 0;
int leftheight=_height(root->_left);
int rightheight=_height(root->_right);
return leftheight>rightheight ? lefthright+1 : rightheight+1;
}
bool _isbalancetree(Node*root)
{
if(root==nullptr)//空树也是AVL树
return true;
int leftheight=_height(root->_left);//利用计算高度函数获得当前高度
int rightheight=_height(root->_right);
int diff=rightheight-leftheight;//高度差，即根结点的平衡因子
// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
// Root平衡因子的绝对值超过1，则一定不是AVL树
if(abs(diff)>=2||diff!=root->_bf)//abs是绝对值函数，解决了高度差正负的问题
return false;
//如果左右子树都是AVL树，该树一定是AVL树
return _isbalancetree(root->_left)&&_isbalancetree(root->_right);
}
除此之外，我们也可以写一个函数记录AVL树中的结点个数，还是递归思想，这里就不展示了。（需要注意的是，由于上面的函数均需要传结点，但是private成员不可访问，所以我们要在外套一层函数传参才能使用）
至于AVL树的删除作者在此就不多讲解了，思路虽然和插入操作的原理类似，但其情况分析其实要比插入复杂的多，涉及到按搜索树的规则删除，更新平衡因子，其异常后还要旋转处理。
以上就是AVL树的一些基本内容了，其中比较重要的是插入以及旋转的原理和平衡因子的调整，建议小伙伴们反复关顾哦，请留下你宝贵的三连再走，这对我更新的动力真的很大（doge）。