数据结构——AVL树(详解 + C++模拟实现)

前言

本篇博客将为大家详细讲述AVL树是什么以及其相对于普通的二叉搜索树有什么优点，将详细讲述其拥有哪些性质，并且通过模拟实现的方式让大家对该数据结构有更深入的理解和认识，对于该数据结构的增删查改操作，其中的删除操作是在普通搜索二叉树的基础上进行一些改进，会简单提及，但不会细讲，重点将会讲述插入操作，查和改操作和二叉搜索树一模一样，也不做讲解。

由于AVL树是一棵特殊的二叉搜索树，因此想要学习AVL树需要先知道二叉搜索树是什么东西，如果有不知道二叉搜索树是什么的小伙半可以先看看博主的另一篇博客:
数据结构—— 二叉搜索树(附c++模拟实现)
该篇博客详细介绍了二叉搜索树。

AVL树的概念

我们知道，二叉搜索树虽然可以缩短查找的效率，但如果数据有序或接近有序，那么此时二叉搜索树将会退化成单支树，此时的查找效率和在链表中搜索等同，效率低下，因此，两位俄罗斯的数学家(G.M.Adelson-Velskii 和E.M.Landis)在1962年的时候发明了一种解决上述问题的方法：

当向二叉搜索树中插入新节点后，如果能够保证每个节点的左右子树高度差的绝对值不超过1(在不破坏二叉搜素树性质的情况下对树中节点进行调整)，即可降低树的高度，从而减少平均搜索长度。

因此，AVL树就这样诞生了！
一棵AVL树可以是空树，或者是具有如下性质的搜索二叉树：

• 它的左右子树都是AVL树
• 左右子树高度之差的绝对值超过1

因此，对于一棵AVL树，最重要的就是如何控制每棵树左右子树高度之差都不超过1，这种控制是通过翻转操作来实现的，博主在下文会重点讲解。

另外，AVL树的实现方式有两种，一种就是在插入的过程中动态的检查左右子树的高度差是否超过1，另外一种就是引入一个新的概念——平衡因子，对于每个节点都存储一个int值表示该根节点左右子树的高度差，负数代表左子树更高，正数代表右子树更高，然后在插入的过程中不断维护每个节点的平衡因子即可。

这里由于第二种方法实现起来相对逻辑更加清晰，所以我们采用第二种方法进行模拟实现，并且用key_value的模型进行实现

AVL树节点的定义

和普通二叉搜索树节点定义不同的是，AVL树的节点为了方便进行旋转操作，需要多加一个指针指向其双亲节点，并且还要有一个int值表示平衡因子，定义如下：

template<typename K, typename V>
struct TreeNode
{pair<K, V> _kv;TreeNode<K, V>* _parent = nullptr;TreeNode<K, V>* _left = nullptr;TreeNode<K, V>* _right = nullptr;int _bf = 0;          //balance factorTreeNode(const K& key, const V& value):_kv({ key, value }){}
};

AVL树类框架

template<typename K, typename V>
class AVL_Tree
{typedef TreeNode<K, V> node;
private:node* _root = nullptr;
public:bool insert(const pair<K, V>& kv)	void inorder();void is_AVL();
};

AVL树的插入

AVL树就是在二叉搜索树的基础上引入平衡因子，因此插入过程其实可以分成两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

对于第一步按照二叉搜索树的规则插入新节点的步骤这里不进行详解，这里重点讲解如何调整插入节点后各个AVL树节点的平衡因子。

pCur表示新插入的节点，pParent表示新插入节点的父节点，（需要找到父节点是节点定义时需要定义指向双亲的指针的原因之一）。
pCur插入后， pParent的平衡因子一定需要调整，插入之前，pParent的平衡因子分为三种情况(-1/0/1)，而根据pCur插入位置的不同，可以分为以下两种情况：

1. 如果pCur插入到pParent的左侧，只需要给pParent的平衡因子减一
2. 如果pCur插入到pParent的右侧，只需要给pParent的平衡因子加一

pParent的平衡因子经过修改后，可能会出现五种情况，0，±1，±2

