一. AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称 平衡因子)的绝对值不超过1(-1/0/1)
平衡因子= 右子树高度 - 左子树高度；非必须，也可以不要，只是方便我们实现的一种方式！
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O ( l o g 2 n ) O(log_2 n) O(log 2 n)，搜索时间复杂度O( l o g 2 n log_2 n log 2 n)
单支树的效率是 O ( N ) O(N) O(N)，AVL树不一样，在10亿中只用找30次（可能多一点）
二. AVL树结点的定义
此处我们定义成三叉链结构 ，方便后序的操作；也在每个节点引入了平衡因子（右子树高度-左子树高度），还需要实现一下构造函数，左右子树以及父节点都是空，再把平衡因子设置为0即可
template<class K, class V> struct AVLTreeNode { //定义三叉链 AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; //存储的键值对 pair<K, V> _kv; //平衡因子(balance factor) int _bf; //构造函数 AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_bf(0) {} };
注意：平衡因子不是必须的，只是我们实现高度平衡的一种方式，不用平衡因子也是可以实现的
三. AVL树的插入
插入节点有三个步骤
按照二叉搜索树的原理，找到待插入的位置
判断待插入的节点是在parent的左还是右，插入节点
更新平衡因子，如果发现不平衡，则要旋转
🔥因为AVL树本身就是一颗二叉搜索树，插入规则（比较节点大小即可）：
插入的节点key值 > 当前位置的key值，插入到右子树
插入的节点key值 < 当前位置的key值，插入到左子树
插入的节点key值等于当前位置的key值，插入失败
🌈那判断完插入成功与否，是不是就要判断平衡因子的更新了
平衡因子是否更新取决于：该结点的左右子树的高度是否发生了变化，因此插入一个结点后，该结点的 祖先结点的平衡因子可能需要更新
🌏更新平衡因子的规则：
新增在右，parent -> bf++；新增在左，parent -> bf --；
每更新完一个结点的平衡因子后，都需要进行以下判断：
如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子
如果parent的平衡因子等于0；表明无需往上更新平衡因子
如果parent的平衡因子等于-2或者2；就已经不平衡了，需要旋转处理
如果parent的平衡因子大于2或者小于-2；就说明之前插入的就不是AVL树了，赶紧去检查💥
更新后的平衡因子 分析
-1 or 1 说明parent插入前的平衡因子是0；左右子树高度相等，插入后有一边高，parent高度变了，则需要往上继续更新
0 说明parent插入前的平衡因子是 -1 or 1；左右子树一边高一边低，插入后两边相等，插入的填上了矮的那一边，parent的高度不变，不需要继续往上更新
-2 or 2 说明parent插入前的平衡因子是 -1 or 1；已经是平衡的临界值了；插入后变成-2 or 2 ；打破了平衡，parent所在的子树需要旋转处理
最坏的情况如下：一路更新到root根节点
那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，向上递归，直到parent为空的情况，以下逻辑是必须的
cur = parent;
parent = parent->_parent;
当平衡因子出现了2/-2的情况，要对子树进行旋转处理，但也要遵守原则
旋转成平衡树
保持搜索树的规则
而旋转有四种大情况，对此我们要进行分类：
当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋
当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋
当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋
当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋
注意：旋转过后无需再往上更新平衡因子了，因为高度已经没有发生变化了，也就不会影响父节点的平衡因子了
//插入 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 (cur->_kv.first < kv.first)//插入节点值大于当前节点的key { parent = cur; cur = cur->_right;//往右走 } else if (cur->_kv.first > kv.first)//插入节点值小于当前节点的key { parent = cur; cur = cur->_left;//往左走 } else { //插入的节点key值等于当前位置的key值，插入失败 return false; } } //开始插入 cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else if (parent->_kv.first < kv.first) { parent->_left = cur; } //连接parent cur->_parent = parent; //控制平衡 //1、更新平衡因子 while (parent) { if (cur == parent->right) { parent->_bf++; } else { parent->_bf--; } if (parent->_bf == -1 || parent->_bf == 1)//也可以用abs { cur = parent; parent = parent->_parent; } else if (parent->_bf == 0) { break; } else if (parent->_bf == -2 || parent->_bf == 2) { //说明parent所在的子树已经不平衡了，需要旋转 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent);//左单旋 } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent);//右单旋 } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent);//左右双旋 } break; } else { assert(false);//在插入前树的平衡因子就有问题 } } return true; }
四. AVL树的旋转
🥑左单旋
新节点插入较高右子树的右侧—右右：左单旋
⚡动图展示：
抽象图过程解析：
其中h可以等于0、1、2等等，不过都可以归纳到这种大情况，处理情况都一样，都是引发parent 等于2，cur等于1
左单旋旋转步骤：
subRL变成parent的右子树（subL和parent的关系，要注意🔥subL可能为空）
parent成为subR的左子树（parent和subLR的关系）
subR成为根节点（ppNode 和 subL关系，也要注意🔥parent是子树的根还是整棵树的根）
最后更新平衡因子
为什么要这样旋转？要符合二叉搜索树规则
subR的左子树的值本身就比parent的值要大，所以可以作为parent的右子树
parent及其左子树当中结点的值本身就比subR的值小，所以可以作为subR的左子树
平衡因子更新：
可以看见，左单旋后树的高度就平衡了，也就无需继续向上更新平衡因子了
代码实现如下：（详细注释）
void RotateL(Node* parent) { //三叉链 Node* subR = parent->_right; Node* subLR = subR->_left; Node* ppNode = parent->_parent; //subR 和 parent之间的关系 subR->_left = parent; parent->_parent = subR; //subRL 和 parent之间的关系 subRL = parent->_right; if (subRL) subRL->parent = parent; //ppNode 和 subR的关系 if (ppNode == nullptr) { _root = subR; subR->_parent = nullptr;//没有父节点，所以为空 } else { if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } //更新平衡因子 subR->_bf = parent->_bf = 0; }
🥑右单旋（和左单旋高度相似）
新节点插入较高左子树的左侧—左左：右单旋
动图演示：
抽象图过程解析：
右单旋旋转步骤：
与左单旋雷同，看上面就行
同样也要满足二叉搜索树的性质：也是和左单旋雷同，看上面就行
平衡因子更新如下：
同样右单旋后，parent的平衡因子为0，左右子树高度相等，也就无需继续往上更新平衡因子了
话不多说上代码：
//右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode = parent->_parent; //subL 和 parent的关系 subL->_right = parent; parent->_parent = subL; //subLR 和 parent之间的关系 parent->_left = subLR; if (subLR) subLR->_parent = parent; //ppNode 和 subL的关系 if (ppNode == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left == subL; } else { ppNode->_right == subL; } subL->_parent = ppNode; } //更新平衡因子 subL->_bf = parent->_bf = 0; }
🔥左右单旋
新节点插入较高左子树的右侧—左右：先左单旋再右单旋、
动图演示：
在b树或者c树中新增节点，均会引发左右双旋
旋转示意图如下：
1、插入新节点
2、以30为旋转点进行左单旋
3、以90为旋转点进行右单旋
左右单旋的步骤如下：
以subL为节点左单旋
以parent为节点右单旋
更新平衡因子（这才是重点）
左右双旋后满足二叉搜索树的性质：
实际上就是把subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根（看图理解）
subLR左子树的节点值比subL的值大，所以可以作为subL的右子树
subLR右子树的节点值比parent的值小，因此可以作为parent的左子树
前两个步骤之后，subL以及子树的值，和parent的值均符合，所以可以当subLR的左右子树
重点来了：（以subLR为突破口）
左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：
当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0
当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0
当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0
经过左右双旋后，即树的高度没有发生变化，所以无需继续往上更新平衡因子
话不多说，代码实现一下吧：
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; //subL节点左单旋 RotateL(subL); //parent节点进行右单旋 RotateR(parent); //更新平衡因子 if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == -1) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if(bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false);//旋转前的平衡因子就出错了 } }
🔥右左单旋
动图演示：
旋转图演示过程：
1、插入新节点
2、以subR的节点进行右单旋
3、以parent的节点进行右单旋
旋转步骤和左右双旋雷同
重点来了：（以subRL为突破口）
左右双旋后，平衡因子的更新随着subRL 原始平衡因子的不同分为三种情况分别对应subRL = 0、1、2情况，此处就不多赘述了，详细可以浏览左右双旋的，情况一样
代码实现
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; //subR右单旋 RotateR(subR); //parent进行左单旋 RotateL(parent); if (bf == 1) { subRL->_bf = 0; subR->_bf = 0; parent->_bf = -1; } else if (bf == -1) { subRL->_bf = 0; subR->_bf = 1; parent->_bf = 0; } else if (bf == 0) { subRL->_bf = 0; subR->_bf = 0; parent->_bf = 0; } else { assert(false); } }
五. 验证AVL树
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确
先验证是否为二叉搜索树
void _InOrder(Node* root) { if (root == nullptr) { return; _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); }
但中序遍历只能代表是二叉搜索树，不能代表是AVL树，为此还需要验证二叉树的平衡性，查平衡因子有一种监守自盗的感觉，因为平衡因子我们刚修改完，所以我们去查高度俩判断！
如果是空树，证明平衡，是AVL树
根高度差不大于2，并且递归子树的高度差都不大于2，即是AVL树
特殊情况，平衡因子和该点的高度差对不上，要判断一下
//是否平衡 bool IsBalance(Node* root) { if (root == nullptr) { return true; } int leftHT = Height(root->_left); int rightHT = Height(root->_right); int diff = rightHT - leftHT; if (diff ！ = root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } //小于2就为真 并且递归调用子树判断是否平衡 return abs(diff) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } //后序查找 int Height(Node* root) { if (root == nullptr) return 0; int leftHT = Height(root->_left); int rightHT = Height(root->_right); return max(leftHT, rightHT) + 1; }
六. AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 l o g 2 ( N ) log_2 (N) log 2 (N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合
