c++进阶——AVL树主要功能的模拟实现(附带旋转操作讲解)

AVL树的实现

本篇文章，我们来重点学习一下AVL树的概念和其模拟实现。虽然set和map系列的容器底层是以红黑树进行实现的。但是学习红黑树前，我们是有必要学习一下AVL树的概念和实现，有助于后续学习。

AVL树的概念及引入

我们先来看看概念

1. AVL树是最先发明的自平衡二叉查找树，AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
2. AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
3. AVL树实现这里我们引入⼀个平衡因子(balance factor)的概念，每个结点都有⼀个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，
4. AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。
5. AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在 ，那么增删查改的效率也可以控制在 ，相比二叉搜索树有了本质的提升。

这里我们注意一下平衡因子的问题我们需要注意一下的是，不是一定是右子树减左子树的高度的，也可以是左子树减右子树的高度。只不过默认的情况下习惯用前者。平衡因子也不是一定要有。在后面的调整AVL树的过程中涉及到一个叫旋转的操作，这个旋转的操作如果使用了平衡因子就会更方便。不添加也是可以的，也有对应的实现方式。当然建议就是添加上去。

我们下面来看看一个比较标准的AVL树长什么样：

我们发现，无论以哪个节点作为空节点，其左右子树的高度差均不会超过1。且均满足平衡因子的值是右子树高度减左子树高度。同时，空树也被认为是一个AVL树，因为没有左右子树，高度差可以认为是0。

AVL树调整问题

我们还需要注意的是，AVL树的插入元素一开始也是先遵循最原始的二叉搜索树的规则进行插入的。但是由于普通的二叉搜索树会出现效率退化问题，所以需要一些方式对树进行调整。AVL树就是通过旋转来调整的。

正常来说，一个AVL树由于其左右子树高度差<=1，也就导致了某个节点对应的子树的平衡因子必然是1，0，-1这三个值。当所有的节点的平衡因子都是这三个值时候，我们可以认为这个树当前是平衡的。

而对一个AVL树进行插入后，如果打破了这个平衡，就会导致某些节点的平衡因子变为2或者-2，这个时候就不符合AVL树的定义了，就打破了这个平衡，所以需要立马进行旋转操作。

如图所示，10这个节点对应的平衡因子就变成了2，需要调整。

至于如何使用旋转操作来调整是我们本篇文章重点需要讲解的内容。具体的我们后面来讲。

AVL树的实现

废话不多说，我们直接上才艺——实现简单的AVL树。

在这里我们实现的AVL树是类似于map的形式的，即key_value模式，没有重复的key关键字。

AVL树的结构

我们先来看节点的结构：

