前面我们对 map / multimap / set / multiset 进行了简单的介绍，可以发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的。
但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成 O(N)，因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用 平衡树 来实现。
一、AVL树（高度平衡二叉搜索树）
1、概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
- 最优情况下，有 n 个结点的二叉搜索树为完全二叉树，查找效率为：O(log₂N)。
- 最差情况下，有 n 个结点的二叉搜索树退化为单支树，查找效率为：O(N)。
因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中 插入新结点 后，如果能 保证每个结点的左右子树高度之差的绝对值不超过 1 （需要对树中的结点进行调整），即可降低树的高度，从而减少平均 搜索长度。
一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是 AVL 树。
- 左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1/0/1）。
如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log₂n)，搜索时间复杂度 O(log₂n)。
为什么左右子树高度差不规定成0呢？
因为在 2、4 等节点数的情况下，不可能做到左右高度相等的情况。
2、AVL 树节点的定义
AVL 树节点的定义：
AVL 树节点是一个 三叉链结构，除了 指向左右孩子的指针，还有一个 指向其父亲的指针，数据域是键值对，即 pair 对象，还引入了平衡因子，用来判断是否需要进行平衡操作。
// AVL树节点的定义（KV模型） template<class K, class V> struct AVLTreeNode { AVLTreeNode<T>* _left; // 该节点的左孩子 AVLTreeNode<T>* _right; // 该节点的右孩子 AVLTreeNode<T>* _parent; // 该节点的双亲指针 pair<K, V> _kv; // 键值对 int _bf; // 该节点的平衡因子(balance factor) = 右子树高度-左子树高度 // 构造函数 AVLTreeNode(const pari<K, V>& kv) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} }; // AVL树的定义（KV模型） template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: // 成员函数 private: Node* _root; }
3、AVL树的插入
AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点到 AVL 树中。
- 新节点插入后，AVL 树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了 AVL 树的平衡（控制树的平衡（旋转操作））。
// 插入节点 bool Insert(const pair<K, V>& kv) { // 如果树为空，则直接插入节点 if (_root == nullptr) { _root = new Node(kv); return true; } // 如果树不为空，找到适合插入节点的空位置 Node* parent = nullptr; // 记录当前节点的父亲 Node* cur = _root; // 记录当前节点 while (cur) // while循环结束，说明找到适合插入节点的空位置了 { if(kv.first > cur->_kv.first) // 插入节点键值k大于当前节点 { parent = cur; cur = cur->_right; } else if(kv.first < cur->_kv.first) // 插入节点键值k小于当前节点 { parent = cur; cur = cur->_left; } else // 插入节点键值k等于当前节点 { return false; } } // 插入新节点 cur = new Node(kv); // 申请新节点 // 判断当前节点是父亲的左孩子还是右孩子 if (cur->_kv.first > parent->_kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; // 控制平衡 // 1、更新平衡因子 // ... return true; }
⚪更新平衡因子
（1）插入新节点cur 插入后，parent 的平衡因子一定需要调整，在插入之前，parent 的平衡因子分为三种情况：-1，0，1，分以下两种情况：
- 如果 cur 插入到 新节点父亲（parent） 的左侧，只需给 父亲（parent） 的平衡因子--（
_bf--）即可。- 如果 cur 插入到 新节点父亲（parent） 的右侧，只需给 父亲（parent） 的平衡因子++（
_bf++）即可。
（2）新节点父亲的平衡因子更新以后，又会分为 3 种情况：
此时：parent的平衡因子可能有三种情况：0，正负 1， 正负 2。
- 如果更新以后，parent 的平衡因子是 0（则说明插入之前 parent 的平衡因子之前一定为 1/-1），说明父亲所在子树高度没变（因为把矮的那边给填补上了），此时满足 AVL 树的性质，插入成功，不需要继续往上更新。
- 如果更新以后，parent 的平衡因子是 1/-1（则说明插入之前 parent 的平衡因子 一定为 0），说明父亲所在子树高度增加，需要继续往上更新。（最坏情况：往上一直更新到根节点）。
- 如果更新以后，parent 的平衡因子是 2/-2，说明父亲所在子树出现了不平衡，需要对其进行旋转处理。
// 插入节点 bool Insert(const pair<K, V>& kv) { // 控制平衡 // 1、更新平衡因子 while (parent) // 最坏情况：更新到根节点 { // 更新双亲的平衡因子 if (cur == parent->_left) // 新节点插入在父亲的左边 parent->_bf--; else // 新节点插入在父亲的右边 parent->_bf++; // 更新后检测双亲的平衡因子 if (0 == pParent->_bf) { break; } //else if (1 == parent->_bf || -1 == parent->_bf) else if (abs(parent->_bf) == 1) // 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整 { cur = parent; parent = cur->_parent; } else if (abs(parent->_bf) == 2) // 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以parent为根的树进行旋转处理 { // 1、父节点的右边高，左边低，需要往左旋 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); // 左单旋 } // 2、父节点的左边高，右边低，需要往右旋 else if ((parent->_bf == -2 && cur->_bf == -1)) { RotateR(parent); // 右单旋 } // 3、父节点的左边高，且父节点左孩子的右边高 else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); // 左右双旋 } // 4、父节点的右边高，且父节点右孩子的左边高 else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); // 右左双旋 } break; // 旋转完成，树已平衡，退出循环 } // 除了上述3种情况，平衡因子不可能有其它的值，报错处理 else { assert(false); } } return true; }
4、AVL树的旋转
如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。
根据节点插入位置的不同，AVL 树的旋转分为四种：
旋转的本质：在遵循二叉搜索树的规则下，让左右均衡，降低整棵树的高度。
该进行哪种旋转操作？
引发旋转的路径是直线就是单旋，如果是折线就是双旋。
注意：此处看到的树，可能是一颗完整的树，也可能是一颗子树。
（1）新节点插入较高左子树的左侧 —— 左左：右单旋
将新的节点插入到了 parent 左孩子的左子树上，导致的不平衡的情况。
上图在插入前，AVL 树是平衡的，新节点插入到 30 的左子树（注意：此处不是左孩子）中，30 左子树增加了一层，导致以 60 为根的二叉树不平衡，要让 60 平衡，只能将 60 左子树的高度减少一层，右子树增加一层，即将左子树往上提，这样 60 转下来，因为 60 比 30 大，只能将其放在 30 的右子树，而如果 30 有右子树，右子树根的值一定大于 30，小于 60，只能将其放在 60 的左子树，旋转完成后，更新节点的平衡因子即可。
【引发右单旋的条件】
- 父亲左边高，右边低，所以要让父亲往右旋。
- parent 的平衡因子为 -2，parent 左孩子平衡因子为 -1，观察发现，平衡因子都是负数，说明是左边高，也说明了引发旋转的路径是一条直线，所以我们要右旋操作。
【右单旋操作】
1、让 subL 的右子树 subLR 成为 parent 的左子树（因为 subLR 的右子树根节点值 > 30，< 60）。
2、让 parent 成为 subL 的右子树（因为 60 > 30）。
3、让 subL 变成这个子树的根。这一步操作前需要先判断下：parent 是根节点，还是一个普通子树
- 如果是根节点，旋转完成后，则更新 subL 为新的根节点。
- 如果是普通子树（可能是某个节点的左子树，也可能是右子树，这里作一个判断），然后更新 subL 为这个子树的根节点。
4、根据树的结构，更新 parent 和 subL 的平衡因子为 0。
在旋转过程中，更新双亲指针的指向，有以下几种情况需要考虑：
- 30 节点的右孩子可能存在，也可能不存在。（subL 的右子树 subLR 可能存在，也可能为空。当不为空时才更新 subL 右子树 subLR 的双亲指针指向）。
- 60 可能是根节点，也可能是子树。（旋转完成后，subL 的双亲节点，可能是空，也可能是 parent 原先的父节点。所以在更新 subL 的双亲指针前需要判断下）。
依次调整 subLR、parent、subL 的位置和双亲指针的指向。
// 右单旋 void _RotateR(Node* parent) { Node* subL = parent->_left; // subL : parent的左孩子 Node* subLR = subL->_right; // subLR : parent左孩子的右孩子 // 旋转完成之后，让subL的右子树subLR成为parent的左子树 parent->_left = subLR; // 如果subLR存在，更新subLR的双亲指针，指向parent if (subLR) { subLR->_parent = parent; } // 因为parent可能是棵子树，因此在更新其双亲前必须先保存parent的父节点 Node* ppNode = parent->_parent; // 让parent成为subL的右子树 subL->_right = parent; // 更新parent的双亲指针，指向subL parent->_parent = subL; // 如果parent是根节点，根新指向根节点的指针 if (_root == parent) { _root = subL; // 更新subL为新的根 subL->_parent = nullptr; // 更新subL的双亲指针，指向空 } // parent不是根节点，就是一个普通子树 else { // 判断parent原先是左孩子还是右孩子 if (ppNode->_left == parent) { ppNode->_left = subL; // parent原先的双亲节点接管subL，subL为这个子树的根 } else { ppNode->_right = subL; } subL->_parent = ppNode; // 更新subL的双亲指针 } // 根据调整后的结构更新部分节点的平衡因子 parent->_bf = pSubL->_bf = 0; }
【C++】map&set的底层结构 -- AVL树（高度平衡二叉搜索树）（下）https://developer.aliyun.com/article/1515239?spm=a2c6h.13148508.setting.28.11104f0e63xoTy
