【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解（一）https://developer.aliyun.com/article/1617411
3.3 双旋解决问题
如果出现了这种if (parent->_bf == 2 || cur->_bf == -1), if (parent->_bf == -2 || cur->_bf == 1)普通单旋是不能解决问题的，需要使用到双旋。
如果使用单旋的话是没有多大作用的，做无用功。我们使用单旋处理的情况是一边独高，而不是那边高，这边高。对此可以先对内部旋转变成单独一边高，再使用单旋进行调整AVL树。
3.3.1 新节点插入较高左子树的右侧–左右:先左单旋再右单旋
场景:parent->_bf == -2 && cur->_bf == 1
这里可以直接复用实现好单旋的接口，但是需要对平衡因子进行调整，这里平衡因子可以通过结论直接修改。
3.3.2 根据结论修改AVL树节点平衡因子
通过图中对于不同情况的分析，对于修改平衡因子的结果是根据SubLR平衡因子特殊值决定的。b、c分别给谁，会影响平衡因子的分配。
3.3.3 新节点插入较高右子树的左侧—右左：先右单旋再左单旋
场景:parent->_bf == 2 && cur->_bf == -1
这里还是需要根据60这块的平衡因子去判断的，b c分别给谁，会影响平衡因子的分配。左边新增两次旋转给到右边，右边新增两次旋转给到左边，通过结论最后修改平衡因子。
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); subRL->_bf = 0; if (bf == 1) { subR->_bf = 0; parent->_bf = -1; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; } else { parent->_bf = 0; subR->_bf = 0; } } void RotateLR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; int _bf = SubLR->_bf; RotateL(parent->_left); RotateR(parent); if (_bf == 0) { parent->_bf = 0; SubL->_bf = 0; SubLR->_bf = 0; } else if (_bf == 1) { parent->_bf = 0; SubL->_bf = -1; SubLR->_bf = 0; } else if (_bf == -1) { parent->_bf = 1; SubL->_bf = 0; SubLR->_bf = 0; } else { assert(false); } }
3.3.4 小总结
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑 ：
- pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
- 当pSubR的平衡因子为1时，执行左单旋
- 当pSubR的平衡因子为-1时，执行右左双旋
- pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
- 当pSubL的平衡因子为-1是，执行右单旋
- 当pSubL的平衡因子为1时，执行左右双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新
四、AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分为两步:验证是否为二叉搜索树，验证是否为平衡树
4.1 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
void InOder() { _InOder(_root); cout << endl; } private: void _InOder(Node* _root) { if (_root == nullptr) { return; } InOder(_root->_left); cout << _root->_kv.first << " " << _root->_kv.second << endl; InOder(_root->_right); }
这里将中序遍历实现逻辑封装到私有成员函数中隐藏它的具体实现细节，使得外部用户无法直接访问该函数，提高了代码的安全性和可维护性，符合面向对象编程的封装性原则。这里外部访问中序遍历接口，只是传递了节点指针的副本，而不修改任何节指针的实际值。
4.2 验证其为平衡树
规则:
- 每个节点子树高度差的绝对值不超过1(注意节点种种那个如果没有平衡因子)
- 节点的平衡因子是否计算正确
bool IsBalance() { return _IsBalance(_root); } int Height() { return _Height(_root); } int Size() { return _Size(_root); } private: int _Size(Node* root) { return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1; } int _Height(Node* root) { if (root == nullptr) return 0; return max(_Height(root->_left), _Height(root->_right)) + 1; } bool _IsBalance(Node* root) { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); // 不平衡 if (abs(leftHeight - rightHeight) >= 2) { cout << root->_kv.first << endl; return false; } // 顺便检查一下平衡因子是否正确 if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << endl; return false; } return _IsBalance(root->_left) && _IsBalance(root->_right); } void _InOder(Node* _root) { if (_root == nullptr) { return; } InOder(_root->_left); cout << _root->_kv.first << " " << _root->_kv.second << endl; InOder(_root->_right); }
五、AVL树的删除(了解 )
因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置 ，这里调正平衡因子的逻辑就需要反过来，同时参考下二叉搜索树的删除操作。
六、AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(log^n^)`。但是如果要对AVL树做一些结构修改的操作，性能非常低下。
插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合
补充调式小技巧:
void TestAVLTree1() { //int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; AVLTree<int, int> t1; for (auto e : a) { /*if (e == 4) { int i = 0; }*/ // 1、先看是插入谁导致出现的问题 // 2、打条件断点，画出插入前的树 // 3、单步跟踪，对比图一一分析细节原因 t1.Insert({e,e}); cout <<"Insert:"<< e<<"->"<< t1.IsBalance() << endl; } t1.InOrder(); cout << t1.IsBalance() << endl; }
【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解（三）https://developer.aliyun.com/article/1617413
