送给大家一句话：
一个人认清了他在这世界上要做的事情，并且在认真地做着这些事情，他就会获得一种内在的平静和充实。 – 周国平
???????
?️?️?️?️?️?️?️
从零开始构建AVL树
?️1 什么是AVL树?️2 实现AVL树?️ 2.1 框架构建?️ 2.2 插入函数?️ 2.3 AVL树的旋转（重点）?️右单旋：?️左单旋：?️左右双旋：?️右左双旋：?️完成插入操作 ?️ 2.4 寻找函数?️ 2.4 删除函数（了解） ?️3 AVL树的测试?️3 AVL树的性能Thanks♪(･ω･)ﾉ谢谢阅读！！！下一篇文章见！！！
?️1 什么是AVL树
前两篇文章：
【C++】从零开始构建二叉搜索树
【C++】初探 map 与 set
我们学习了二叉搜索树：二叉搜索树虽可以缩短查找的效率，如果数据有序或接近有序二叉搜索树将退化为单支树，这样二叉搜索树效率退化为O(n)，不够高效！所以就有了改进版的二叉搜索树->AVL树（平衡二叉搜索树）
在1962年，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
map与set 的底层实现也是AVL树或红黑树！
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1 / 0 / 1 )如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)，搜索时间复杂度 O( l o g 2 n log_2 n log2n)
通过每次插入删除的调整保证二叉树始终保持一个近乎完美的完全二叉树，规避了极端情况下二叉搜索树退化为单枝树的情况
接下来我们就来研究如何实现AVL树!!!
?️2 实现AVL树
?️ 2.1 框架构建
首先AVL树是在二叉搜索树的基础上进行改进，AVL树节点中加入了：
平衡因子_bf：左右子树的高度差 right子树高度 - left子树高度 ，即左子树插入节点时_bf--，右子树插入节点时_bf++!父指针_parent：指向父节点的指针，为了可以回溯更新父节点的平衡因子。 template<class K, class V>struct AVLtreeNode{typedef AVLtreeNode<K, V> Node;//三叉树结构Node* _parent;Node* _left;Node* _right;//键值对pair<K, V> _kv;//平衡因子int _bf;AVLtreeNode(pair<K, V> kv):_parent(nullptr),_right(nullptr),_left(nullptr),_kv(kv) ,_bf(0){}};注意构造函数的初始化列表，不要出现野指针！！！
?️ 2.2 插入函数
先不管平衡因子这个变量，AVL树的插入比二叉搜索树略微复杂一点，需要多处理一步父指针：
bool Insert(pair<K, V> kv){Node* node = new Node(kv);//如果为空直接赋值if (_root == nullptr){_root = node;return true;}//反之寻找插入位置（按照 key 比较大小）else{Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){parent = cur;if (cur->_kv.first > kv.first){cur = cur->_left;}else if(cur->_kv.first < kv.first){cur = cur->_right;}else{//二叉搜索树默认不重复数据return false;}}//按照大小插入节点if (kv.first > parent->_kv.first){parent->_right = node;}else{parent->_left = node;}//记得要处理父指针！！！node->_parent = parent;cur = node;//更新平衡因子//...}}结下来就是处理平衡因子：左子树插入节点时_bf--，右子树插入节点时_bf++
这里思考一下，平衡因子的处理要到什么情况才停下来？？？
当我们插入一个新节点时，有两种情况：
插入parent的左子树，parent的平衡因子减一！插入parent的右子树，parent的平衡因子加一！父节点的平衡因子经过更新后可以得到三种情况：
parent的平衡因子是 0 ：得到0 说明之前之前parent的左右两边不平衡，插入后平衡了，高度没有改变，不需要处理爷爷节点！！！parent的平衡因子是 ∓1 ：得到正负一说明之前parent的平衡因子是0，插入后以parent为根节点的子树的高度增加了！那么就要继续处理爷爷节点！parent的平衡因子是 ∓2 ：得到这种情况说明在本来就高的一边继续插入了一个新节点！以parent为根节点的子树已经不满足AVL树的结构，需要特殊处理！根据上述是分类我们可以写出处理平衡因子的的代码！
首先可能要向上一直处理，所以干脆写一个while循环，在内部在进行分类：如果需要继续处理爷爷节点，就继续循环，不需要处理就跳出循环！
//...//处理平衡因子//更新平衡因子while (parent != nullptr){if (cur == parent->_left){//左子树增加 父节点平衡因子--parent->_bf--;}else{//右子树增加 父节点平衡因子++parent->_bf++;}//为零直接退出if (parent->_bf == 0){break;}//为 1 或 -1 继续向上进行else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = cur->_parent;}//旋转来哩！！！else if (parent->_bf == 2 || parent->_bf == -2){//分类旋转//旋转之后二叉树平衡！break;}//特殊情况处理 因为未来不知道会出什么bug ,在这里截断一下else{cout << "错误！！！" << endl;assert(false);}}parent的平衡因子是 ∓2的情况的特殊处理就是旋转！！！下面我们来看如何进行旋转！！！
?️ 2.3 AVL树的旋转（重点）
旋转是AVL树的精髓所在！！
首先选择有四种：右单旋 ，左单旋，左右双旋，右左双旋
我们依次来介绍：
?️右单旋：
我们先来看什么情况需要使用右单旋：
这是最简单的情况，简单的向右旋转，使其满足AVL树的性质！
再来看一般情况，并来具体分析一下：
-1，subL的平衡因子是0 ！当我们在subL的左子树插入一个节点，并使subL的平衡因子变为-1 , parent的平衡因子变为-2此时需要对parnet进行右单旋: parent成为subL的右子树subLR成为parent的左子树subL代替原本parnet的位置注意处理平衡因子！！！处理_parent 指针 void RotateR(Node* parent){Node* subL = parent->_left; //左子节点Node* subLR = subL->_right; //左节点的右节点Node* ppNode = parent->_parent;//爷爷节点subL->_right = parent;parent->_parent = subL;parent->_left = subLR;if (subLR != nullptr)subLR->_parent = parent;//处理爷爷节点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{//保证爷爷节点的指向正确if (parent == ppNode->_left){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}//处理平衡因子 因为已经平衡了 所以都为 0 parent->_bf = 0;subL->_bf = 0;}旋转完parent满足AVL树的性质！
?️左单旋：
左单旋与右单旋类似！！！
1，subL的平衡因子是0 ！当我们在subL的左子树插入一个节点，并使subL的平衡因子变为1 , parent的平衡因子变为2此时需要对parnet进行左单旋: 具体实现基本就是右单旋的框架，更改一下变量，不在单独写！
?️左右双旋：
我们来看一种情况：
这种情况既不能通过右单旋解决，也不能通过左单旋解决！！！
这时候就需要继续左右双旋：先进行一次做单旋，在进行一次右单旋。
具体怎么操作，我们来看：
-1，subL的平衡因子是0 ！当我们在subL的右子树插入一个节点，并使subL的平衡因子变为1 , parent的平衡因子变为-2此时需要先对subL进行一次左单旋，使其成为可以进行右单旋的状态，再对parent进行一次右单旋 注意，根据图分析，插入的位置会影响subL和 parent的平衡因子，需要根据subLR分类讨论:
如果插入到subLR的右子树， 那么该右子树最终会变成parent的左子树，所以相当于parent的左子树插入节点，所以parent的平衡因子应为-1如果插入到subLR的左子树， 那么该左子树最终会变成subL的左子树，所以相当于subL的右子树插入节点，所以parent的平衡因子应为1如果subLR自己是新插入的节点，那么平衡因子都为0！ //左右双旋void RotateLR(Node* parent){//先记录相关信息Node* subL = parent->_left;Node* subLR = subL->_right;//需要通过subLR来确定平衡因子int bf = subLR->_bf;//进行旋转//左单旋 subLRotateL(subL);//右单旋 parentRotateR(parent);//平衡因子需要调整！！！//在subLR的左子树插入 if (bf == -1){//右单旋 parent 会将subLR的右子树给parent的左边 ，parent左边比右边低parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}//在subLR的右子树插入 else if (bf == 1){parent->_bf = 0;//左单旋 subL 会将subLR的左子树给subL的右边 ，subL左边比右边高subL->_bf = -1;subLR->_bf = 0;}//如果subLR自身是插入的节点else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{//出错了assert(false);}}这样就好了
?️右左双旋：
来看图：
具体实现与左右双旋类似，先进行一次右单旋，再进行一次左单旋!
细节不在多说，根据图自行书写即可！
?️完成插入操作
我们完成了旋转，就可以补全插入操作的空缺,按情况分好类即可：
//插入节点bool Insert(pair<K, V> kv){Node* node = new Node(kv);//如果为空直接赋值if (_root == nullptr){_root = node;return true;}//反之寻找插入位置（按照 key 比较大小）else{Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){parent = cur;if (cur->_kv.first > kv.first){cur = cur->_left;}else if(cur->_kv.first < kv.first){cur = cur->_right;}else{//二叉搜索树默认不重复数据return false;}}//cur = node;if (kv.first > parent->_kv.first){parent->_right = node;}else{parent->_left = node;}node->_parent = parent;cur = node;//更新平衡因子while (parent != nullptr){if (cur == parent->_left){//左子树增加 父节点平衡因子--parent->_bf--;}else{//右子树增加 父节点平衡因子++parent->_bf++;}//为零直接退出if (parent->_bf == 0){break;}//为 1 或 -1 继续向上进行else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = cur->_parent;}//旋转来哩else if (parent->_bf == 2 || parent->_bf == -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){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}//旋转之后二叉树平衡！break;}//特殊情况处理else{cout << "错误！！！" << endl;assert(false);}}}}在这里一定一定做好测试工作！！！
一定一定保证插入没有问题了在向下进行其他函数的书写，不然出错了就会让人崩溃的！！！
?️ 2.4 寻找函数
寻找与二叉搜索树一样：
//寻找节点bool Find(K key){Node* cur = _root;while (cur != nullptr){if (key == cur->_kv.first){return true;}else if (key < cur->_kv.first){cur = cur->_left;}else{cur = cur->_right;}}return false;}?️ 2.4 删除函数（了解）
删除节点的方法是在二叉搜索树的基础上加入了平衡因子与父节点指针，我们依旧可以按照被删除节点的状况来分类讨论：
1️⃣要删除的结点无孩子结点2️⃣要删除的结点只有左孩子结点3️⃣要删除的结点只有右孩子结点4️⃣要删除的结点有左、右孩子结点⚠️⚠️⚠️下面的过程很重要⚠️⚠️⚠️：
同样要先找到需要删除的节点找到需要删除的节点，按照AB类进行区分，来进行虚拟删除（处理完平衡因子在完全删除） A类（1️⃣2️⃣3️⃣）：直接删除就可以，parent 跳过 cur 指向cur的子树，一定保证指针的指向正确！B类（4️⃣）：使用替换法，寻找右子树的最小值，交换键值对，然后对其进行删除虚拟删除：就是记录下需要删除节点的指针与其父节点指针。 更新平衡因子，与插入有一些不同，删除的情况更加复杂，其对应的平衡因子关系会有 3 种 ⚠️parent 修改后变为 0 ：说明高度变化了，需要继续向上进行修改⚠️parent 修改后变为 ∓1 ：说明相比原来，高度并没有变化（由 0 删除一边而来），可以停止更新平衡因子⚠️parent 修改后变为 ∓2 ： 说明两边此时高度差不满足AVL树，需要进行旋转！此时旋转又要分 6 种情况来讨论：2 * 3 = 6 需要旋转时父树有两个子树，都需要讨论 。子树节点平衡因子有 3 种 -1 1 0 。我们不需要思考这些情况是删除哪里的节点得到的，只需要对每种情况进行处理就可以！！！ | 平衡因子情况 | 如何选择 | 为什么 |
|---|---|---|
| parent为 -2 parent->_left为 -1 | 此时进行右单旋 | 现在是左边高，因此需要向右旋转 |
| parent为 -2 parent->_left为 1 | 此时进行左右双旋 | 此时左边高，并且子树的平衡，所以只需要向右旋转 |
| parent为 -2 parent->_left为 0 | 此时进行右单旋 | 此时是删除了parent右边的节点，导致其不平衡（左高右低），所以向右旋转 |
| parent为 2 parent->_right为 1 | 此时进行左单旋 | 现在是右边高，因此需要向左旋转 |
| parent为 2 parent->_right为 -1 | 此时进行右左双旋 | 因为子树左边高，父树右边高，先对子树进行右旋使其偏差一致，可以进行左旋来修正 |
| parent为 2 parent->_right为 0 | 此时进行左单旋 | 此时右边高，并且子树的平衡，所以只需要向左旋转 |
来看代码：
//删除节点bool Erase(K key){Node* cur = _root;Node* parent = nullptr;//记录需要删除的节点Node* DelParentPos = nullptr;Node* DelPos = nullptr;//寻找替换值//寻找需要被删除的节点while (cur != nullptr){if (key > cur->_kv.first){parent = cur;cur = cur->_right;}else if (key < cur->_kv.first){parent = cur;cur = cur->_left;}else{//现在找到了需要被删除的节点// //删除需要涉及平衡因子的改变//父指针的修正// 根据需要删除节点的状态分出以下4种状态：//a.要删除的结点无孩子结点//b.要删除的结点只有左孩子结点//c.要删除的结点只有右孩子结点//d.要删除的结点有左、右孩子结点//平衡因子的修正比较复杂 所以不能直接删除的情况要进行虚拟删除if (cur->_left == nullptr || cur->_right == nullptr){if (cur->_left == nullptr){//如果删除的的是根节点，单独处理if (cur == _root){_root = cur->_right;if(cur->_right)cur->_right->_parent = nullptr;delete cur;}//只要有祖先节点就要进行平衡因子的处理！！！ 先虚拟删除else{DelParentPos = parent; //标记实际删除结点的父结点DelPos = cur; //标记实际删除的结点}}else{//如果删除的的是根节点，单独处理if (cur == _root){_root = cur->_left;cur->_left->_parent = nullptr;delete cur;}else{DelParentPos = parent; //标记实际删除结点的父结点DelPos = cur; //标记实际删除的结点}}break;}//d.要删除的结点有左、右孩子结点//替换法 + 虚拟删除else{Node* rightMin = nullptr;Node* rightMinParent = cur;//寻找右子树最小值rightMin = cur->_right;rightMinParent = cur;while (rightMin->_left != nullptr){rightMinParent = rightMin;rightMin = rightMin->_left;}//找到可以替换的节点//交换键值对swap(cur->_kv, rightMin->_kv);//把要删除的节点记录下来，模拟删除DelParentPos = rightMinParent;DelPos = rightMin;break;}}}//没有找到的情况if (DelParentPos == nullptr) return false;parent = DelParentPos;cur = DelPos;//然后更新平衡因子while (cur != _root){if (cur == parent->_left){parent->_bf++;}else{parent->_bf--;}//根据不同结果来处理// 为0说明该子树的高度改变 高度变低了 继续向上处理if (parent->_bf == 0){cur = parent;parent = cur->_parent;}//为正负 1 说明该子树的高度没有改变 else if (parent->_bf == 1 || parent->_bf == -1){break;}//出现 正负 2 说明需要进行旋转修正！else if (parent->_bf == 2 || parent->_bf == -2){//分类讨论if (parent->_left->_bf == -1 && parent->_bf == -2){//注意要及时更新parent根节点，不然无法顺利向上推进//cur 节点经过旋转 指向依然正确，是parnet的子树Node* tmp = parent->_left;RotateR(parent);parent = tmp;}else if (parent->_left->_bf == 1 && parent->_bf == -2){Node* tmp = parent->_left->_right;RotateLR(parent);parent = tmp;}else if (parent->_left->_bf == 0 && parent->_bf == -2){Node* tmp = parent->_left;RotateR(parent);parent = tmp;parent->_bf = 1;parent->_right->_bf = -1;//此时 parent 的平衡因子为 1 说明该树删除后高度没有改变，所以不在需要向上更新break;}else if (parent->_right->_bf == -1 && parent->_bf == 2){Node* tmp = parent->_right->_left;RotateRL(parent);parent = tmp;}else if (parent->_right->_bf == 1 && parent->_bf == 2){Node* tmp = parent->_right;RotateL(parent);parent = tmp;}else if (parent->_right->_bf == 0 && parent->_bf == 2){Node* tmp = parent->_right;RotateL(parent);parent = tmp;parent->_bf = -1;parent->_left->_bf = 1;//此时 parent 的平衡因子为 -1 说明该树删除后高度没有改变，所以不在需要向上更新break;}//旋转的本质是将树的高度变低，所以parent树的高度一定会发生改变！//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子！cur = parent;parent = cur->_parent;}else{cout << "旋转出现错误！" << endl;assert(false);}}//处理完平衡因子，现在可以开始删除节点了if (DelPos->_left == nullptr){if (DelPos == DelParentPos->_left){DelParentPos->_left = DelPos->_right;if (DelPos->_right)DelPos->_right->_parent = DelParentPos;}if (DelPos == DelParentPos->_right){DelParentPos->_right = DelPos->_right;if (DelPos->_right)DelPos->_right->_parent = DelParentPos;}}else//右为空{if (DelPos == DelParentPos->_left){DelParentPos->_left = DelPos->_left;if (DelPos->_left)DelPos->_left->_parent = DelParentPos;}if (DelPos == DelParentPos->_right){DelParentPos->_right = DelPos->_left;if (DelPos->_left)DelPos->_left->_parent = DelParentPos;}}delete DelPos;//删除！！！return true;}这一部分值得细细琢磨！
通过借鉴他人的 =代码，我调试了半天才完全排除错误…
?️3 AVL树的测试
我们写了这么多的代码，现在来测试一下，来看看是否满足AVL树！！！
验证AVL树就要来检查每个节点的平衡因子是否满足条件！平衡因子的本质是左右子树的高度差，所以我们可以通过检查每颗子树的高度差来看看是否满足条件：
检查过程需要遍历当前节点的左右子树来获得对应高度，所以我们需要再写一个求高度的函数，都是通过递归来实现，我这里使用的事前序，效率比后序稍差，但写起来简单。
bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}bool _IsBalance(Node* root) {//按照高度进行检查if (root == nullptr) return true;if (abs(_Height(root->_left) - _Height(root->_right) ) >= 2) return false;return _IsBalance(root->_left) && _IsBalance(root->_right);}int _Height(Node* root){if (root == nullptr) return 0;return max(_Height(root->_left) + 1, _Height(root->_right) + 1);}现在：
我们写个测试代码测试一下：
void AVLTreeTest3(){const int N = 10000000;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));//验证过程中是否平衡//cout << "Insert:" << e << "->" << t.IsBalance() << endl;}cout << 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;}来看效果：
我们实际插入了六百万的节点，测试出来其是AVL树，左右平衡！！！
完美！！！！
?️3 AVL树的性能
都说AVL树的性能很NB ,现在我们就来看看到底有多厉害！
我们之间提供 1亿 的数据量，来看看其插入，查找和删除的效率怎么样：
void AVLTreeTest6(){const int N = 100000000;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));}cout << t.IsBalance() << endl;size_t end2 = clock();cout << "Insert:" << end2 - begin2 << 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;size_t begin3 = clock();for (auto e : v){t.Erase(e);}size_t end3 = clock();cout << "Erase:" << end3 - begin3 << endl;}来看用时：
其中一共有六千万的节点，插入共用时 44 s，依次删除所有节点用时 18s，搜索只用了不到1ms！！！
所以AVL树的优缺点很明显：
插入删除的效率比较低，毕竟每次插入删除时都有对应更新平衡因子，还要考虑旋转的情况。搜索的效率是真的快！！！1亿数据量的最多就搜索29次（因为最高才29层）。下面是对AVL树性能的分析：
查找操作
最坏情况时间复杂度：O(log n)平均情况时间复杂度：O(log n)由于AVL树总是保持平衡的，因此查找操作的时间复杂度与树的高度成正比，树的高度最小，查找效率就高。插入操作
最坏情况时间复杂度：O(log n)平均情况时间复杂度：O(log n)插入操作后，AVL树可能会失去平衡。为了恢复平衡，可能需要进行一次或多次旋转（单旋转或双旋转）。尽管如此，这些操作的时间复杂度仍然是对数级别的。删除操作
最坏情况时间复杂度：O(log n)平均情况时间复杂度：O(log n)删除操作与插入操作类似，可能会使树失去平衡，需要进行旋转操作来恢复平衡。空间复杂度
空间复杂度：O(n)AVL树需要存储额外的信息（例如节点的平衡因子），以及可能需要的额外空间来执行旋转操作。AVL树在频繁进行插入和删除操作的场景中可能不是最佳选择。在这些情况下，红黑树等其他自平衡二叉搜索树可能是更好的选择，因为它们对平衡的要求不那么严格，从而在插入和删除操作时可能需要更少的旋转操作。
如果数据结构是静态的，即一旦创建就不会频繁修改，AVL树是一个很好的选择，因为它可以提供高效的查询操作。但是，如果数据结构需要频繁地修改，那么可能需要考虑使用其他数据结构，如红黑树、B树或跳表等，这些数据结构在动态操作方面可能更加高效。
应用场景：
数据库索引：数据库系统经常使用AVL树作为索引结构，因为它能够提供高效的查询、插入和删除操作。字典实现：在需要动态插入和删除键值对的场景中，AVL树是一种有效的数据结构。优先队列：通过维持AVL树的排序性质，可以用来实现优先队列，保证优先级最高的元素总是能够快速被检索。多叉搜索树的基础：AVL树是构建更复杂的多叉搜索树（如B树）的基础。编译器设计：在编译器设计中的符号表中，AVL树可以用来存储和检索变量、函数名及其属性，确保查找的高效性。网络路由算法：在IP路由选择中，AVL树可以用来维护和查询路由表，确保数据包能够高效路由。