[数据结构] AVL树模拟实现AVL树

标题：[数据结构] AVL树 && 模拟实现AVL树

@水墨不写bug

正文开始：

（一）普通二叉搜索树的痛点

（二）AVL树简介

（1）AVL树的概念

（三）AVL树的实现

（1）AVL树节点的定义

（2）AVL树的插入

（3）AVL树的旋转

i，左单旋（新节点插入较高右子树的右侧---右右：左单旋）

ii，右单旋（新节点插入较高左子树的左侧---左左：右单旋）

iii，左右双旋（新节点插入较高左子树的右侧---左右：先左单旋再右单旋）

iv，右左双旋（新节点插入较高右子树的左侧---右左：先右单旋再左单旋）

（四）AVL树的验证

（五）适用场景与性能分析

（一）普通二叉搜索树的痛点

在学习map和set之前，我们先认识一下AVL树和红黑树，他们是平衡二叉树，不同的是控制平衡的方法不同。本文主要讲解AVL树的概念以及实现的原理，从源代码角度带你理解AVL树的控制平衡的方法。

map/multimap/set/multiset这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的。
但是一般的二叉搜索树有一个致命的缺陷：往树中插入元素有序或者接近有序，二叉搜索树会退化为接近链表形状的单支树结构，时间复杂度会退化为O（N）。

为了能够利用二叉树的结构优势，同时避免二叉树时间复杂度退化的缺陷，AVL树横空出世。

（二）AVL树简介

AVL树的概念由两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年提出，目的是为了解决在 数据有序或者接近有序的二叉搜索树中查找元素时的时间复杂度退化的问题。

平衡的二叉搜索树结构查找的时间复杂度为O（logN），是一个高效的查找复杂度。但是一旦在构建二叉树时，数据有序或者接近有序，那么二叉搜索树会退化为单支树，这就相当于在链表中查找元素，复杂度为O（N），效率低下。

两位数学家提出：当向二叉搜索树中插入新节点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

（1）AVL树的概念

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

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

什么是平衡因子？

平衡因子是人为引入的快速判断二叉树是不是AVL树的一个标准。

平衡因子是一个变量，它存储在每一个二叉树节点中。

根据习惯，平衡因子=右子树的高度-左子树的高度。

(图中为平衡因子的计算结果)

一旦一个节点的平衡因子的绝对值超过1，这表示这个根节点的左右子树的高度差超过1，那么就需要特殊操作（旋转），使得这棵树的左右子树的高度差的不超过1。

如果一棵树是高度平衡的，那么它就是AVL树。如果他有n个节点，那么他的高度可以保持在log(n),那么在搜索时，时间复杂度就降下来了，为O(logN)。

（三）AVL树的实现

AVL树的特点是仅仅使用旋转这一种特殊操作来维持搜索树的平衡，这与其他的维持搜索树平衡的方法相比，是一个特点。本文我们依靠在节点中加入parent指针来更新平衡因子，来实现AVL树，但是这并不代表实现AVL树的方法仅此一种。

（1）AVL树节点的定义

对于节点内存储的值，可以是一个值key，也可以是一个键值对pair{key，val}，但是只存一个值key可以归为pair{key，key}，存的值与键值相等，于是，本文的AVL树采用内部存储pair{key，val}键值对。

什么是key，val？

key是存取时判断的标准，val是key对应的值。key，val都可以是int；也可以key是int，val是string。（需要根据实际情况判断）

什么是pair？

pair是一种STL中的类：

该类将一对不同类型的值(T1和T2)耦合在一起。单个值可以通过它的公共成员first和second来访问。

AVL树节点的定义：
template<class K,class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K,V>& pair_ = pair<K,V>()): _left(nullptr), _right(nullptr), _parent(nullptr)//根节点的_root是空, _pair(pair_), _bf(0){}AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _pair;int _bf;   // 节点的平衡因子
};
唯一需要注意的是缺省参数要给 pair<K,V>() 表示一个匿名对象，这种写法的好处我们以前文章讨论过，这里不再赘述。

（2）AVL树的插入

AVL树的插入过程分为两个步骤：

（1）与普通二叉树相同的插入操作；

（2）调整节点的平衡因子，根据平衡因子，判断是否要进行旋转操作。

就插入操作而言，AVL树相对于普通的二叉搜索树，对二叉树的结构（或者形状）更加关切。

插入操作：（普通二叉树）

处理特殊情况，根为空，直接插入即可。

对于一般情况，先根据键值key找到插入节点的位置，接下来进行的就是节点间指针的连接了——为了在找到插入位置时能够找到插入位置的_parent的位置，创建一个parent指针在cur向下查找的时候记录parent，这样就可以成功得到_parent。但是，现在子节点可以找到父亲，但是父亲没有办法确定子节点是他的左孩子还是右孩子，想要成功连接，还需要确定当前节点是parent的左还是右，所以需要有一次单独的判断。

