【C++从0到王者】第三十三站：AVL树

前言

我们常见的查找方式有以下几种：

1. 暴力查找（效率太低）

2. 二分查找（条件太苛刻了，有序，伴随着插入和删除数据效率太低，维护成本很高）

3. 二叉搜索树（极端场景下退化为了链表，效率太低）

以上是我们已经知道的几种查找方式，上面的方式或多或少都存在许多问题。于是，我们便有了下面几种查找方式

1. 二叉平衡搜索树（AVL树/红黑树）
2. 多叉平衡搜索树（B树系列）
3. 哈希表

一、AVL 树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) （右子树的高度减去左子树的高度）

AVL树其实就是高度平衡二叉搜索树，**这里的平衡不是相等，而是高度差不超过。**其实是因为无法做到高度相等，只能做到高度差不超过1。因为总有一些结点是无法做到满二叉树的

如下是一颗典型的AVL树

对于这种AVL树，它的增删查改效率都是很高的。都是logN级别的复杂度

试想一下：

如果是满二叉树，当它高度为h的时候，他的总结点个数为2^h-1==N。

如果是平衡二叉树的话，当它的高度为h的时候，它的节点个数为2^{h-X==N。这里的X属于[1,2}(h-1)-1]

所以它的效率为logN

二、AVL树的实现

1. AVL树的结点定义

如下所示，我们将AVL结点的值定义为一个pair对象，目的是使用key-value模型。bf是一个平衡因子。这里我们还需要使用三叉链结构

template<class K, class V>
struct AVLTreeNode
{pair<K,V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

2. AVL树的插入之插入部分

关于AVL树的插入，我们根据它的特性，不难得知，首先要先将一个值给插入进去，再去考虑控制平衡。

