【C++ —— AVL树】

AVL树的概念

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

AVL树本质上是一颗二叉查找树，但是它又具有以下特点：

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

在AVL树中，任何节点的两个子树的高度最大差别为 1 ，所以它也被称为平衡二叉树.

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$o(lo{g}_{2}n)$，搜素时间复杂度o($lo{g}_{2}n$)。

本文规定：
平衡因子时采用公式：平衡因子 = 右子树高度 - 左子树高度

AVL树节点的定义

template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;	//存储当前节点的平衡因子//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

这里使用了pair来存储节点的值，_bf表示改节点的平衡因子。

AVL树的插入

 AVL树的插入步骤大致分为下面两种

1. 找到准备插入节点的位置
2. 更新节点的平衡因子
3. 做出相应的调整

---

看下面几个实例：

因为新插入的节点会影响到树原本的平衡，所以每次插入都得更新节点的平衡因子，平衡因子的变化有以下几种：

1. 首先按照搜索树的规则插入
2. 更新插入节点的祖先节点的平衡因子
   • 插入父亲的左边，父亲平衡因子 - -
   • 插入父亲的右边，父亲平衡因子 + +
3. 根据父亲的平衡因子分以下三种调整：
   • 父亲平衡因子是 0 ， 父亲所在子树的高度不变，稳定，不需要向上更新。
   • 父亲平衡因子是 1 / -1 ，父亲所在子树的高度变了，继续向上更新直到稳定。
   • 父亲平衡因子是 2 / -2 ，父亲所在子树已经不平衡了，需要旋转处理。

向上调整

while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0)	//已经平衡，无需调整，结束。{break;}else if (parent->_bf == 1 || parent->_bf == -1)	// 0 -> 1 / -1		需要线上调整{cur = parent;parent = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)		//1 / -1   ->   2  -2   需要旋转{//旋转}}

旋转

AVL树的旋转分为两种：单旋 和 双旋

其中单旋转又分为：右单旋(RotateR) 和 左单旋(RotateL)
其中双旋转又分为：右左双旋(RotateRL) 和 左右双旋(RotateLR)

为什么会有多旋呢？

因为有些情况单旋无法解决，不得不选择双旋，具体情况下文将继续讨论。

左单旋

假设我们有下图AVL树：

现在需要插入新节点15，插入后如图：

但因为此时节点13的平衡因子为2，不稳定，需要旋转处理，如下图：

由结果可知，将节点13进行左旋转，让节点13的父亲变为节点14，节点14的左孩子变为节点13，节点14的父亲变为节点12，即可达到平衡。
动图演示：

代码：

void RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;parent->_right = SubRL;if (SubRL){SubRL->_parent = parent;}Node* ppNode = parent->_parent;SubR->_left = parent;parent->_parent = SubR;if (parent == _root){_root = SubR;SubR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = SubR;}else{ppNode->_right = SubR;}SubR->_parent = ppNode;}parent->_bf = SubR->_bf = 0;}

右单旋

假设我们有下图AVL树：

现在需要插入新节点3，插入后如图：

但因为此时节点5的平衡因子为**-2**，不稳定，需要旋转处理，如下图：

由结果可知，将节点5进行右旋转，让节点5的父亲变为节点4，节点4的右孩子变为节点5，节点4的父亲变为节点10，即可达到平衡。
动图演示：

void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;parent->_left = SubLR;if (SubLR){SubLR->_parent = parent;}Node* ppNode = parent->_parent;SubL->_right = parent;parent->_parent = SubL;if (parent == _root){_root = SubL;SubL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = SubL;}else{ppNode->_right = SubL;}SubL->_parent = ppNode;}parent->_bf = SubL->_bf = 0;}

左右双旋

假设我们有下图AVL树：

现在需要插入新节点7，插入后如图：

但因为此时节点10的平衡因子为 -2 节点4的平衡因子是1 ，不稳定，需要先进行左旋处理，如下图：

左旋完成后，此时节点10的平衡因子仍为 -2 不稳定，再进行右单旋，如下图：

由结果可知，经过节点4的左旋处理，再经过节点10的右旋处理，最终平衡。
动图演示：

由上述的上述调整代码可知，因为节点10的平衡因子是-2，所以在进行左右双旋时，节点10是parent，我们定义 节点5为SubL，节点4为SubLR。分别对SubL和parent进行左单旋和右单旋。

---

但是上述是吧新添加的节点插入到了5的右边，实际上共有下面三中情况可以引起树的双旋转：