1. 如果pParent的平衡因子为0，说明修改后以pParent为根节点的最高高度并没有发生变化，所以无需继续调整，插入成功
   如下图所示：
2. 如果插入后pParent的平衡因子为±1，说明插入前pParent的平衡因子一定是0，插入后被更新成±1，说明插入后以pParent为根的子树高度增加了1，也就是说我们需要继续向上更新祖先节点的平衡因子
   如下图所示:
   
   这个过程将不断循环，直到一直更新到pParent的平衡因子为0或者pParent更新到根节点为止。

3. 如果pParent的平衡因子为±2，那么此时以pParent为根的树已经不满足AVL树的性质了，此时，就需要进行旋转操作，对于旋转是什么，我们在下一个小节进行讲解，这里先给出插入代码整体框架：

	bool insert(const pair<K, V>& kv){//如果头节点为空，直接将值赋给头节点即可if (!_root){node* newNode = new node(kv.first, kv.second);_root = newNode;return true;}//如果不为空，寻找插入位置node* parent = nullptr, *cur = _root;while (cur){auto& key = cur->_kv.first;parent = cur;if (kv.first > key)cur = cur->_right;else if (kv.first < key)cur = cur->_left;else return false;}node* newNode = new node(kv.first, kv.second);//循环结束，找到插入位置if (parent->_kv.first < kv.first)parent->_right = newNode;elseparent->_left = newNode;newNode->_parent = parent;cur = newNode;//更新平衡因子while (parent){//先修改因子//判断新增节点的方位对parent的平衡因子进行处理if (parent->_right == cur)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0) break;//如果parent的平衡因子为±1，继续处理else if (abs(parent->_bf) == 1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){//此时以pParent为根的子树已经违反了AVL树的特性，需要进行旋转处理//...}//由于平衡因子的情况只有以上五种，出现其他种类的平衡因子说明AVL树已经被破坏//通过抛异常来显示else throw "the bf out_of_range";}return true;}

AVL树的旋转

上一小节说到，在一棵本来是平衡的AVL树中插入一个新节点，可能导致不平衡，必须调整树的结构，使之平衡，这一步也叫做旋转，AVL树的旋转也分为四种：

旋转的本质其实是使高度较高的子树高度降低，然后将降低的高度给到其另一个较低的子树

新节点插入较高子树的左侧 —— 左左: 右单旋

上图是左单旋的普遍思路，但是我们还需要考虑一些特殊场景:

1. 30的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树
   如果60是根节点，旋转完成之后需要更新根节点，如果60是子树，可能是左子树也可能是右子树，需要注意更改上面的链接关系

这里大家可以自行画图模拟一下各种特殊场景，至于为什么要考虑这些场景，是因为虽然整个思路很简单，但是由于我们整棵树是以三叉链的形式来存储的，所以修改过程中需要维护这一结构。
下面是右旋代码：

void reverseR(node* parent)
{node* cur = parent->_left, *ppnode = parent->_parent;node* curR = cur->_right;//连接parent和curRparent->_left = curR;if (curR)curR->_parent = parent;//连接cur和parentcur->_right = parent;parent->_parent = cur;//连接ppnode和curcur->_parent = ppnode;if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;}else_root = cur;//跟新bfparent->_bf = cur->_bf = 0;
}

新节点插入较高右子树的右侧——右右: 左单旋

由于右单旋和左单旋基本类似，这里不进行细致讲解，下面是实现代码:

void reverseL(node* parent)
{node* ppnode = parent->_parent, *cur = parent->_right;node* curL = cur->_left;// 连接parent和curLeftparent->_right = curL;if (curL) curL->_parent = parent;// 连接parent和curcur->_left = parent;parent->_parent = cur;//跟新parent和cur的平衡因子parent->_bf = cur->_bf = 0;//更新根节点或者与ppnode的连接关系if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;cur->_parent = ppnode;}else{_root = cur;cur->_parent = nullptr;}
}

新节点插入较高左子树的右侧 —— 左右： 先左单旋然后再有单旋

其次，对于右左单旋来说还有一个需要考虑的点就是平衡因子的更新，对于这个问题，我们可以先总结一下上图，（90作为pParent, 30作为pCur, 60作为curR）左右单旋的结果其实使把curR的左子树与pCur链接，curR的右子树与pParent链接，然后curR作为新树的根，那么平衡因子的修改就需要根据60的平衡因子为状况进行修改了,curR的平衡因子一共有三种情况(-1/0/1).我们逐步分析：

1. curR是新插入的节点 —— curR的平衡因子是0，相当于上图中h等于0的情况

插入后pParent，pCur和curR的平衡因子都变成0

2. 插入在curR的左子树 —— curR的平衡因子是-1

由于插入后curR的左子树交给了pCur，也就是上图中的情况，此时pCur和curR的平衡因子都变成0，pParent的平衡因子变成1

3. 插入在curR的右子树——curR的平衡因子是1

对应的就是上图中c的高度是h, b的高度是h - 1, 此时pParent 和 curR的平衡因子都变成0， pCur的平衡因子变成-1

因此，旋转后平衡因子的改变是根据curR的平衡因子的状况就行分类修改的，并且由于上文中我们定义了左右旋转的函数，直接复用就可以得到左右单选的函数，代码如下:

	void reverseRL(node* parent){node* cur = parent->_right, * curL = cur->_left;int bf = curL->_bf;reverseR(cur);reverseL(parent);if (bf == 0)cur->_bf = parent->_bf = curL->_bf = 0;else if (bf == -1){cur->_bf = 1;parent->_bf = curL->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = curL->_bf = 0;}elsethrow "balance factor out_of_range";}

新节点插入较高右子树的左侧：右左单旋

这里的思考方式和右左单选相同，留给大家自己思考。

旋转总结

假如以pParent为根的子树不平衡，即pParent的平衡因子为±2，分以下情况考虑：

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pCur

• 当pCur的平衡因子为1是，执行左单旋
• 如果是-1，执行右左单选

2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pCur

• 当pCur的平衡因子为-1时，执行右单旋
• 当pCur的平衡因子为1时，执行左右单旋
  另外，我们可以发现旋转完成之后，当前根的平衡因子都变成了0，因此不需要继续向上更新

AVL树插入完整代码

public:bool insert(const pair<K, V>& kv){//如果头节点为空，直接将值赋给头节点即可if (!_root){node* newNode = new node(kv.first, kv.second);_root = newNode;return true;}//如果不为空，寻找插入位置node* parent = nullptr, *cur = _root;while (cur){auto& key = cur->_kv.first;parent = cur;if (kv.first > key)cur = cur->_right;else if (kv.first < key)cur = cur->_left;else return false;}node* newNode = new node(kv.first, kv.second);//循环结束，找到插入位置if (parent->_kv.first < kv.first)parent->_right = newNode;elseparent->_left = newNode;newNode->_parent = parent;cur = newNode;//更新平衡因子while (parent){//先修改因子//判断新增节点的方位对parent的平衡因子进行处理if (parent->_right == cur)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0) break;//如果parent的平衡因子为±1，继续处理else if (abs(parent->_bf) == 1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){//进行翻转操作if (parent->_bf == 2 && cur->_bf == 1) reverseL(parent);else if (parent->_bf == -2 && cur->_bf == -1)reverseR(parent);else if (parent->_bf == 2 && cur->_bf == -1) reverseRL(parent);else if (parent->_bf == -2 && cur->_bf == 1) reverseLR(parent);break;}//由于平衡因子的情况只有以上五种，出现其他种类的平衡因子说明AVL树已经被破坏//通过抛异常来显示else throw "the bf out_of_range";}return true;}
private:void reverseL(node* parent){node* ppnode = parent->_parent, *cur = parent->_right;node* curL = cur->_left;// 连接parent和curLeftparent->_right = curL;if (curL) curL->_parent = parent;// 连接parent和curcur->_left = parent;parent->_parent = cur;//跟新parent和cur的平衡因子parent->_bf = cur->_bf = 0;//更新根节点或者与ppnode的连接关系if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;cur->_parent = ppnode;}else{_root = cur;cur->_parent = nullptr;}}void reverseR(node* parent){node* cur = parent->_left, *ppnode = parent->_parent;node* curR = cur->_right;//连接parent和curRparent->_left = curR;if (curR)curR->_parent = parent;//连接cur和parentcur->_right = parent;parent->_parent = cur;//连接ppnode和curcur->_parent = ppnode;if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;}else_root = cur;//跟新bfparent->_bf = cur->_bf = 0;}void reverseRL(node* parent){node* cur = parent->_right, * curL = cur->_left;int bf = curL->_bf;reverseR(cur);reverseL(parent);if (bf == 0)cur->_bf = parent->_bf = curL->_bf = 0;else if (bf == -1){cur->_bf = 1;parent->_bf = curL->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = curL->_bf = 0;}elsethrow "balance factor out_of_range";}void reverseLR(node* parent){node* cur = parent->_left;node* curR = cur->_right;int bf = curR->_bf;reverseL(cur);reverseR(parent);if (bf == 0)cur->_bf = parent->_bf = curR->_bf = 0;else if (bf == -1){parent->_bf = -1;cur->_bf = curR->_bf = 0;}else if (bf == 1){cur->_bf = 1;curR->_bf = parent->_bf = 0;}else throw"balance factor out_of_range";}

AVL树的验证

可以通过监视窗口进行验证，但是这样过于麻烦，我们可以设计一个验证函数：

验证其为二叉搜索树

如果中序遍历能够得到一个有序序列，那就说明是二叉搜索树

public:void inorder() {_inorder(_root); cout << endl;return;}
private:void _inorder(node* root){if (!root) return;_inorder(root->_left);cout << root->_kv.first << ' ' << root->_kv.second << endl;_inorder(root->_right);}

验证其为平衡树

• 每个节点子树的高度绝对值不超过1
• 验证节点的平衡因子是否计算正确
  博主采用的是回溯的方法来验证，先验证左子树和右子树是否为AVL_Tree，同时返回该树的高度，用于验证上层的树是否为AVL_Tree。
  代码如下:

public:void is_AVL() {auto ret = _is_AVL(_root); if (ret.second) cout << "this tree is AVL_tree\n";}
private:pair<int, bool> _is_AVL(node* root){pair<int, bool> ret{ 0, true };if (!root) return ret;auto ret_left = _is_AVL(root->_left);auto ret_right = _is_AVL(root->_right);ret.second = ret_left.second && ret_right.second;//判断平衡因子是否正确int ans_bf = ret_right.first - ret_left.first;if (ans_bf != root->_bf){printf("平衡因子计算错误，正确平衡因子: %d, 当前平衡因子:%d", ans_bf, root->_bf);ret.second = false;}if (abs(ans_bf) >= 2){cout << "平衡因子超过最大值\n";ret.second = false;}ret.first = max(ret_left.first, ret_right.first) + 1;return ret;}

AVL树的删除

因为AVL树也是搜索二叉树，所以可以按照搜索二叉树的方式将节点删除，然后只需要加入更新平衡因子的步骤就可以了，比较不同的是删除操作下平衡因子的更新是如果删除后节点的平衡因子为0还需要继续更新，而如果是±1不需要继续更新，±2进行旋转，但是旋转完成之后由于根的平衡因子变成了0，还有可能需要继续向上更新。

AVL树的性能

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

完整实现代码

template<typename K, typename V>
struct TreeNode
{pair<K, V> _kv;TreeNode<K, V>* _parent = nullptr;TreeNode<K, V>* _left = nullptr;TreeNode<K, V>* _right = nullptr;int _bf = 0;TreeNode(const K& key, const V& value):_kv({ key, value }){}
};template<typename K, typename V>
class AVL_Tree
{typedef TreeNode<K, V> node;
private:node* _root = nullptr;
public:bool insert(const pair<K, V>& kv){//如果头节点为空，直接将值赋给头节点即可if (!_root){node* newNode = new node(kv.first, kv.second);_root = newNode;return true;}//如果不为空，寻找插入位置node* parent = nullptr, *cur = _root;while (cur){auto& key = cur->_kv.first;parent = cur;if (kv.first > key)cur = cur->_right;else if (kv.first < key)cur = cur->_left;else return false;}node* newNode = new node(kv.first, kv.second);//循环结束，找到插入位置if (parent->_kv.first < kv.first)parent->_right = newNode;elseparent->_left = newNode;newNode->_parent = parent;cur = newNode;//更新平衡因子while (parent){//先修改因子//判断新增节点的方位对parent的平衡因子进行处理if (parent->_right == cur)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0) break;//如果parent的平衡因子为±1，继续处理else if (abs(parent->_bf) == 1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){//进行翻转操作if (parent->_bf == 2 && cur->_bf == 1) reverseL(parent);else if (parent->_bf == -2 && cur->_bf == -1)reverseR(parent);else if (parent->_bf == 2 && cur->_bf == -1) reverseRL(parent);else if (parent->_bf == -2 && cur->_bf == 1) reverseLR(parent);break;}//由于平衡因子的情况只有以上五种，出现其他种类的平衡因子说明AVL树已经被破坏//通过抛异常来显示else throw "the bf out_of_range";}return true;}void inorder() {_inorder(_root); cout << endl;return;}void is_AVL() {auto ret = _is_AVL(_root); if (ret.second) cout << "this tree is AVL_tree\n";}
private:void reverseL(node* parent){node* ppnode = parent->_parent, *cur = parent->_right;node* curL = cur->_left;// 连接parent和curLeftparent->_right = curL;if (curL) curL->_parent = parent;// 连接parent和curcur->_left = parent;parent->_parent = cur;//跟新parent和cur的平衡因子parent->_bf = cur->_bf = 0;//更新根节点或者与ppnode的连接关系if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;cur->_parent = ppnode;}else{_root = cur;cur->_parent = nullptr;}}void reverseR(node* parent){node* cur = parent->_left, *ppnode = parent->_parent;node* curR = cur->_right;//连接parent和curRparent->_left = curR;if (curR)curR->_parent = parent;//连接cur和parentcur->_right = parent;parent->_parent = cur;//连接ppnode和curcur->_parent = ppnode;if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;}else_root = cur;//跟新bfparent->_bf = cur->_bf = 0;}void reverseRL(node* parent){node* cur = parent->_right, * curL = cur->_left;int bf = curL->_bf;reverseR(cur);reverseL(parent);if (bf == 0)cur->_bf = parent->_bf = curL->_bf = 0;else if (bf == -1){cur->_bf = 1;parent->_bf = curL->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = curL->_bf = 0;}elsethrow "balance factor out_of_range";}void reverseLR(node* parent){node* cur = parent->_left;node* curR = cur->_right;int bf = curR->_bf;reverseL(cur);reverseR(parent);if (bf == 0)cur->_bf = parent->_bf = curR->_bf = 0;else if (bf == -1){parent->_bf = -1;cur->_bf = curR->_bf = 0;}else if (bf == 1){cur->_bf = 1;curR->_bf = parent->_bf = 0;}else throw"balance factor out_of_range";}//需要知道两个东西，层数高度以及高度差pair<int, bool> _is_AVL(node* root){pair<int, bool> ret{ 0, true };if (!root) return ret;auto ret_left = _is_AVL(root->_left);auto ret_right = _is_AVL(root->_right);ret.second = ret_left.second && ret_right.second;//判断平衡因子是否正确int ans_bf = ret_right.first - ret_left.first;if (ans_bf != root->_bf){printf("平衡因子计算错误，正确平衡因子: %d, 当前平衡因子:%d", ans_bf, root->_bf);ret.second = false;}if (abs(ans_bf) >= 2){cout << "平衡因子超过最大值\n";ret.second = false;}ret.first = max(ret_left.first, ret_right.first) + 1;return ret;}void _inorder(node* root){if (!root) return;_inorder(root->_left);cout << root->_kv.first << ' ' << root->_kv.second << endl;_inorder(root->_right);}};

总结

AVL树的出现较为有效的解决了二叉搜索树在极端情况下效率低下的问题，但还处理的不够完善，因此，后面又出现了红黑树，对于AVL树在一些地方会更有优势，红黑树博主在之后也会讲解！关于AVL树的知识就到此结束了，如果大家有什么疑惑或者发现博主写的有哪些问题，欢迎在评论区指出！