//节点结构
template<class K, class V>
struct AVLTreeNode {pair<K, V> _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;//平衡因子balance factorAVLTreeNode(const pair<K, V>& kv) :_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

我们会发现存储的数据变成了一个pair类，这个类在上一篇文章set和map的使用已经介绍过了。内部存储着两个数据，并且重载和实现了一些接口。节点内还增加了一个叫做平衡因子的成员变量。但是我们发现，这里多了一个指针，看名字就知道指向的是父节点，为什么要定义成这样的三叉链呢？

我们先说结论，每执行一次插入操作，都需要向上进行调整平衡因子。那需要不断地向上遍历。如果不添加指向父节点的指针，那遍历祖先节点是非常困难的。实现是可以实现，但是代价可能有一些大。所以为了更高的效率，也是建议把这个指针的声名加上。

树的基本结构：

template<class K, class V>
class AVLTree {
public:using Node = AVLTreeNode<K, V>;bool Insert(const pair<K, V>& kv) {}//还未实现Node* Find(const K& k) {Node* cur = _root;while (cur) {if (k > cur->_kv.first)cur = cur->_right;else if (k < cur->_kv.second)cur = cur->_right;else return cur;}return nullptr;}void InOrder() {_InOrder(_root);cout << endl;}int Height() {return _Height(_root);}int Size() {return _Size(_root);  }private:void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);cout << "key: " << root->_kv.first << "	" << "value: " << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root) {if (!root) return 0;size_t LHeigth = _Height(root->_left);size_t RHeigth = _Height(root->_right);return (LHeigth > RHeigth) ? LHeigth + 1 : RHeigth + 1;}int _Size(Node* root) {if (!root) return 0;return _Size(root->_left) + _Size(root->_right) + 1;}Node* _root = nullptr;   
};

我们先实现一些比较主要的功能，比如树中节点的个数，还有对树的中序遍历。树的高度等。

非常建议把树的中序遍历先放在内部进行实现。因为对于默认的搜索树来讲，如果使用中序遍历会得到一个升序的序列(按照key排序)。如果中序遍历的代码非常简单，且实现过很多次，所以极大概率是不会出错的。我们每完成一个功能就建议测试一次，就是使用一些操作后看是否中序遍历的结果还正确。如果连着几次测试都没什么太大的问题那就可以了。

至于其它的先不先写都无所谓，只不过后续测试的时候还是要写，所以就放在这里先了。

AVL树的插入

前面的都只是铺垫，插入是最复杂的，我们需要好好学习，这是本篇文章的重点部分。

插入的流程

AVL树插入⼀个值的大概过程

1. 插入一个值按二叉搜索树规则进行插入。
2. 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。
3. 更新平衡因子过程中没有出现问题，则插入结束
4. 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束。

我们先来弄明白这个插入的主要流程：
首先，AVL树的本质还是一个二叉搜索树，只不过有其独特的规则，所以一开始插入的时候，必须先按照普通版本的二叉搜索树的规则进行插入。
其次，新插入的节点平衡因子肯定是0，这点毋庸置疑。但是新插入节点，必然会引起某些子树的左右高度差改变，即平衡因子。所以我们需要不断地调整。经过一系列的分析发现，新插入节点后，只会影响到其到整个树的根节点的路径上的所有节点的平衡因子，说白点就是影响了其所有的祖先节点。所以需要不断地向上调整平衡因子，一旦发现某个节点的平衡因子不符合要求(-1，0，1)就需要调整以这个节点为根节点的子树了。
如若调整路径上没有出现问题，或者调整到根，那就不需要再更新平衡因子了，也就不需要调整这个树地结构了，也就是不进行旋转操作。

更新平衡因子的原则

更新原则：

1. 平衡因子 = 右子树高度-左子树高度
2. 只有子树高度变化才会影响当前结点平衡因子。
3. 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子–
4. parent所在子树的高度是否变化决定了是否会继续往上更新

更新停止条件：

1. 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前parent子树一边高一边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。
2. 更新后parent的平衡因子等于1或-1，更新前更新中parent的平衡因子变化为0->1或者0->-1，说明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。
3. 更新后parent的平衡因子等于2或-2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的目标有两个：
   1、把parent子树旋转平衡。
   2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
4. 不断更新，更新到根，根的平衡因子是1或-1也停止了。

有些人可能会疑问，有没有可能出现，原本平衡因子为2或-2，更新后变为3或-3的呢？这么想其实是有些杞人忧天了。因为这是一个AVL树，我们要做的逻辑就是将这个树始终能保持AVL树对应的性质。如果出现了2或者-2的平衡因子那就需要马上修改了，不可能等到插入的时候调整的时候才发现出现端倪的。

我们举几个例子来看看就很清楚了：

第一种：更新到需要进行旋转的节点

插入13这个值，那此时cur指向的就是新插入的位置，parent指向的是其父节点的位置。此时cur在parent的左边，所以parent的平衡因子–，变为-1，说明高度变了，往上走。cur指向14，parent指向10，此时cur在parent的右边，所以parent的平衡因子++，变为2，说明不平衡了，需要马上进行旋转操作。

第二种：更新到某个节点时发现，此时这个节点的对应子树高度没变

还是按照前一个例子中的哪个调整逻辑往上走，发现调整到3这个节点的时候平衡因子变为0。说明此时以这个节点作为根节点的子树的高度是0，那它的所有祖先节点的子树高度其实是没有改变的，所以不需要再往上调整了。

第三种：最坏更新到根停止

插入7这个值，发现一直调整到整个树的根节点8了还是平衡因子等于1，正常来说，还是需要向上调整平衡因子的。但是此时已经处在整个树的根节点位置了，没有祖先节点了，所以不需要再调整，此时这个树也是平衡的。

以上就是平衡因子大致的调整逻辑了，我们还是发现，在节点中设置一个指向父亲节点的指针还是很有必要的。这极大的帮助了我们简化了向上遍历的逻辑。如果不添加父亲指针，那就需要将经过的所有的祖先节点入栈(这只是一种处理方式)，然后再根据栈来实现这些逻辑。这是很麻烦的，不妨直接使用三叉链，这样更简便一些。

实现插入的基本框架(插入 + 调整平衡因子)

直接上代码框架：

bool Insert(const pair<K, V>& kv) {//插入逻辑if (_root == nullptr) {_root = new Node(kv);return true;}Node* parent = _root, * cur = _root;  while (cur) {if (kv.first > cur->_kv.first)cur = cur->_right;else if (kv.first < cur->_kv.first)cur = cur->_left;else return false;if (cur) parent = cur;}//此时cur指向被插入的位置 parent指向被插入位置的父亲节点cur = new Node(kv);if (kv.first > parent->_kv.first) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;//从cur节点开始向上调整平衡因子 如果不符合情况就得进行旋转操作while (parent) {if (parent->_left == cur)parent->_bf--;elseparent->_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); }return true;
}

这里的插入逻辑其实就是普通版本的二叉搜索树的插入逻辑。我们早已实现过。只不过有所不同的是，这一次实现的时候，key和value是存储在pair类中的。之前实现的是分开存放的。而pair类虽然支持比较大小，但是其重载的比较大小逻辑不符合我们想要的，所以我们需要自行的拿出pair中的first成员进行比较。

向上调整平衡因子的逻辑中，还加入了一个阻断逻辑。这是为了防止出现更新平衡因子的过程中会出现平衡因子出错导致整个AVL树的性质失效。所以可以强制阻断一下。

现在框架搭好了，我们就需要来看看，究竟应该如何实现这里的旋转操作。

旋转操作

这个部分，我们来重点看看旋转的操作。

旋转的原则：

1. 保持搜索树的规则
2. 让旋转的树从不满足变平衡，其次降低旋转树的高度
   旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
   说明：下面的图中，有些结点我们给的是具体值，如10和5等结点，这里是为了方便讲解，实际中是什么值都可以，只要大小关系符合搜索树的性质即可。

右单旋

我们以这个抽象的图为例子来讲解。此时a、b、c三个子树高度为h。这个h可能等于0，也有可能大于0。如果此时我们在a这个子树上多插入一个值，导致a的子树高度+1，这个时候向上调整平衡因子会发现，10这个节点的平衡因子变为-2了。这很明显不符合AVL树的规则，所以我们需要对10这个节点为根节点的子树进行旋转操作。

我们来看看是怎么进行旋转的，把5的右子树给10的左边(因为b子树所有值比5大比10小)，然后再让10为节点的子树变为5的右子树。这样子我们就完成了对树的调整操作。此时看最后一个图，会发现树的高度降低了，且树也变平衡了。这种情况我们就称为右单旋。因为在视觉效果上来看，就很像是将这个树往右边压下去了一点一样。

当然一上来就这样讲肯定会很懵，为什么是这样，这样能代表各种各样的场景吗？这些现在我们来一起探讨一下。

首先肯定会好奇为什么三者高度是一样的呢？首先我们得知道，插入前这也是一个AVL树，那么它必须是平衡的。a、b、c三者必然是满足几种特定的关系才能保持平衡。然后又因为需要进行旋转操作，所以插入新的值后是需要出现不平衡的状态的。对于这个问题如果需要具体分析那是很困难的，这毕竟是发表在论文上的东西。感兴趣的读者可以去查一下这篇论文。

我们随便举两个例子就知道为什么了：假设c的高度比a和b高1，那么这个树本来就是完全平衡的。再插入一个值进去还是平衡的，根本不会涉及到旋转操作。又假如b的高度矮1，那么在a插入会导致5的平衡因子出问题，那么要调整的就是5不是10，其实我们可以理解为调整提前了，单这个调整场景和图中展示的还是一样的。只不过调整的节点靠下罢了。旋转的节点并不是一定要整个树的根节点，也可以是子树的根节点。

所以对于这个问题我们不需要关注太多，这是已经经过论文发表出来的。我们只需要能对旋转有较深的了解和能够实现出即可。

然后就是来看，对应的h可能会有很多情况：

1.h == 0

2.h == 1

3.h == 2

h再变大就不进行分析了，随着h的增大，对应的可能出现的场景是会爆炸性增长的。这么多场景根本分析不完，所以需要使用抽象的图来进行分析。

我们来讲讲h == 2的时候面临的场景，h等于2的子树有三种，但是a必须是x子树。这是要更新10这个节点的前提。因为如果a是y或者z的其中一种，插入第二层的空位置会让这个树便平衡，不需要调整。插入下一层导致的是a子树的根节点需要被旋转，旋转操作向下了。但是旋转的节点可能不是整个树根节点，而是a子树的根节点。这时候把a的根节点当作旋转的节点其实就又回到了右单旋的场景了。所以这些问题我们根本就不需要担心太多，记住原理的基本逻辑即可。论文发表者早就将这些场景考虑到明明白白的了。

我们在这里可以总结一下右单旋的步骤：

1. 使用parent指针指向平衡因子为2或者-2的节点(也称旋转节点)，然后subL指向parent的左孩子，subLR指向subL的右孩子。
2. 让subLR作为parent的左孩子，让subL的_parent指针指向parent。但是有一个问题需要注意，就是h==0的情况下，subLR指向为空，是没有_parent指针的，所以需要特殊处理。
3. 再让subL作为根节点，右指针指向parent，parent的_parent指针指向subL。这里不需要担心subLparent是否为空，因为为空了谈何旋转呢？
4. 但是我们还需要注意的是，单旋操作的旋转节点有可能是根节点，如果是根节点好办，直接让根节点变成新的根节点subL，然后让subL的_parent指针置空即可。但是如果不是根节点，即可能是子树的根节点，那就需要让新的根节点与原来指向旧的根节点的父亲节点进行连接。但是旋转操作后，parent的父亲节点就被修改了，所以我们在旋转前应该现保留一份原来根节点的父亲节点的地址P_parent，然后旋转完后再以这个保留的地址进行连接。
5. 但是还涉及一个问题是，原本的根节点我们一开始也不知道是左孩子还是有孩子，所以我们并不知道此时新的根节点应该作为左孩子还是右孩子。这个处理很简单，虽然我们改变了原来根节点的父亲指针，但是它原来的父亲节点的指向它的指针没有被修改呀。所以可以用逻辑P_parent->_left == parent来判断是左孩子，反之右孩子，然后进行连接即可。
6. 最后更新平衡因子，发现只有parent和subL这两个节点的平衡因子受到影响，且旋转完后二者左右子树高度差是一样的，所以更新为0即可。

最后我们来看代码的实现：

void RotateR(Node* parent) {//右单旋其实就是把cur的右孩子给parent作为左孩子//再让cur作为根节点 parent作为cur的右孩子//还得修改一下被改动节点的_parent指针指向//然后需要将新的子树根节点与原来指向此子树的根节点的节点进行链接Node* Parent = parent;Node* subL = parent->_left;Node* subLR = subL->_right;Node* P_Parent = Parent->_parent;Parent->_left = subLR;//subLR可能为空 所以需要判断if (subLR != nullptr) subLR->_parent = Parent;subL->_right = Parent;Parent->_parent = subL;//链接原来的AVLTree//但是这时候有一个问题 //即原来的子树根节点的父亲P_Parent可能是空(对应此时Parent是整个树的根节点)if (Parent == _root) {_root = subL;subL->_parent = nullptr;}else {//此时的新根节点subL不知道是应该插入在P_Parent的左边还是右边 需要判断一下if (P_Parent->_left == Parent) P_Parent->_left = subL;else P_Parent->_right = subL;subL->_parent = P_Parent; }//更新平衡因子//只需要关注被改动的节点即可subL->_bf = 0;Parent->_bf = 0;}

最后我们需要知道何时需要进行右单旋。我们知道，进行旋转的时候，parent指针一定会指向旋转节点。如若parent指向节点平衡因子为-2并且parent->_left指向节点的平衡因子为-1的时候，就需要对parent指向节点进行右单旋操作了。

左单旋

左单旋的场景如图所示：

其实就是a、c的位置交换了一下，还是在a处进行插入。上面的一通分析其实和右单旋是类似的，只不过逻辑需要反过来一下而已，在这里就不进行赘述了，直接上代码：

void RotateL(Node* parent) {Node* Parent = parent;Node* subR = Parent->_right;Node* subRL = subR->_left;Node* P_Parent = Parent->_parent;Parent->_right = subRL;if (subRL != nullptr) subRL->_parent = Parent;subR->_left = Parent;Parent->_parent = subR;if (Parent == _root) {_root = subR;subR->_parent = nullptr;}else {if (P_Parent->_left == Parent) P_Parent->_left = subR;else P_Parent->_right = subR;subR->_parent = P_Parent;}subR->_bf = 0;Parent->_bf = 0;
}

也就是几个指针的指向问题而已。跟右单旋相比只是换汤不换药，感兴趣的读者自行理解实现

当parent指向节点平衡因子为2并且parent->_right的平衡因子为1时，需要进行左单旋。

左右双旋

前两种场景肯定是不能满足所有的情况的，我们这里举一个例子：

之前都是在左孩子的左边或者右孩子的右边插入，这一次不一样了，插入的位置反过来。
如果还是按照前面单旋的操作对10进行右旋，会发现只是把左边过高的情况变成了右边过高，这肯定是不行的。

a、b、c三个子树的高度也可能是大于0，经过单旋操作发现，旋转出的新树仍然不是一个我们想要的平衡树，这应该怎么操作呢？

在这里直接说结论：
我们需要进行两次旋转操作，我们就以第二个图为例子讲解：

在5的右子树插入，就先对5进行左旋操作，得到新的树如下：

这样一看，这个树经过两次单旋操作就i变得平衡了确实是可以达到想要的结果。所以左右双旋的主要逻辑其实就是复用一下单旋的代码。然后再更新平衡因子。

在单旋的逻辑中，会有节点的平衡因子被改动的。在图中显示出来的就是5、8、10这三个节点。平衡因子都会被改成0，这很明显是不对的。因为我们发现5那个节点的平衡因子应该是-1才对。所以更新平衡因子这一块我们需要好好的探讨一下。

更新平衡因子我们需要分成三个情况来讨论：

左右双旋的情况就是在左子树的右边进行插入。

1. h == 0的情况
   假设a、b、c三个子树均为空树，我们在b这里插入一个值x。按照二叉搜索树的规则，x必然大于5，小于10。先对5左旋，再对10右旋的左右双旋操作后，这个x是根节点，左边为5右边为10，此时三者的平衡因子都是0。所以对应的第一种情况就是当abc均为空树的时候，被修改过的节点的平衡因子应该全部置为0。
   
   我们将这个图进行抽象化，a、b、c三个子树均为空。那么可以我们把插入的子树(图中梯形框住部分)拆分成根节点和左右子树部分。但是此时因为本来就是空树，所以左右子树不存在罢了。直接插入的就是b子树的根节点上。此时经过双旋操作就可以得到。

但是我们需要有一个条件来判断，满足说明条件对应这样一种情况。我们正好可以用b子树插入节点后的平衡因子来判断。如果是空树，那么插入节点后这个b子树的平衡因子一定是0。那就可以以此为判断了。

2.h >= 1但是插入在b的左边
这种情况是这样子的：

在b子树的左半边插入，这个时候会导致b子树的平衡因子变成-1。然后再经过左右双旋操作，我们发现被改动的三个节点的平衡因子是由区别的。我们从结果导向来看，左右双旋的本质就是将b子树的根作为新的根节点，b子树的左半部分要给原本的5的右半边，b子树的右半部分要给原本的5的左半边，然后让被分配的二者再充当b子树的左右半边。

最后得到的是subL的平衡因子为0，parent的平衡因子为1。

3. 第三种情况就显而易见了，就是插入在b子树的右半边
   
   这种情况分析方法和第2点是一样的，就不啰嗦了。parent的平衡因子变成0，但是subL的平衡因子却变成了-1。而新的根subLR的平衡因子发现始终为0。

这样子我们就可以得到左右双旋的代码实现了：

void RotateLR(Node* parent) {Node* Parent = parent;Node* subL = parent->_left;Node* subLR = subL->_right;int subLR_bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//h == 0if (subLR_bf == 0) {subLR->_bf = 0; Parent->_bf = 0; subL->_bf = 0; }//h >= 1else if (subLR_bf == -1) {subLR->_bf = 0;Parent->_bf = 1;subL->_bf = 0;}else if (subLR_bf == 1) {subLR->_bf = 0;Parent->_bf = 0;subL->_bf = -1;}else assert(false);}

还差最后一个问题，就是何时满足左右双旋的场景呢？
经过分析发现，当parent的平衡因子为-2并且parent->_left的平衡因子为1的时候。

右左双旋

右左双旋其实就是在根节点的右子树的左半边进行插入。

也是有像上面一样的三种情况，但是也是属于换汤不换药，所以在这里就展示一下流程图就好了。具体的分析参见左右双旋的方法。

这里就直接上代码了：

	void RotateRL(Node* parent) {Node* Parent = parent;Node* subR = Parent->_right;Node* subRL = subR->_left;int subRL_bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (subRL_bf == 0) {subRL->_bf = 0;Parent->_bf = 0;subR->_bf = 0;}else if (subRL_bf == 1) {subRL->_bf = 0;Parent->_bf = -1;subR->_bf = 0;}else if (subRL_bf == -1) {subRL->_bf = 0;Parent->_bf = 0;subR->_bf = 1;}else assert(false);}

经过分析发现，当parent的平衡因子为2并且parent->_right的平衡因子为-1的时候。

合并旋转代码

至此，旋转平衡二叉树的旋转操作我们就讲解完毕了。从为何要旋转到如何旋转，以及旋转中可能会遇到的场景我们都进行列举了。上述的四种旋转操作就囊括了所有可能面对的需要旋转的场景了，最后是画花一些时间进行理解记忆。切勿死记硬背。

最后我们将实现的旋转代码放回旋转操作部分中：

else if (parent->_bf == 2 || parent->_bf == -2) {//旋转操作//1.右单旋if (parent->_bf == -2 && parent->_left->_bf == -1) RotateR(parent);//2.左单旋else if (parent->_bf == 2 && parent->_right->_bf == 1) RotateL(parent);//3.左右双旋else if (parent->_bf == -2 && parent->_left->_bf == 1) RotateLR(parent);//4.右左双旋else if (parent->_bf == 2 && parent->_right->_bf == -1) RotateRL(parent);//5.其余情况直接报错else assert(false);break;
}

这部分代码直接填充到框架当作的旋转操作部分就可以了。

测试部分

当然，我们刚刚仅仅只是停留在理论阶段。由于旋转的操作比较多，我们很难做到写完一种旋转方式就测试一次。我们现在写完了四种旋转方式，应该先来验证一下是否平衡了。

但是怎么样能证明平衡呢？我们需要紧抓搜索树的性质。对其中序遍历，如果遍历出来的是一个升序序列，那就可以说明搜索树的性质成立了。但是能说明是平衡的搜索树吗？

答案是不行的。要检测是否为平衡树，需要再验证一下平衡树的性质——左右子树的高度差小于1。很多人会说，从上到下检测一下平衡因子不就可以吗？这样万万不可，甚至是自己骗自己的方式。为什么？

因为平衡因子我们是可以随意修改的。我们每插入一次数据，就得更新一次平衡因子。在更新的过程中我们是没办法保证一定是正确的。如果有人无论如和都把平衡因子修改成正确值，那样再以平衡因子来测试是否平衡那不就是自己骗自己吗？所以我们还是需要围绕着定义来走，即不断地去算左右子树的高度差值是否小于等于1。

平衡检测接口

所以这个时候我们在搭框架的时候完成了一些基础接口的作用就在这里了。方便了后续检测。

我们可以写一个IsBanlanceTree函数进行平衡测试：

public:
bool IsBanlanceTree(){return _IsBalanceTree(_root);
}private:
bool _IsBalanceTree(Node* root)
{// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者// pRoot平衡因⼦的绝对值超过1，则—定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "⾼度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因⼦异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树—定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

但是这样写是先序遍历来计算左右子树的高度。这样做在不太追求性能的情况下可以，也比较容易写。但是这样有一个问题，就是从上往下计算，越靠下的层被重复计算的次数会越多。如果递归层数比较深其实是非常低效的。

但是如果可以后续遍历来计算呢？即从下往上来计算不就好很多了吗？从下往上算。这样子我们一开始算的层数就比较低。如果在中间哪里发现问题了就可以直接进行截断，这样子效率会有所提升，所以我们把这个接口改造一下：

bool _IsBalanceTree(Node* root) {if (root == nullptr) return true;if (_IsBalanceTree(root->_left) && _IsBalanceTree(root->_right)) {int LHeight = _Height(root->_left); int RHeight = _Height(root->_right); int diff = (RHeight - LHeight);if (abs(diff) >= 2) {cout << "cout << root->_kv.first" << "高度差异常" << endl;return false;}else if (diff != root->_bf) {cout << "cout << root->_kv.first" << "平衡因子异常" << endl;return false;}else return true;}else return false;
}

测试用例

测试用例1：

void TestAVLTree1()
{AVLTree<int, int> t;// 常规的测试⽤例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试⽤例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e }); }t.InOrder(); cout << t.IsBalanceTree() << endl;  
}int main() {TestAVLTree1();return 0;
}

我们选取一些常规的测试用例和会有双旋的场景测试用例来测试。如果平衡测试接口返回值为真且遍历为中序，就可以基本确认为这个树平衡了：


发现确实如此，所以是平衡了。

测试用例2：
我们来测试一下在大量数据下的一些指标：
如查找速度，插入速度等：

 //插⼊⼀堆随机值，测试平衡，顺便测试⼀下⾼度和性能等
#include<vector>
void TestAVLTree2()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.IsBalanceTree() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();//确定在的值/*for (auto e : v){t.Find(e);}*///随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}int main() {TestAVLTree2();return 0;
}

我们就只展示一下找随机值的速度了：

发现在那么多个数据的情况下，查找速度就变得十分快了。只有平衡的时候才有可能。如果是一个普通的二叉搜索树的效率是绝对不可能这么高的。

对于其他接口的说明

细心的读者肯定发现，我们实现的这个AVL树其实还有一些默认的接口没有完成。比如拷贝构造，赋值重载，析构函数等。我们可以套用一下BinaryTree的那些逻辑就可以。只不过需要对父亲指针和平衡因子特殊处理一下。

甚至我们没有封装迭代器。这些在这里不重要。因为set和map的底层是红黑树，我们到那个时候再来进行这些的实现。而对于AVL树来说，面试的时候大概率考的就是旋转插入操作。删除操作其实不太考察，所以就先不进行实现。当然感兴趣的读者可以前往实现一下。