5、总结
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑：
pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
当SubR的平衡因子为1时，执行左单旋
当SubR的平衡因子为-1时，执行右左双旋
pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
当SubL的平衡因子为-1是，执行右单旋
当SubL的平衡因子为1时，执行左右双旋
从视角上来看，当旋转相关结点成直线，则进行单旋；当旋转相关结点成折线，则进行双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新
五、AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制
- 要验证AVL树可以分两步：
- 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
- 实现代码：
void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " : " << root->_kv.second << endl; _InOrder(root->_right); }
- 验证其为平衡树
每个结点子树高度差的绝对值不超过1(注意结点中如果没有平衡因子)以及结点的平衡因子是否计算正确
- 实现代码：
//验证pRoot是否为有效的AVL树 bool _IsAVLTree(Node* root) { //空树 if (root == nullptr) return true; //比较高度 int heightL = _Height(root->_left); int heightR = _Height(root->_right); //检查平衡因子是否有误 if (heightR - heightL != root->_bf) { cout << "平衡因子错误：" << root->_kv.first << endl; return false; } return abs(heightR - heightL) < 2 && _IsAVLTree(root->_left) && _IsAVLTree(root->_right);//递归检查左右子树 } //高度 size_t _Height(Node* root) { //空节点 if (root == nullptr) return 0; size_t left = _Height(root->_left); size_t right = _Height(root->_right); return left > right ? left + 1 : right + 1; }
六、AVL树的性能
分析：
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度logN
但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置
总结：
如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合
