一、AVL树概念

1.二叉搜索树的缺点

map/multimap/set/multiset的底层都按照二叉搜索树实现，但是在【C++】-- 搜索二叉树一文中已经了解到二叉搜索树的缺点在于，假如向树中插入的元素有序或者接近有序时，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，相当于在顺序表中搜索元素，效率低下。所以map/multimap/set/multiset的底层结构对二叉搜索树做了处理，采用平衡树来实现。

2.AVL树的概念

如何避免二叉树搜索树会退化成单支树的缺点呢？

向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。为什么高度差的绝对值不超过1而不是0呢？因为如果高度差的绝对值不超过0，那么二叉树就变成满二叉树了，因此绝对值不能超过1。这就引入了平衡二叉树的概念：

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

(1)它的左右子树都是AVL树

(2)左右子树高度之差(简称平衡因子=右子树高度-左子树高度)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在，搜索时

间复杂度O（）。

二、AVL树定义

由于要实现AVL树的增删改查，所以定义AVL树的节点，就需要定义parent，否则插入节点时，不知道要链接到树里面哪个节点下面。

1.AVL树节点定义

节点定义：

1. #pragma once
2. #include<iostream>
3. using namespace std;
4. 
5. template<class K,class V>
6. class AVLTreeNode
7. {
8.  AVLTreeNode<K, V>* _left;//左子树
9.  AVLTreeNode<K, V>* _right;//右子树
10.   AVLTreeNode<K, V>* _parent;//父亲
11. 
12.   int _bf;//平衡因子
13. 
14.   pair<K, V> _kv;//节点
15. 
16.   AVLTreeNode(const pair<K, V>&, kv)
17.   {
18.     :_left(nullptr)
19.     ,_right(nullptr)
20.     ,_parent(nullptr)
21.     ,_bf(0)
22.     , _kv(kv)
23.   }
24.   {}
25. 
26. };

2.AVL树定义

1. template<class K,class V>
2. struct AVLTree
3. {
4.  typedef AVLTreeNode<K, V> Node;
5. public:
6.    //构造函数
7.  AVLTree()
8.    :_root(nullptr)
9.  {}
10. 
11.   void _Destroy(Node* root)
12.   {
13.     if (root == nullptr)
14.     {
15.       return;
16.     }
17.     _Destroy(root->_left);
18.     _Destroy(root->_right);
19. 
20.     delete root;
21.   }
22. 
23. //重载operator[]
24.   V& operator[](const K& key)
25.   {
26.     pair<Node*, bool> ret = Insert(make_pair(key, V()));
27.     return ret.first->_kv.second;
28.   }
29. 
30.   //析构函数
31.   ~AVLTree()
32.   {
33.     _Destroy(_root);
34.     _root = nullptr;
35.   }
36. 
37. private:
38.   Node* _root;
39. };

三、AVL树插入

1.插入节点

插入节点需要先判断树是否为空：

（1）若为空，让该节点作为根节点

（2）若不为空，分3种情况：

①key比当前节点小，向左走

②key比当前节点大，向右走

③相等，插入失败

如果没找到节点，那么需要插入新节点

1.  bool Insert(const pair<K, V>& kv)
2.  {
3.    //1.空树
4.    if (_root == nullptr)
5.    {
6.      _root = new Node(kv);
7.      return true;
8.    }
9. 
10.     //2.非空树
11.     Node* parent = _root, * cur = _root;
12.     while (cur)
13.     {
14.       if (cur->_kv.first > kv.first)//向左找
15.       {
16.         parent = cur;
17.         cur = cur->_left;
18.       }
19.       else if (cur->_kv.first < kv.first)//向右找
20.       {
21.         parent = cur;
22.         cur = cur->_right;
23.       }
24.       else//找到了
25.       {
26.         return false;
27.       }
28.     }
29. 
30.     //没找到，需要插入
31.     cur = new Node(kv);
32.     if (parent->_kv.first < cur->_kv.first)
33.     {
34.       parent->_right = cur;
35.       cur->_parent = parent;
36.     }
37.     else
38.     {
39.       parent->_left = cur;
40.       cur->_parent = parent;
41.     }
42. 
43.     return true;
44.   }

2.控制平衡

（1）更新平衡因子