1. 插入在较高左子树的右侧的左边
2. 插入在较高左子树的右侧的右边
3. 直接当作较高左子树的右边

插入在较高左子树的右侧的左边：

2. 插入在较高左子树的右侧的右边

3. 直接当作较高左子树的右边

所以由上面三种情况 ，我们可以总结出最终的平衡因子调整规则：

• 当 subLR = 0 时：调整为 subLR = 0 ，subL = 0 ，parent= 0
• 当 subLR =-1 时：调整为 subLR =0 ，subL = 0 ，parent = 1
• 当 subLR = 1 时：调整为 subLR = 0 ，subL =-1，parent = 0

代码：

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

右左双旋

由左右双旋的推理我们可以得出： 当将新添加的节点插入到较高右子树的左侧使需要右左双旋。

具体分为三种情况：

1. 插入在较高右子树的左侧的右边
2. 插入在较高右子树的左侧的左边
3. 直接当作较高右子树的左边

---

1. 插入在较高右子树的左侧的右边

2. 插入在较高右子树的左侧的左边

3. 直接当作较高右子树的左边

代码：

void RotateRL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;int bf = SubRL->_bf;RotateR(SubR);RotateL(parent);SubRL->_bf = 0;if (bf == 1){SubRL->_bf = 0;parent->_bf = -1;SubR->_bf = 0;}else if (bf == -1){SubRL->_bf = 0;parent->_bf = 0;SubR->_bf = 1;}else{SubRL->_bf = 0;parent->_bf = 0;SubR->_bf = 0;}}

AVL树的高度

int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right)) + 1;}

AVL树的验证

bool _IsBalance(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}// 顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}

总结：

代码

#pragma once
#include <assert.h>
#include <vector>
#include <iostream>using namespace std;
template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;	//存储当前节点的平衡因子//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public :bool Insert(const pair<K, V>& kv){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->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0)	//已经平衡，无需调整，结束。{break;}else if (parent->_bf == 1 || parent->_bf == -1)	// 0 -> 1 / -1		需要线上调整{cur = parent;parent = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)		//1 / -1   ->   2  -2{//当前树已经出现了问题，需要旋转if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{//不会出现的情况assert(false);}}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first){cur = cur->_right;}else if (key < cur->_kv.first){cur = cur->_left;}else{return cur;}}return nullptr;}void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;parent->_left = SubLR;if (SubLR){SubLR->_parent = parent;}Node* ppNode = parent->_parent;SubL->_right = parent;parent->_parent = SubL;if (parent == _root){_root = SubL;SubL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = SubL;}else{ppNode->_right = SubL;}SubL->_parent = ppNode;}parent->_bf = SubL->_bf = 0;}void RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;parent->_right = SubRL;if (SubRL){SubRL->_parent = parent;}Node* ppNode = parent->_parent;SubR->_left = parent;parent->_parent = SubR;if (parent == _root){_root = SubR;SubR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = SubR;}else{ppNode->_right = SubR;}SubR->_parent = ppNode;}parent->_bf = SubR->_bf = 0;}void RotateRL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;int bf = SubRL->_bf;RotateR(SubR);RotateL(parent);SubRL->_bf = 0;if (bf == 1){SubRL->_bf = 0;parent->_bf = -1;SubR->_bf = 0;}else if (bf == -1){SubRL->_bf = 0;parent->_bf = 0;SubR->_bf = 1;}else{SubRL->_bf = 0;parent->_bf = 0;SubR->_bf = 0;}}void RotateLR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;int bf = SubLR->_bf;RotateL(SubL);xRotateR(parent);if (bf == -1){SubLR->_bf = 0;SubL->_bf = 0;parent->_bf = 1;}else if (bf == 1){SubLR->_bf = 0;SubL->_bf = -1;parent->_bf = 0;}else if (bf == 0){SubLR->_bf = 0;SubL->_bf = 0;parent->_bf = 0;}else{assert(false);}}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}void InOrder(){_InOrder(_root);cout << endl;}private:int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _IsBalance(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}// 顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;
};void TestAVLTree1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t1;for (auto e : a){/*if (e == 4){int i = 0;}*/// 1、先看是插入谁导致出现的问题// 2、打条件断点，画出插入前的树// 3、单步跟踪，对比图一一分析细节原因t1.Insert({ e,e });cout << "Insert:" << e << "->" << t1.IsBalance() << endl;}t1.InOrder();cout << t1.IsBalance() << endl;
}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);//cout << v.back() << endl;}size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));//cout << "Insert:" << e << "->" << t.IsBalance() << endl;}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;//cout << t.IsBalance() << 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;
}