（具体实现如下：）
// 在AVL树中插入值为data的节点
bool insert(const pair<K,V>& pair)//1,插入  2,调整平衡因子
{//处理特殊情况if (_root == nullptr){_root = new Node(pair);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_pair.first > pair.first){parent = cur;cur = cur->_left;}else if (cur->_pair.first < pair.first){parent = cur;cur = cur->_right;}else//插入的节点等于data时退出{return false;}}//cur就是要插入的位置,parent记录父亲位置cur = new Node(pair);if (pair.first > parent->_pair.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;
插入操作：（AVL树）

两个步骤：

（1）与普通二叉树相同的插入操作；（与上面完全一致）

（2）调整节点的平衡因子，根据平衡因子，判断是否要进行旋转操作。（这是AVL树多做的部分）

如何调整平衡因子？

平衡因子是每一个节点都有的，并且插入一个节点，只会对插入的子树的父祖节点的平衡因子产生影响。所以我们使用迭代法，从下向上依次更新平衡因子：

每一次迭代后，cur和parent会向上移动，同时平衡因子也会更新。

更新平衡因子的方法是比较容易想的：

只看当前新插入节点和parent节点——如果心插入节点是parent左，平衡因子_bf = 右子树高度 - 左子树高度；在左侧插入会导致平衡因子减小1；

只看当前新插入节点和parent节点——如果心插入节点是parent右，平衡因子_bf = 右子树高度 - 左子树高度；在→侧插入会导致平衡因子增大1；
if (cur == parent->_left)parent->_bf--;
elseparent->_bf++;
(上述代码是在每次迭代后的更新平衡因子操作)

如何根据平衡因子来判断是否需要旋转？

在更新平衡因子之后，需要根据平衡因子来判断是否需要旋转，更新平衡因子之后，父节点的平衡因子只有三种情况：
//parent的平衡因子为0    ——原来是1、-1，插入后为0，插入的是较矮的一边，高度不变化，不需要向上追踪父族
//parent平衡因子是-1、1  ——原来是0，插入后为1、-1，原来平衡，插入后不平衡，高度变化，需要向上
//parent平衡因子是2、-2  ——原来是1、-1，插入后加剧了不平衡，高度变化，需要旋转
我们只需要将上述的三种情况转化为代码即可：
while (parent)//parent的平衡因子为0    ——原来是1、-1，插入后为0，插入的是较矮的一边，高度不变化，不需要向上追踪父族//parent平衡因子是-1、1  ——原来是0，插入后为1、-1，原来平衡，插入后不平衡，高度变化，需要向上//parent平衡因子是2、-2  ——原来是1、-1，插入后加剧了不平衡，高度变化，需要旋转
{if (cur == parent->_left)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);}
}
在向上迭代的过程中，如果cur节点的parent节点的平衡因子为2或者-2，这就表明这棵树已经不平衡了，将parent和cur所在的子树单独拿出来，旋转处理。

（3）AVL树的旋转

AVL树的旋转总结来说一共右四种情况，分别是：左单旋，右单旋，左右双旋，右左双旋。

这四种情况的区别仅仅是插入节点的位置不同。

以下四种情况是触发旋转后才考虑的，如果在插入后没有触发旋转，则对下面四种旋转的讨论是没有意义的；（画的图也是刚好可以触发旋转的抽象图，目的是便于理解和梳理思路，便于写代码）

i，左单旋（新节点插入较高右子树的右侧---右右：左单旋）

通过观察，我们发现：

1，旋转的过程需要将bf等于2或者-2的子树拿出来进行——新节点的插入导致15的bf==2，于是把15这课子树拿出来进行旋转处理。

2，旋转后，整棵树变化为平衡二叉树（左子树和右子树高度之差小于2）。

3，至于旋转的为什么这样旋，以及可行性问题等，可以参考当年提出AVL树的学术论文。

这里我们先考虑具体实现：需要几个指针变量记录节点的地址，便于改变树的形状：

parent为树的根节点，subR，subRL不再赘述。

对于一种特殊情况：当高度H==0，这时subRL==nullptr，不能再对subRL解引用，所以在访问subRL的时候，需要特殊判空。
void RotateL(Node* parent)
{Node* subR = parent->_right, * subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;//....
}
接下来，parent的父亲节点以及父亲节点和parent之间的关系没有确定，所以需要一个变量提前保存parent的父亲节点：
Node* Parentparent = parent->_parent;
判断parent与他的父亲节点的关系：

特殊的，如果parent的父亲是空，说明parent是整棵树的根，这种情况直接将旋转后的新根赋值给_root即可；