	bool Insert(const pair<K, V>& kv){Node* newnode = new Node(kv);if (_root == nullptr){_root = newnode;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > newnode->_kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < newnode->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}if (parent->_kv.first > newnode->_kv.first){parent->_left = newnode;}else{parent->_right = newnode;}newnode->_parent = parent;//平衡return true;}

如上代码所示，与二叉搜索树的方法类似，我们先想办法插入一个值进去。上面我们已经成功插入了一个数据。这一点是不难的。

1. 我们先申请一个结点

2. 如果根节点为空，那么我们直接将这个结点交给根节点即可。

3. 如果根节点不为空，那么由于是二叉搜索树，那么我们先设定两个结点指针，一个指向空称作parent，一个指向根节点称作cur。

4. 然后我们让cur去与我们要插入结点进行比较，持续迭代，最终我们就可以找出cur为待插入结点的位置，parent为要插入结点的父亲

5. 然后我们根据待插入的值与父节点进行比较，从而确定插入左子树还是右子树。这一步是非常有必要的。

在第五步中，我们极其容易犯一个错误，就是我们想当然的认为，cur此时就是要插入的孩子结点，所以我们会写出cur = newnode这样奇葩的代码，其实是万万不可的。我们可以画个内存图了解一下

6. 插入号了结点以后，我们就可以开始将链接关系了。

3. AVL树的插入之平衡因子的改变

将结点插入以后，我们需要做的就是控制平衡。因为我们AVL树的最终目的还是控制平衡。

我们先来看第一种情况

我们就以这颗树作为例子

首先它本身已经是一颗AVL树了，我们先考虑对右子树的插入

有如下几种情况

当我们插入之后，需要做的就是改变平衡因子。我们先来分析如何改变。

根据上图，我们可以自己观测到，它的改变如下所示

对于这些平衡因子的改变，我们可以总结如下的规律

• 新增在左，parent平衡因子减减
• 新增在右，parent平衡因子加加
• 更新后parent平衡因子==0，说明parent所在的子树高度不变，不再影响祖先，不再沿着祖先的路径往上更新
• 更新后parent平衡因子==1/-1,说明parent所在子树的高度变化，影响了祖先，需要沿着祖先的路径往上更新
• 更新后parent的平衡因子==2/-2，说明parent所在子树出现了问题，已经失衡，需要对parent所在子树进行旋转，使其平衡
• 更新到根节点就可以结束了

代码如下

		//更新平衡因子cur = newnode;while (parent){if (parent->_left == cur){parent->_bf--;}else if (parent->_right == cur){parent->_bf++;}else{assert(false);}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){//子树旋转break;}else{assert(false);}}

4. AVL树的插入之左旋

当一颗树（这棵树有可能是子树，也可能是一颗完整的树）插入一个结点以后，它会变为如下的形状（红色是插入的结点）

一开始，我们的树还是处于平衡状态的，但是当我们插入了一个结点以后，失去了平衡了，所以我们需要对其进行旋转使其进行平衡。

我们不难得知，上面两种树，都是右边的偏高，我们想，可以让cur作为这颗树的根节点，然后parent作为cur的左子树的话，那么就可以使得高度降低1次了。刚好使得我们的AVL树再次平衡了。

如下所示，当我们进行这样的旋转之后，我们会发现cur与parent的平衡因子都变为了0。

在这一步中，我们可以先思考一下为什么这样做了之后，parent和cur的平衡因子会变为了0呢？

其实是因为首先我们这里的情形是插入一个结点后，使得某一个平衡因子变为2,从而导致了失衡，那么既然要导致2，那么之前的parent就需要为1，那么自然parent左边和右边悬挂的两颗子树高度差就需要恰好为1。我们上面的情况就相当于是右边比左边高1。我们把多出来的那个结点称之为cur。

所以一开始的情形就得是parent的左子树，cur的左右子树高度是相同的，且都满足AVL树。然后我们才去插入一个结点。（如果cur的左右子树高度不相同，那么我们会发现，此时的cur应该称作为parent。如果parent的左子树太小，那么更不可能了，因为此时平衡因子早已为2了，早就需要调整了。如果parent的左子树要大一点，那么就不需要进行旋转了。）

当我们插入了这个结点以后，我们就需要控制平衡了，我们控制平衡的核心操作就是

parent->_right = cur->_left;
cur->_left = parent

上面两步操作执行完成之后，parent的左右子树高度一定是相同的，所以parent的平衡因子为0，而且cur的左子树的高度也变为了h+1，右子树由于插入了一个值所以也是h+1,恰好平衡因子也为0了。所以这样一来，使得树的高度整体降了一个且树平衡了。

上面的操作固然是很重要很核心的两步，不过要注意，我们的是三叉链模型，所以我们还需要改变_parent的指向，否则关系会十分混乱。而且还需要去考虑parent所代表的子树是不是一颗完整的树还是说一个子树。如果是子树那么又是左子树还是右子树呢？这些都是需要去考虑的。不过在上面的过程中，我们会发现，需要改变的结点一共就三个：parent，cur，cur->left这三个结点的指针需要进行修改。其他的结点，他们原本的位置是哪里，现在的相对位置仍然不变。

上面这种旋转方式其实就是由于右子树高了，所以需要向左旋转，即将一个结点给左边。我们将其称之为左旋

	void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;//修改parent的链接关系parent->_right = curleft;parent->_parent = cur;//修改curleft的链接关系if (curleft){curleft->_parent = parent;}//修改cur的链接关系cur->_left = parent;cur->_parent = ppnode;//修改ppnode与cur之间的关系if (ppnode == nullptr){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else if (ppnode->_right == parent){ppnode->_right = cur;}}parent->_bf = cur->_bf = 0;}

这样的话，就能保证在保证它是搜索树的条件下，还能降低这个子树的高度了

5. AVL树的左旋抽象图

如上是我们在左旋的情况下的抽象图，为什么要用一个抽象图呢？这是因为我们前面对于左旋的分析并不能完整的表示出左旋的全部情况。

在我们插入一个新的结点之前，a/b/c都是符合AVL规则的子树

当h为0的时候。

这种情况的左旋，我们前文已经讨论过

当h为1的时候

这种情况，还是前文所讨论的情形

但是当h为2的时候，我们每颗高度为2的子树，就分为以下几种情况了，如下的x,y,z三种都属于满足AVL规则的子树

结合上下两张图，在这里有一个细节需要注意:a，b是符合AVL规则的x/y/z，但是c一定是z，也只能是z。

这是因为，我们要保证插入新节点后，要导致根节点的平衡因子变为2。如果是x或者y型的话，无法这样的保证，要么会导致树仍然是一颗AVL树，就不需要进行旋转了。要么就是导致c自己内部的平衡因子变为了2，这样的话就与30这部分就无关了，提前进行了左旋。

这样的话，插入之前的树的可能性就有3*3*1=9种，而由于要插入的位置是z形状的，所以有四种可能，合计36种情况。

显然，我们不可能进行穷举，如果h更高，左旋的情况更加复杂。

所以我们的抽象图，就不在关心里面的具体细节了，我们只需要关心如下所示的几个结点直接的链接关系即可。

而这些链接关系，就是我们如下所示的代码

	void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;//修改parent的链接关系parent->_right = curleft;parent->_parent = cur;//修改curleft的链接关系if (curleft){curleft->_parent = parent;}//修改cur的链接关系cur->_left = parent;cur->_parent = ppnode;//修改ppnode与cur之间的关系if (ppnode == nullptr){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else if (ppnode->_right == parent){ppnode->_right = cur;}}parent->_bf = cur->_bf = 0;	}

6.AVL树的右旋抽象图

右旋的情形与左旋的情形是非常之类似的，如下图所示，所谓右旋，就是左旋的镜像，左子树高了，所以就往右边旋转。

与左旋类似，它的三颗子树高度必须满足高度一样，否则就不是AVL树了，或者说插入一个结点之后还是平衡的，不是我们所期望的亚健康状态，即在插入一个结点后一定需要进行平衡了。

当h为0的时候，如下图所示

当h为1的时候，如下图所示

当h为2的时候，如下图所示是他们每一个子树的可能性。

其中a必须为z类型的子树，b，c可以为x，y，z均可

在h为2的时候，插入前的可能形状组合为3*3*1种，待插入位置有四种插法，可见合计36种。如果考虑的h更大，那么情况更加复杂，但是我们仍然只需要关心那四个最为关键的结点之间的关系即可

如下就是右旋的代码

	void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;//改变parent的链接关系parent->_left = curright;parent->_parent = cur;//改变curright的链接关系if (curright){curright->_parent = parent;}//改变cur的链接关系cur->_right = parent;cur->_parent = ppnode;//改变ppnode与cur之间的关系if (ppnode == nullptr){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else if (ppnode->_right == parent){ppnode->_right = cur;}}parent->_bf = cur->_bf = 0;}

7. AVL树的双旋

我们在前面的抽象图中，主要讨论的是如果是右子树高，继续往右子树的右孩子插入的话，就会诱发左旋

如果是左子树高的话，继续往左子树的左孩子插入新结点，就会诱发右旋

但是我们会发现还有可能会当右子树高的话，往右子树的左孩子插入新节点，或者左子树高的话，往左子树的右孩子插入新节点。这样的话，这颗树又该如何旋转呢？

如果我们还是按照先前的逻辑，右子树高的情况下，往右子树的左孩子插入结点，我们来试一下左旋是如何的进行的。（因为右边高，我们期望往左旋转）

当h为0的时候，下图第一个是我们上面提到的特殊情况，下图第二个是我们原先左旋就能解决的情况。可见这种类似于折线的情形无法使用左旋来完成

如果是h为1的情况下，就是如下图所示的情形。可见这种折线的情况也是不可以实现我们的目的的，这样的操作仅仅只是向右突出的折线变为了向左突出的折线。

并且我们发现，对上面的情形进行了右旋之后，又恢复了之前了状态。当时当我们先右旋，然后在左旋的时候，我们会惊讶的发现，树平衡了。

8. AVL树的右左双旋

前文说道，如果新结点插入的形状是折线形状的，单纯的左旋或者右旋已经无法解决问题了。而这个时候如果我们能够先进行右旋，然后左旋的话，那么问题将得到解决。我们来看抽象图

我们接下来对下面这棵树进行操作，先考虑右子树较高的情况

关于这棵树，我们将90的左子树进行了更细一步的划分，将一共结点单独的抽出来为我们的研究方便。

我们先说结论

以90为旋转点进行右旋，然后以30为旋转点进行左旋。就可以使得这棵树平衡

我们可以先画一下具象图来进行理解

当h==0的时候，即60这个结点就是新插入的结点，他的旋转图如下

当h==1的时候，这个结点可以在60的左边或者右边插入，都是满足条件的。因为都属于右凸出折线插入。仍然是先以90为旋转点进行右旋，然后以30为旋转点进行左旋。可见树平衡

当h==2的时候， 每个子树又呈现出了不同的情况

然而a和d一定是x/y/z中的任意一种，中间这颗子树一定是z形状的。由于我们已经进行了细分，所以中间这棵树我们直接画出具象图

我们的总变化共计3*3*4=36种

可是无论是如何的变化，我们都无需担心，因为只要我们先对90进行右旋，然后对30进行左旋，就一定可以使得这棵树变为平衡。

而诱发这种旋转的条件就是右子树原先比左子树高1，且新插入的结点在右子树的左子树中。当新节点插入以后，parent的平衡因子为2，cur的平衡因子为-1。这两个平衡因子的大小也就是诱发右左双旋的条件。

9. AVL树的右左双旋的本质

关于右左双旋，我们似乎可以直接复用前面的左旋和右旋的代码。但是这样做的话会出现问题的。因为只是左旋和右旋的话会导致平衡因子被改变为0，但是实际上，平衡因子不为0。也就是说平衡因子需要再次处理一下。

我们在分析一下右左双旋，当h==1的时候，我们当时可以插入在左边或者右边都是可以的

从中我们可以看到一个规律，也就是双旋的本质

60的左边变成了30的右边

60的右边变成了90的左边

60变成了这棵树的根

这样的话，我们在观察一下最终平衡因子的变化，似乎就区域于插入到了60的左边还是右边。即取决于插入后60的平衡因子。由于双旋的本质，所以最终插入结束以后，如果是插入到了60的左边，那么左边将被平衡为0，右边将被平衡为1。如果插入到了60的右边，左边被平衡为-1，右边被平衡为0。

如果60本身就是新插入的结点的话，那么最终三个结点都为0

最终我们得出了双选引发的平衡因子问题的解决方法

当插入到了60的右侧，那么最终的变化如下图所示

如果插入到了60的左侧，那么最终的变化如下图所示

如果是60本身就是被插入的，那么就是下图的变化

所以最终我们也可以写出右左双旋的完整代码了

10. AVL树的左右双旋

左右双旋与右左双旋是呈镜像关系的，我们这里直接画出他的抽象图。可见他的本质其实也是一样的。

那么我们就不难写出左右双旋的代码了

	void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){curright->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else if (bf == 1){curright->_bf = 0;cur->_bf = -1;parent->_bf = 0;}else if (bf == -1){curright->_bf = 0;cur->_bf = 0;parent->_bf = 1;}else{assert(false);}}

11. AVL树的验证

上面的程序都是我们在最好的情况下写出来的，但是大部分时候，我们写的代码各种bug，所以我们需要调试，在调试的过程中，自然免不了需要判断一棵树是否为AVL树。所以我们可以利用AVL树的规则，写出如下的代码判断一棵树是否为AVL树

