前言
在前几日的文章中，我曾提到过map和set的底层实现是基于红黑树，可能有不少读者以为今天的文章会讲解红黑树——但NO，NO，NO，虽然红黑树我会在后续讨论，但由于其较高的难度，今天我并不会直接介绍红黑树。而是将带大家了解另一种特殊的二叉搜索树——AVL树，也就是俗称的“平衡二叉搜索树”。这里的“平衡”二字非常巧妙，接下来正文中我会详细解释这其中的奥妙。
AVL树与红黑树一样，都是非常重要的自平衡二叉搜索树，但我认为相较于红黑树，AVL树的复杂度更低，且其旋转操作与红黑树的操作非常相似。今天，我将为大家详细讲解AVL树，带大家一步步攻克这个小“BOSS”。那么，系好安全带，准备好迎接这次有趣的挑战吧！
1.AVL树的概念
1.AVL树的来源以及简单的介绍
AVL树是最先被发明出来的平衡二叉搜索树，AVL树是一颗空树（什么结点也木有），或者是具备下面性质的二叉搜索树：它的左右子树均是AVL树，并且左右子树的高度差不能大于1（后面即将叙述的平衡因子）。AVL树是一颗高度平衡二叉搜索树，通过控制它的高度来控制平衡（因为这个性质AVL树无法作为数据库存储索引的数据结构）。当然，AVL树还是遵从二叉搜索树的性质的，即根节点大于左边节点，小于右边节点。
可能不少读者好奇，为什么平衡二叉搜索树要被称之为AVL树，是不是有个很励志的故事！那当然是没有故事，它的得名是因为发明它的两个前苏联科学家：G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文中首次提出了平衡二叉搜索树这个概念。（论文名《An algorithm for the organization of information》）。
为了后期更好的理解以及去实现AVL树，我们需要清楚一个概念：平衡因子。
2..平衡因子
在AVL树中，每个结点都有平衡因子，平衡因子就是为了让我们更好更容易的去检测树是否是平衡的。由于每本教材对平衡因子的定义不同，这里小编先确认好自己的定义：平衡因子是右边子树的高度减去左边子树的高度，也就是说如果一颗二叉搜索树平衡了，那么就需要让平衡因子等于-1/0/1，因为树的高度差不能大于1，也就是平衡因子的绝对值不可以大于1。当然，AVL树不一定必须要有平衡因子，但是我在开头说了，它可以帮助我们更容易去检测树是否平衡。
3.思考
当我们提到 AVL 树的平衡因子时，很多读者可能会问，为什么平衡因子允许为 -1 或 1，而不是要求为 0？这个问题的根源在于 AVL 树的设计目标是保持平衡，而不是要求每个节点的左右子树高度完全相等。虽然平衡因子为 0 的情况下树是最平衡的，但要求每个节点的平衡因子为 0 实际上是过于苛刻的。举个例子，当插入的节点数是偶数时，树中不可能每个节点的左右子树高度完全相同，这样就不可避免地会有一些节点的平衡因子为 -1 或 1。实际上，AVL 树允许平衡因子为 -1 或 1，这是为了保持树的平衡，同时避免不必要的旋转操作。
4.见一见平衡二叉搜索树的样子
说了这么多AVL树的概念，但是小编还没让各位见识一下AVL树的样子，于是我自己制作一张图片来让各位更好的去了解AVL树。
2.AVL树的实现——预备工作
AVL树的预备工作其实很简单，我们需要先把每个节点的结构体定义出来，由于键值对我们后期经常使用，所以小编这次直接定义一个键值对类型的结构体，由于结构体的实现难度不是很大，下面我就简单的说一下结构体里面有什么：里面需要有一个pair类型的对象，它存储着键值对，小编刚才漏说了一个知识点：AVL树是一颗三叉链的树，即，它是有左，右，父三个节点的，存储父节点的原因是和之后的更新平衡因子有关，之后我会告诉各位父节点存在的意义。当然，平衡因子可别忘了，下面给出相关的代码。
template<class K, class V>
struct AVLTreeNode
{
// 需要parent指针，后续更新平衡因子可以看到
pair<K, V> _kv;
AVLTreeNode<K, V>* _left; //三叉链，左节点
AVLTreeNode<K, V>* _right; //右节点
AVLTreeNode<K, V>* _parent; //父结点
int _bf; // balance factor 平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0) // 平衡因子 默认肯定是0，会随着插入和删除改变的
{}
};当然，为了避免命名冲突，我把AVL树的实现统一放到了我自己建立的命名空间里面，主打的就是一个严谨（当然，using namespace std是一个典型的不严谨的行为）。
之后，我们需要简单的把AVL树大致框架建立出来，其实就是写一个模板类的方法，把每一个节点作为其的成员变量，如下所示：
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node; //为了更好的表示节点，重命名未尝不是一种比较香的行为。
private:
Node* _root = nullptr;
};3.AVL树的实现——查找操作的实现
由于插入的难度比较大，所以我们先从简单的下手，AVL树的查找操作是一个很简单的接口，它其实就是之前二叉搜索树的查找，唯一的差别还是key和键值对的差别，但其实我们最终还是通过key找寻节点。
首先，我们需要定义好一个节点来代替根节点进行查找，为了保证根节点不被改变，之后就是通过循环加上判断左右子树的key和当前节点key的大小比较来进行节点的查找，如果节点存在的话就返回该节点，如果不存在的话就返回空，难度很小，代码如下所示。
Node* Find(const K& key)
{
Node* cur = _root; //让根保持原样
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
//走到这说明没找到
//cout << "没有找到，您可以插入这个结点";
return nullptr;
}4.AVL树的实现——基本插入实现（难度最高的一集）
bool Insert(const pair<K, V>& kv) //函数的声明下面登录的是我愿称之为本文难度最高的部分——插入功能的实现，因为此时的插入非彼二叉搜索树的插入，二叉搜索树的插入我们仅需找到合适的位置，然后直接插入即可；此时的AVL树可不是简单的直接就插入了，我们需要判断该节点的平衡因子是否在合理的范围内，如果在合理的范围内的话，那么就是插入成功，这是我们最想看到的情况，但是现实往往是残酷的——我们插入一个新的节点的时候可能会导致平衡因子的绝对值大于1，从而让平衡性消失，所以此时我们需要一种方法来位置平衡性，它就是——旋转。
在讲述旋转之前，我们有必要去了解完整插入节点的流程。
1.插入的大致流程
1.此时我们需要先按照二叉搜索树的规矩来进行值的插入（小的往左插，大的往左边插入）。
2.新增节点以后，收到影响的肯定是祖先节点的高度，说直白点是会影响到祖先节点的平衡因子，所以我们需要及时的更新平衡因子，从新插入节点的父节点开始进行平衡因子的更新，也就是从新插入节点->根节点的路径进行平衡因子的更新。实际上最坏的情况才回到根节点，一般来说，我们会在中途就可以进行平衡因子的更新完毕。
3.更新平衡因子的过程没有出现问题，那么就代表着插入结束了。
4.当更新后的平衡因子的绝对值大于1之后，我们就需要进行旋转操作了，在旋转之后，我们就可以让平衡因子降到0，它的本质实际上是降低树的高度；因此当我们旋转完以后，就不用在往上进行旋转因子的更新了，这个操作我待会就会详细说的。
2.平衡因子的更新
平衡因子的更新是AVL树插入的一个很重要的过程，因为平衡因子会体现树的平衡性，也是我们之后是否在进行旋转操作的一个判断的因素，所以说，对于平衡因子如何更新，十分重要。
1.更新的原则
先来回顾下平衡因子的定义：右子树的高度减去左子树的高度（不同教材可能定义不同）；之后子树的高度变化才会影响到当前节点的平衡因子，就拿下图举例：
此时的2所在节点的平衡因子是-1，当我们往他的右子树插入一个元素以后，如下所示：
此时2所在节点的右子树高度发生了变化，因次让它的平衡因子从-1变成了0，但是4所在节点的左子树插入前和插入后的高度并没有发生变化，因此它的平衡因子还是-1。
插入节点，一般来说是会增加高度的，如果新增节点在父节点的右边，那么就让平衡因子++；反之，如果插入的位置在左，那么，就让平衡因子--；parent所在子树的高度决定了是否会往上进行更新。
2.继续更新的情况
如果在更新后parent的平衡因子是1或者是-1，那么可知更新中的parent的平衡因子是从0->1或者是从0->-1，从而知晓更新之前parent所在的子树高度是一致的，插入的节点插在了左子树或者右子树，从而导致一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。
如果更新后的parent的平衡因子变成了2或者是-2，就知更新中的parent的平衡因子从1->2或者是-1->-2，说明在插入之前，parent的子树就是一边高一边低，插入的节点在高的子树那边，parent所在子树的高度变得更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
3.更新停止条件
如果更新后parent的平衡因子为0，那么可知更新中的parent的平衡因子从-1到0或者从-1到0，说明此时在更新之前parent子树是一边高一边低的，并且新插入的节点是在parent子树中低的那边的=，插入后parent所在的子树保持高度不变，并不会影响到其父亲节点的平衡因子，此时就可以更新结束了。
3.基本插入的实现
此时我们就可以进行基本插入的实现了，此时找寻插入的位置和之前二叉搜索树一样，通过循环在加上搜索树本来的规则就可以轻易找到插入位置，这里我就不细说了，实现代码如下：
//先插入节点，之后在进行平衡因子的更新以及旋转操作
//如果此时的树就是个空树
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
//找到插入节点的位置
while (cur)
{
if (kv.first < cur->_kv.first)
{
//比节点的值小，往左边走
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false; //不能出现相同的结点
}
}
//找到节点了之后，我们需要创立好节点，并且和之前的节点建立父子关系。
cur = new Node(kv);
cur->_parent = parent; // 必须让新节点知道父节点是谁
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}做完这些操作以后，我们就需要进行平衡因子的更新了，更新的规则如上所示，此时因为我们需要进行一个路径的更新，因此需要用到循环，这里可能有不少读者认为用递归也可以——递归确实是没有问题的，只不过递归写起来比较难受，并且之后造成死递归的概率比较大，并且效率不如循环高，写起来还没有循环舒服，所以我采取的循环。
之后需要先把父节点的平衡因子进行一波更新，之后通过每次判断父节点的平衡因子来决定是否需要往上更新，一般我们会遇到三种情况：
1. 平衡因子为0，那么就代表此时无须往上更新，break本次循环即可。
2. 平衡因子的绝对值为1，此时代表着高度发生了变化，但是变化幅度不大，没有违法AVL树平衡条件，仍需往上更新。
3.平衡因子的绝对值为2，最麻烦的情况，此时已经违反了AVL树本身的规则，并且此时还需要分成几个小情况，这会在我下篇讲述旋转的时候逐个提到，需要通过循环来让高度变为正常，当然，旋转完以后的树肯定是正常的，无须在往上更新了。
还有个情况，平衡因子的绝对值大于2，此时不合理，直接打个错误报告，退出循环即可。
下面展现代码：
//更新平衡因子
while (parent)
{
if (cur == parent->_right)
{
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)
{
//这里就要进行旋转调整处理
//先进行右单旋处理
if (parent->_bf == -2 && cur->_bf == -1)
{
//...........
}
//也可能是左单旋处理
else if (parent->_bf == 2 && cur->_bf == 1)
{
//...........
}
//最复杂的一集要来了
//左右双旋
else if (parent->_bf == -2 && cur->_bf == 1)
{
//...........
}
//右左双旋
else if (parent->_bf == 2 && cur->_bf == -1)
{
//...........
}
break;
}
else
{
//不合理了这样就
cerr << "二叉树弄错了中间有一步，还没有进行旋转" << endl;
return false;
}
}
return true;
}这就是AVL树的基本插入，通过上述的代码各位就可以看出AVL树的插入十分的麻烦，并且，其中最重要的旋转操作我还没有细讲，由于目前我的灵感比较枯竭，所以我决定下一篇文章再来讲述AVL树，各位读者首先一定要好好的掌握关于平衡因子更新的知识，这和下篇文章的内容息息相关。
5.小结
在本文中，我们从 AVL 树的基本定义、平衡因子的计算规则，到插入过程中的平衡因子更新逻辑，逐步构建起对 AVL 树这一“自平衡二叉搜索树”的完整认识。在下一篇文章中，我将深入剖析 AVL 树中最核心的旋转操作，包括左单旋、右单旋、左右双旋和右左双旋等情况，敬请期待！一起学习的时光总是短暂的，各位大佬下一篇见啦~
