【C++】map&set的底层结构 -- AVL树（高度平衡二叉搜索树）（上）https://developer.aliyun.com/article/1515237?spm=a2c6h.13148508.setting.29.11104f0e63xoTy
（2）新节点插入较高右子树的右侧 —— 右右：左单旋
【引发左单旋的条件】
- 父亲右边高，左边低，所以要让父亲往左旋。
- parent 的平衡因子为 2，parent 左孩子平衡因子为 1，观察发现，平衡因子都是正数，说明是右边高，也说明了引发旋转的路径是一条直线，所以我们要右旋操作。
【右单旋操作】
1、让 subR 的左子树 subRL 成为 parent 的右子树（因为 subRL 的左子树根节点值 > 30，< 60）。
2、让 parent 成为 subR 的左子树（因为 30 < 60）。
3、让 subR 变成这个子树的根。这一步操作前需要先判断下：parent 是根节点，还是一个普通子树
- 如果是根节点，旋转完成后，则更新 subR 为新的根节点。
- 如果是普通子树（可能是某个节点的左子树，也可能是右子树，这里作一个判断），然后更新 subR 为这个子树的根节点。
4、根据树的结构，更新 parent 和 subR 的平衡因子为 0。
在旋转过程中，更新双亲指针的指向，有以下几种情况需要考虑：
- subR 的左子树 subRL 可能存在，也可能为空。（当不为空时才更新 subR 左子树 subRL 的双亲指针指向）。
- 旋转完成后，subR 的双亲节点，可能是空，也可能是 parent 原先的父节点。（所以更新 subR 的双亲指针前需要判断下）。
依次调整 subRL、parent、subR 的位置和双亲指针的指向。
// 左单旋 void treeRotateLeft(Node* parent) { Node* subR = parent->_right; // subR：父亲的右孩子 Node* subRL = subR->_left; // subRL：父亲的右孩子的左孩子（大于父亲，小于subR） // 让subRL成为父亲的右子树 parent->_right = subRL; // 如果subRL不为空 if (subRL) { subRL->_parent = parent; // 更新subRL双亲指针，指向parent } // 因为parent可能是棵子树，因此在更新其双亲前必须先保存parent的父节点 Node* ppNode = parent->_parent; // 让parent成为subR的左子树 subR->_left = parent; // 更新parent双亲指针的指向 parent->_parent = subR; // 判断parent是不是根节点 if (parent == _root) { _root = subR; // subR为新的根 subR->_parent = nullptr; // subR双亲指针指向空 } // 不是根节点，就是一个普通子树 else { // 判断parent原先是左孩子还是右孩子 if (ppNode->_left == parent) { ppNode->_left = subR; // parent原先的双亲节点接管subR，subR为这个子树的根 } else { ppNode->_right = subR; } subR->_parent = ppNode; // 更新subR的双亲指针 } // 根据树的结构，更新parent和subR的平衡因子 parent->_bf = subR->_bf = 0; }
（3）新节点插入较高左子树的右侧 —— 左右：先左单旋再右单旋（左右双旋）
将新的节点插入到了 parent 左孩子的右子树上，导致的不平衡的情况。
这时我们需要的是先对 parent 的右孩子进行一次左旋，再对 parent 进行一次右旋。
将双旋变成单旋后再旋转，即：先对 30 进行左单旋，然后再对 90 进行右单旋，旋转完成后再考虑平衡因子的更新。
旋转之前，60 的平衡因子可能是 -1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进行调整。
【h == 0】
【引发双旋的条件】
引发旋转的路径是直线就是单旋，如果是折线就是双旋。
parent 的平衡因子为 -2，parent 左孩子的平衡因子为 1，观察发现，平衡因子是一负一正，说明左孩子右边高，父亲左边高，也说明了引发旋转的路径是一条折线，所以我们要先对左孩子进行左旋操作，再对父亲进行右旋操作。
左右双旋操作后，根据树的结构，更新平衡因子时，需要注意：
插入新节点的位置不同，经过左右双旋后，得到树的结构也会有所不同，平衡因子也会有所不同，有以下三种情况：
- 新节点插入到了 parent 左孩子的右子树的左边。
- 新节点插入到了 parent 左孩子的右子树的右边。
- 新节点就是 parent 左孩子的右孩子。
这里可以观察到一个现象，根据这个现象就很好推出旋转后的平衡因子：
节点 60 的左右子树被分走了，左子树最终成为了节点 30 的右子树，右子树最终成了节点 90 的左子树。
void _RotateLR(PNode pParent) { Node* subL = parent->_left; // 记录parent的左孩子 Node* subLR = subL->_right; // 记录parent的左孩子的右孩子 // 旋转之前，因为插入新节点的位置不同，subLR的平衡因子可能是-1/0/1 int bf = subLR->_bf; // 记录subLR的平衡因子 // 先对parent的左孩子进行左单旋 RotateL(parent->_left); // 再对parent进行右单旋 RotateR(parent); // 旋转完成之后，根据情况对其他节点的平衡因子进行调整 subLR->_bf = 0; if (bf == -1) { parent->_bf = 1; subL->_bf = 0; } else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; } else if (bf == 0) { parent->_bf = 0; subL->_bf = 0; } else { assert(false); } }
（4）新节点插入较高右子树的左侧 —— 右左：先右单旋再左单旋（右左双旋）
将新的节点插入到了 parent 右孩子的左子树上，导致的不平衡的情况。
这时我们需要的是先对 parent 的右孩子进行一次右旋，再对 parent 进行一次左旋。
【h == 1】
【引发双旋的条件】
引发旋转的路径是直线就是单旋，如果是折线就是双旋。
parent 的平衡因子为 2， parent 右孩子平衡因子为 -1，观察发现，平衡因子是一正一负，说明右孩子左边高，父亲右边高，也说明了引发旋转的路径是一条折线，所以我们要先对右孩子进行右旋操作，再对父亲进行左旋操作。
左右双旋操作后，根据树的结构，更新平衡因子时，需要注意：
插入新节点的位置不同，经过右左双旋后，得到树的结构也会有所不同，平衡因子也会有所不同，有以下三种情况：
- 新节点插入到了 parent 右孩子的左子树的左边。
- 新节点插入到了 parent 右孩子的左子树的右边。
- 新节点就是 parent 右孩子的左孩子。
这里可以观察到一个现象，根据这个现象就很好推出旋转后的平衡因子：
节点 60 的左右子树被分走了，左子树 b 最终成了节点 30 的右子树，右子树 c 最终成了节点 90 的左子树。
// 右左双旋 void treeRotateRL(Node* parent) { Node* subR = parent->_right; // 记录parent的右孩子 Node* subRL = subR->_left; // 记录parent的右孩子的左孩子 // 旋转之前，因为插入新节点的位置不同，subRL的平衡因子可能为-1/0/1 int bf = subRL->_bf; // 记录subRL的平衡因子 RotateR(parent->_right); // 先对parent的右孩子进行右单旋 RotateL(parent); // 再对parent进行左单选 // 旋转完成之后，根据树的结构对其他节点的平衡因子进行调整 subRL->_bf = 0; if (bf == -1) { parent->_bf = 0; subR->_bf = 1; } else if (bf == 1) { parent->_bf = -1; subR->_bf = 0; } else if(bf == 0) { parent->_bf = 0; subR->_bf = 0; } else { assert(false); } }
【总结】
假如以 parent 为根的子树不平衡，即 parent 的平衡因子为 2/-2，分以下情况考虑：
1、parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 subR。
- 当 subR 的平衡因子为 1 时，执行左单旋。
- 当 subR 的平衡因子为 -1 时，执行右左双旋。
2、parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent 的左子树的根为 subL。
- 当 subL 的平衡因子为 -1 时，执行右单旋。
- 当 subL 的平衡因子为 1 时，执行左右双旋。
旋转完成后，原 parent 为根的子树个高度降低，已经平衡，不需要再向上更新。
5、AVL树的验证
AVL 树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证 AVL 树，可以分两步：
1、验证其为二叉搜索树
- 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。
2、验证其为平衡树
- 每个节点子树高度差的绝对值不超过 1（注意节点中如果没有平衡因子）。
- 节点的平衡因子是否计算正确。
（1）首先写一个计算当前树高度的函数
// 计算当前树的高度 int Height(Node* root) { // 当前树为空，则高度为0 if (root == nullptr) return 0; // 当前树的高度 = 左右子树中高度最大的那个加1 return max(Height(root->_left), Height(root->_right)) + 1; }
（2）检查AVL树是否平衡：【思路一】自顶向下的暴力解法
bool IsBalance1() { return _IsBalance(_root); } bool _IsBalance1(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); }
（3）检查AVL树是否平衡【思路二】自底向上的高效解法（动态规划，前一个子问题的解，能够用于后一个问题求解）
bool IsBalance2() { return _IsBalance2(_root) != -1; } int _IsBalance2(Node* root) { // 先判断当前树的左、右子树是否平衡，再判断当前树是否平衡 // 不平衡返回-1，平衡则返回当前树的高度 // 当前树为空，返回高度0 if (root == nullptr) return 0; // 当前树不为空，分别计算左右子树的高度 int leftHeight = _IsBalance2(root->_left); int rightHeight = _IsBalance2(root->_right); int diff = rightHT - leftHT; if (diff != root->_bf) // 检查当前树的平衡因子是否计算正确 { cout << "平衡因子异常:" << root->_kv.first << endl; } // 左子树高度等于-1、右子树高度等于-1、左右子树高度差的绝对值大于1，说明当前树不平衡 if (leftHeight == -1 || rightHeight == -1 || abs(diff) > 1) return -1; // 运行到这里来了，说明当前树是平衡的，返回当前树的高度 return max(leftHeight, rightHeight) + 1; }
（4）【思路三】
bool _IsBalanceTree3(Node* root) { // 空树也是AVL树 if (nullptr == root) return true; // 计算pRoot节点的平衡因子：即pRoot左右子树的高度差 int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); int diff = rightHeight - leftHeight; // 如果计算出的平衡因子与pRoot的平衡因子不相等，或者pRoot平衡因子的绝对值超过1，则一定不是AVL树 if (diff != root->_bf || (diff > 1 || diff < -1)) return false; // pRoot的左和右如果都是AVL树，则该树一定是AVL树 return _IsBalanceTree3(root->_left) && _IsBalanceTree3(root->_right); }
3、验证用例
- 常规场景 1：{16, 3, 7, 11, 9, 26, 18, 14, 15}
- 特殊场景 2：{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}
6、AVL树的删除（了解）
因为 AVL 树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。
7、AVL 树的性能
AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查询时高效的时间复杂度，即 O(logN)。
但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑 AVL 树，但一个结构经常修改，就不太适合。