	int _Height(Node* root){if (root == nullptr){return 0;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? 1 + leftHeight : 1 + rightHeight;}bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if ((rightHeight - leftHeight) != root->_bf){cout << "平衡因子异常,当前插入结点为 " << root->_kv.first << endl;return false;}return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);}bool IsBalance(){return _IsBalance(_root);}

同时，当我们写完代码以后，我们可能不知道我们写的是否存在一些问题， 这个我们可以使用如下的测试用例去验证

void testAVL3()
{AVLTree<int, int> avl;srand(time(0));const int N = 10000;vector<int> v(N);for (int i = 0; i < N; i++){v.push_back(rand());avl.Insert(make_pair(v[i], v[i]));cout << avl.IsBalance() << endl;}
}

当运行结果全部为1的时候，说明我们的树没有任何问题

12. AVL树的删除

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与插入不同的是，删除节点后的平衡因子更新，如果更新后平衡因子是1或者-1，那么说明这棵树是不需要进行调整，如果平衡因子为0，说明原来是1或者-1，需要进行向上调整平衡因子。最差情况下一直要调整到根节点的位置 。他的更新策略与插入是相反的

如上图所示，是删除时候的模型，最终需要经历一个右旋。

可以看到上面的过程中，如果需要判断是否旋转的话，不是在其本身的路径上了，而是在另一颗树上判断是否需要旋转，而且旋转时候的条件判断将会更加复杂，双旋时候的平衡因子将更加复杂。所以这里就非常麻烦了。

三、AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即logN。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会变)，可以考虑AVL树，但一个结构经常修改，就不太适合。