一个节点的平衡因子是否需要更新，取决于它的左右子树的高度是否发生变化。插入一个节点，如果它的父亲的平衡因子需要更新，那么它所在这条路径的从父亲到根的所有节点的平衡因子都需要更新。因此

①如果新增节点是父亲的左子树，那么parent->_bf--

②如果新增节点是父亲的右子树，那么parent->_bf++

更新后：

a.如果parent->_bf=0，则停止更新

b.如果parent->_bf==1||-1，需要继续往上更新（说明以parent为根的子树高度变了，由0变成了1或-1，有可能导致parent的parent的平衡因子=2或=-2）

c.如果parent->_bf=2||-2已经不平衡了，那么需要旋转处理

1.    //控制平衡
2.    //1.更新平衡因子
3.    while (cur != root)
4.    {
5.      if (parent->_left == cur)//新节点插入到parent左孩子，parent的左子树变高了，平衡因子-1
6.      {
7.        parent->_bf--;
8.      }
9.      else
10.       {
11.         parent->_bf++;
12.       }
13. 
14. 
15.       if (parent->_bf == 0)
16.       {
17.         //已经平衡，停止更新
18.         break;
19.       }
20.       else if(parent->_bf == 1 || parent->_bf == -1)
21.       {
22.         //说明以parent为根的子树高度变了，由0变成了1或-1，有可能影响parent的parent的平衡因子，需要继续往上更新
23.         cur = parent;
24.         parent = parent->_parent;
25.       }
26.       else if (parent->_bf == 2 || parent->_bf == -2)
27.       {
28.         //已经出现了不平衡，需要旋转处理
29.         if (parent->_bf == -2)
30.         {
31.           if (cur->_bf == -1)
32.           {
33.             //右单旋
34.             RotateR(parent);
35.           }
36.         }
37.       }
38.       else
39.       {
40.         //插入新节点之前，树已经不平衡了
41.         assert(false);
42.       }
43.     }

（2）旋转

旋转处理有4种：右单旋、左单旋、右左单旋、左右单旋

①右单旋

将新节点插入到较高左子树的左侧，即左左-----右单旋

插入新节点前，AVL树是平衡的，新节点插入到10的左子树，那么10的左子树增加了一层，导致以20为根的二叉树不平衡。为了让20平衡，只能让20的左子树的高度减小一层，并把10的右子树的高度增加一层。

因此，要把10的左子树往上提，把20转下来，因为20比10大，只能把20放在10的右子树，10的右子树比10大，比20小，因此只能把10的右子树放在20的左子树。再更新节点平衡因子。

抽象图：

需要考虑的情况：

（1）10的右孩子可能存在，也可能不存在

（2）20可能是根节点，也可能是子树；如果是根节点，旋转后，要更新根节点。如果是子树，可能是左子树也可能是右子树，就把20原来的父亲的左或右指向10。

1.  void RotateR(Node* parent)
2.  {
3.    Node* subL = parent->_left;
4.    Node* subLR = nullptr;
5. 
6.    if (subL)
7.    {
8.      subLR = subL->_right;
9.    }
10.     //1.左子树的右子树变我的左子树
11.     parent->_left = subLR;
12. 
13.     if (subLR)
14.     {
15.       subLR->_parent = parent;
16.     }
17. 
18.     //左子树变父亲
19.     subL->_right = parent;
20.     Node* parentParent = parent->_parent;
21.     parent->_parent = subL;
22. 
23. 
24.     if (parent == _root)//parent是根
25.     {
26.       _root = subL;
27.       _root->_parent = nullptr;
28.     }
29.     else//parent不是根，是子树
30.     {
31.       if (parentParent->_left == parent)
32.       {
33.         //parent是自己父亲的左子树,将subL作为parent父亲的左孩子
34.         parentParent->_left = subL;
35.       }
36.       else
37.       {
38.         //parent是自己父亲的右子树,将subL作为parent父亲的右孩子
39.         parentParent->_right = subL;
40.       }
41. 
42.       //subL的父亲就是parent的父亲
43.       subL->_parent = parentParent;
44.     }
45. 
46.     //更新平衡因子
47.     subL->_bf = parent->_bf = 0;
48.   }

具象图：

h=0的情况：

20变成10的左子树，10的左子树为空，不用考虑

h=1的情况：

20变成10的右子树，10的右子树12变成20的左子树

h=2的情况：

20变成10的左子树，10的右子树12变成20的左子树

【C++】-- AVL树详解（一）