一般情况，需要判断parent是他的父亲的左孩子还是右孩子：
if (Parentparent == nullptr)
{subR->_parent = nullptr;_root = subR;
}
else
{if (Parentparent->_left == parent){Parentparent->_left = subR;}else{Parentparent->_right = subR;}subR->_parent = Parentparent;
}
最后，根据抽象图更新平衡因子即可：
			subR->_bf = parent->_bf = 0;
左单旋整体代码逻辑：
	void RotateL(Node* parent){Node* subR = parent->_right, * subRL = subR->_left;Node* Parentparent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (Parentparent == nullptr){subR->_parent = nullptr;_root = subR;}else{if (Parentparent->_left == parent){Parentparent->_left = subR;}else{Parentparent->_right = subR;}subR->_parent = Parentparent;}subR->_bf = parent->_bf = 0;}

ii，右单旋（新节点插入较高左子树的左侧---左左：右单旋）

右单旋与与左单旋，无论是插入位置，触发条件，还是旋转处理，都与左单旋类似（某一种对称）这里给出右单旋抽象图，不再赘述：

实现参考：
// 右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left, * subLR = subL->_right;Node* Parentparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (Parentparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (Parentparent->_left == parent){Parentparent->_left = subL;}else{Parentparent->_right = subL;}subL->_parent = Parentparent;}//更新平衡因子，下方的树的平衡因子没有影响subL->_bf = parent->_bf = 0;
}

通过总结，我们发现：插入在较高的子树的同侧（较高的左子树的左侧，较高的右子树的右侧），只需要进行一次旋转就可以树平衡化；但是对于插入位置在较高的子树的异侧时，就需要换一种处理方法——双旋。

iii，左右双旋（新节点插入较高左子树的右侧---左右：先左单旋再右单旋）

对于这棵子树（一般来说是子树，也可能是一整颗树），90节点为根，30节点为左子树，它相对于90的右子树更高。

插入位置在较高的左子树（30这棵子树）的右侧；这时需要先对30这棵子树左单旋，再对90这棵子树右单旋，最终90这棵子树成为平衡树。

在具体实现中，我们可以复用已经实现的左单旋和右单旋的函数：
void RotateLR(Node* parent)
{Node* subL = parent->_left, * subLR = subL->_right;RotateL(subL);RotateR(parent);//.....
}
但是需要注意，在旋转后，需要手动更新平衡因子，因为单旋中更新的平衡因子是只适合单旋的情况，对于双旋，自己设计更新平衡因子：

通过观察抽象图，我们发现，左右双旋的插入位置无非只有两个：

这两种情况我们可以通过观察60的平衡因子来判断，于是，在旋转之前，提前保存60这个节点的平衡因子：
int bf = subLR->_bf;
接下来，根据60节点的平衡因子的情况，更新90这棵子树中，插入位置的父祖节点的平衡因子即可。

特殊处理：60这个节点的平衡因子可能为0，这表示60这个节点本身就是插入的新节点。依然根据抽象图分类假设，更新平衡因子即可。

左右双旋代码实现：
// 左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left, * subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){subLR->_bf = 0;parent->_bf = 0;subL->_bf = -1;}else if (bf == -1){subLR->_bf = 0;parent->_bf = 1;subL->_bf = 0;}elseassert(false);//一般逻辑不会进入，用于检验平衡因子的异常
}

iv，右左双旋（新节点插入较高右子树的左侧---右左：先右单旋再左单旋）

基本思路与左右双旋一致，这两种满足某种对称性，这里仅仅给出抽象图和代码实现：

右左双旋参考代码：
// 右左双旋
void RotateRL(Node* parent)
{Node* subR = parent->_right, * subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}elseassert(false);
}

（四）AVL树的验证

到这里，AVL树的主要工作原理你已经十分清楚了，接下来可以通过一下这个程序来测试一下我们的AVL树的代码逻辑有没有问题：

bool IsAVLTree()
{return _IsBalanceTree(_root);
}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 || root->_bf != diff)return false;// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}size_t _Height(Node* root)
{if (root == nullptr)return 0;int Hl = _Height(root->_left), Hr = _Height(root->_right);return Hl > Hr ? Hl + 1 : Hr + 1;
}

如果没有问题，那么在运行如下场景时，每一次插入后，检测都是满足AVL树的：

#include"AVLTree.h"
int main()
{ddsm::AVLTree<int,int> at;//int arr[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (const auto& e : arr){at.insert({e,e});}at.inorder();cout<<at.IsAVLTree();return 0;
}

运行结果：

4->1
2->1
6->1
1->1
3->1
5->1
15->1
7->1
16->1
14->1

（五）适用场景与性能分析

        AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即logN。

        但是如果要对AVL树做一些结构修改的操作，性能非常低下；（比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。）

        因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合使用AVL树来做底层来实现。

回顾：

二叉搜索树——模拟实现

完~

未经作者同意禁止转载