②左单旋
新节点插入到较高右子树的右侧，即右右-----左单旋
插入新节点前，AVL树是平衡的，新节点插入到20的右子树，那么20的右子树增加了一层，导致以10为根的二叉树不平衡。为了让10平衡，只能让10的右子树的高度减小一层，并把20的左子树的高度增加一层。
因此，要把20的右子树往上提，把10转下来，因为10比20小，只能把10放在20的左子树，20的左子树比20小，比10大，因此只能把20的左子树放在10的右子树。再更新节点平衡因子。
抽象图：
需要考虑的情况：
（1）20的左孩子可能存在，也可能不存在
（2）10可能是根节点，也可能是子树；如果是根节点，旋转后，要更新根节点。如果是子树，可能是左子树也可能是右子树，就把10原来的父亲的左或右指向20。
1. void RotateL(Node* parent) 2. { 3. Node* subR = parent->_right; 4. Node* subRL = nullptr; 5. 6. if (subR) 7. { 8. subRL = subR->_left; 9. } 10. 11. //1.右子树的左子树变我的右子树 12. parent->_right = subRL; 13. 14. if (subRL) 15. { 16. subRL->_parent = parent; 17. } 18. 19. //2.右子树变父亲 20. subR->_left = parent; 21. Node* parentParent = parent->_parent; 22. parent->_parent = subR; 23. 24. if (parent == _root)//parent是根 25. { 26. _root = parent; 27. _root->_parent = nullptr; 28. } 29. else//parent不是根，是子树 30. { 31. if (parentParent->_left == parent) 32. { 33. //parent是自己父亲的左子树,将subR作为parent父亲的左孩子 34. parentParent->_left = subR; 35. } 36. else 37. { 38. //parent是自己父亲的右子树,将subR作为parent父亲的右孩子 39. parentParent->_right = subR; 40. } 41. 42. //subR的父亲就是parent的父亲 43. subR->_parent = parentParent; 44. } 45. 46. //更新平衡因子 47. subR->_bf = parent->_bf = 0; 48. }
具象图：
h=0的情况：
10变成20的左子树，20的左子树为空，不考虑
h=1的情况：
10变成20的左子树，20的左子树变成10的右子树
h=2的情况：
10变成20的左子树，20的左子树变成10的右子树
③左右双旋
新节点插入较高左子树的右侧---左右：先左单旋再右单旋
插入新节点前，AVL树是平衡的，新节点插入到20的左子树，那么20的左子树增加了一层，导致以30为根的二叉树不平衡。为了让30平衡，只能让30的左子树的高度减小一层。
现在30左子树的高度是h+1，但是现在不能把10进行右单旋，因为要把10右单旋，那么20和30都必须处于10的右子树，这办不到。因此要分为两步：
（1）先把10左单旋
（2）再把20右单旋
1. void RotateLR(Node* parent) 2. { 3. Node* subL = parent->_left; 4. Node* subLR = subL->_right; 5. int bf = 0; 6. 7. if (subLR) 8. { 9. bf = subLR->_bf; 10. } 11. 12. 13. RotateL(parent->_left); 14. RotateR(parent); 15. 16. //平衡因子调节还需要分析 17. if (bf == -1) 18. { 19. subL->_bf = 0; 20. parent->_bf = 1; 21. subLR->_bf = 0; 22. } 23. else if (bf == 1) 24. { 25. parent->_bf = 0; 26. subL->_bf = -1; 27. subLR->_bf = 0; 28. } 29. else if (bf == 0) 30. { 31. parent->_bf = 0; 32. subL->_bf = 0; 33. subLR->_bf = 0; 34. } 35. else 36. { 37. assert(false); 38. } 39. }
④右左双旋
新节点插入较高右子树的左侧---右左：先右单旋再左单旋
插入新节点前，AVL树是平衡的，新节点插入到30的右子树，那么30的右子树增加了一层，导致以10为根的二叉树不平衡。为了让10平衡，只能让10的右子树的高度减小一层。
现在10右子树的高度是h+1，但是现在不能把30进行左单旋，因为要把30左单旋，那么10和20都必须处于30的左子树，这办不到。因此要分为两步：
（1）先把20右单旋
（2）再把10左单旋
1. void RotateRL(Node* parent) 2. { 3. Node* subR = parent->_right; 4. Node* subRL = subR->_left; 5. int bf = 0; 6. 7. if (subRL) 8. { 9. bf = subRL->_bf; 10. } 11. 12. 13. //先右旋再左旋 14. RotateR(parent->_right); 15. RotateL(parent); 16. 17. //平衡因子调节还需要具体分析 18. if (bf == 1) 19. { 20. parent->_bf = -1; 21. subR->_bf = 0; 22. subRL->_bf = 0; 23. } 24. else if (bf == -1) 25. { 26. parent->_bf = 0; 27. subR->_bf = 1; 28. subRL->_bf = 0; 29. } 30. else if (bf == 0) 31. { 32. parent->_bf = 0; 33. subR->_bf = 0; 34. subRL->_bf = 0; 35. } 36. else 37. { 38. assert(false); 39. } 40. }
四、AVL树查找
查找比较简单：
（1）如果key比当前节点大，那就继续向右查找；
（2）如果key比当前节点小，那就继续向左查找；
（3）如果key恰好等于当前节点，找到了
1. Node* Find(const K& key) 2. { 3. Node* cur = _root; 4. while (cur) 5. { 6. if (cur.first < key)//比当前节点大，向右查找 7. { 8. cur = cur->_right; 9. } 10. else if (cur.first > key)//比当前节点小，向左查找 11. { 12. cur = cur->_left; 13. } 14. else//等于当前节点，找到了 15. { 16. return cur; 17. } 18. } 19. return nullptr; 20. }
五、AVL树高度
计算树高度肯定要递归计算：
（1）计算左右子树的高度
（2）谁的高度大，那AVL树的高度就为较高子树的高度+1
1. //求树的高度 2. int Height(Node* root) 3. { 4. if (root == nullptr) 5. { 6. return 0; 7. } 8. 9. int leftHeight = Height(root->_left); 10. int rightHeight = Height(root->_right); 11. 12. return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; 13. }
六、判断是否为AVL树
检查树是否是AVL树：
（1）获取左右子树高度
（2）根据左右子树高度计算平衡因子
（3）当平衡因子<=2 || -2时就是平衡的
1. bool _IsBanlance(Node* root) 2. { 3. if (root == nullptr) 4. { 5. return true; 6. } 7. 8. int leftHeight = Height(root->_left); 9. int rightHeight = Height(root->_right); 10. 11. //检查平衡因子是否正确 12. if (rightHeight - leftHeight != root->_bf) 13. { 14. cout << "平衡因子异常：" << root->_kv.first << endl; 15. return false; 16. } 17. 18. return abs(rightHeight - leftHeight) < 2 19. && _IsBanlance(root->_left) 20. && _IsBanlance(root->_right); 21. } 22. 23. //判断是否是AVL树 24. bool IsAVLTree() 25. { 26. return _IsBanlance(_root); 27. }
七、AVL树遍历
遍历也很简单：递归遍历左子树和右子树即可
1. void _InOrder(Node* root) 2. { 3. if (root == nullptr) 4. { 5. return; 6. } 7. 8. _InOrder(root->_left); 9. cout << root->_kv.first << ":" << root->_kv.second << endl; 10. _InOrder(root->_right); 11. } 12. 13. void InOrder() 14. { 15. _InOrder(_root); 16. }
八、时间复杂度
AVL树的操作时，需要找到位置，因此时间复杂度为高度次，即O(
) 。
