1. AVL树的概念
前一篇对map / multimap / set / multiset进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。
二叉搜索树虽然可以提高我们查找数据的效率，但如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的。
因此，两位俄罗斯的数学家G.M.A delson-Velskii和E.M.Landis在1962年发明了解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。
AVL树可以是一棵空树，也可以是具有以下性质的一棵二叉搜索树：
树的左右子树都是AVL树。
树的左右子树高度之差（简称平衡因子）的绝对值不超过1（-1 / 0 / 1）。
如果一棵二叉搜索树的高度是平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度也是O(logN)。注意： 这里所说的二叉搜索树的高度是平衡的是指，树中每个结点左右子树高度之差的绝对值不超过1，因为只有满二叉树才能做到每个结点左右子树高度之差均为0。
2. AVL树结点和树的定义
下面来模拟实现一下AVL树，直接实现KV模型的AVL树，为了方便后续的操作，这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子，（右子树高度-左子树高度）。
除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，于是将新构造结点的平衡因子初始设置为0即可。（平衡因子并不是AVL树所必须的，这里只是其中一种实现方法）
AVLTree.h：
#pragma once #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; // balance factor 平衡因子 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; protected: Node* _root = nullptr; // 给缺省值直接在初始化列表初始化 };
3. AVL树的插入（未包含旋转）
VL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。
那么AVL树的插入过程可以分为两步：
① 按照二叉搜索树的方式插入新节点
与根结点比较如果比根大就往右子树插入，如果比根小就往左子树插入，
直到走到合适的位置就插入，由于这里是三叉链所以需要处理结点之间的关联关系
② 调整节点的平衡因子
当左右子树的高度发生了变化，那么就需要对父亲及祖先路径上的所有结点的平衡因子进行调整
插入结点后需要倒着往上更新平衡因子，更新规则如下：
1. 新增结点在parent的右边，parent的平衡因子+ +。
2. 新增结点在parent的左边，parent的平衡因子− −。
每更新完一个结点的平衡因子后，都需要进行以下判断：
如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了。
如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子。
如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，
需要进行旋转处理。
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) // 找要插入的位置 { if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->right; } else { return false; } } cur = new Node(kv); if (kv.first < parent->_kv.first) // 插入要插入的位置 { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; // 三叉链多一步 while (parent) // 控制平衡, 更新平衡因子, 如果平衡因子不对, 就要旋转 { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0) { break; } else if (abs(parent->_bf) == 1) // 往上更新 { parent = parent->_parent; cur = cur->_parent; } else if (abs(parent->_bf) == 2) // 不平衡了，需旋转 { // 后面写 } else // 理论不可能走到这，除非之前就错了 { assert(false); // 报个错 } } return true; }
4. AVL树的旋转
若是在更新平衡因子的过程当中，出现了平衡因子为-2/2的结点，这时需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行以下分析：
当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。
理由如下：
若cur的平衡因子是0，那么cur一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新。
而cur是新增结点的话，其父结点的平衡因子更新后一定是-1/0/1，而不可能是-2/2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：
其父结点是一个左右子树均为空的叶子结点，其平衡因子是0，新增结点插入后其平衡因子更新为-1/1。
其父结点是一个左子树或右子树为空的结点，其平衡因子是-1/1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。
综上所述，当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。
根据此结论，我们可以将旋转处理分为以下四类：
- 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
- 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
- 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。
- 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。
并且，在进行旋转处理后就无需继续往上更新平衡因子了，因为旋转后树的高度变为插入之前了，即树的高度没有发生变化，也就不会影响其父结点的平衡因子了。具体原因请看下面的旋转讲解。
4.1 右右_左单旋
可以看到，经过左单旋后，树的高度变为插入之前了，即树的高度没有发生变化，
所以左单旋后无需继续往上更新平衡因子。
左单旋的步骤如下：
- 让subR的左子树作为parent的右子树。
- 让parent作为subR的左子树。
- 让subR作为整个子树的根。
- 更新平衡因子。
左单旋后满足二叉搜索树的性质：
- subR的左子树当中结点的值本身就比parent的值大，因此可以作为parent的右子树。
- parent及其左子树当中结点的值本身就比subR的值小，因此可以作为subR的左子树。
左单旋代码：
void RotateL(Node* parent) { Node* subR = parent->_right; // 动了三个标记了的结点，共更新六个指针，这更新两个指针 Node* subRL = subR->_left; parent->_right = subRL; if (subRL) // subRL不为空才更新 { subRL->_parent = parent; } Node* ppNode = parent->_parent; // 记录parent的parent，防止parent是一颗子树的头结点 subR->_left = parent; // 再更新两个指针 parent->_parent = subR; if (_root == parent) // 最后更新两个指针 { _root = subR; subR->_parent = nullptr; } else // parent是一颗子树的头结点 { if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } subR->_bf = parent->_bf = 0; // 更新平衡因子 }
4.2 左左_右单旋
经过右单旋后，树的高度变为插入之前了，即树的高度没有发生变化，
所以右单旋后无需继续往上更新平衡因子。
右单旋的步骤如下：
- 让subL的右子树作为parent的左子树。
- 让parent作为subL的右子树。
- 让subL作为整个子树的根。
- 更新平衡因子。
右单旋后满足二叉搜索树的性质：
- subL的右子树当中结点的值本身就比parent的值小，因此可以作为parent的左子树。
- parent及其右子树当中结点的值本身就比subL的值大，因此可以作为subL的右子树。
右单旋代码：
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 (_root == parent) // 最后更新两个结点 { _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; // 更新平衡因子 }
4.3 左右双旋
左右双旋步骤示意图
1、插入新结点。这里可能插入到b / c下面，还可能h等于0，插入到60下面
（以上三种插入的后两步都是一样的，只是最后平衡因子不同：）
2、以30为旋转点进行左单旋。
3、以90为旋转点进行右单旋。
左右双旋的步骤如下：
- 以subL为旋转点进行左单旋。（前两步都可以复用上面的代码）
- 以parent为旋转点进行右单旋。
- 更新平衡因子。（左右双旋复杂的地方）
左右双旋后满足二叉搜索树的性质：
左右双旋后，实际上就是让subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根（结合图理解）。
1. subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。
2. subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。
3. 经过步骤1/2后，subL及其子树当中结点的值都就比subLR的值小，而parent及其子树当中结点的值都就比subLR的值大，因此它们可以分别作为subLR的左右子树。
观察发现，左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：
1、当subLR原始平衡因子是-1时，左右双旋后subLR，parent、subL的平衡因子分别更新为0、1、0。
2、当subLR原始平衡因子是1时，左右双旋后subLR、parent、subL的平衡因子分别更新为0、0、-1。
3、当subLR原始平衡因子是0时，左右双旋后subLR、parent、subL的平衡因子分别更新为0、0、0。
可以看到，经过左右双旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左右双旋后无需继续往上更新平衡因子。
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)（下）：https://developer.aliyun.com/article/1522271?spm=a2c6h.13148508.setting.21.50c04f0edmwqiI
