前面对map/multimap/set/multiset进行了简单的介绍，在其文档介绍中发现，这几个容器有个
共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中
插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此
map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现
目录
1. AVL树
1.1 概念
1.2 AVL树节点的定义
1.3 AVL树的插入（健康版）
1.4 AVL树的旋转（非健康版）
1. 右旋图解
右旋代码
2. 左旋图解
左旋代码
3. 右左双旋图解
右左双旋代码
4. 左右双旋图解
左右双旋代码
总结
1.5 AVL树的验证
1.5.1 二叉搜索树的验证
1.5.2 AVL树的验证
验证代码
1.6 AVL树的删除
1.7 AVL树的性能
1. AVL树
1.1 概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树。
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O(logN)，搜索时间复杂度O(logN)
1.2 AVL树节点的定义
AVL与红黑树中存放的数据都是pair<k,v>结构。
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;//左孩子AVLTreeNode<K, V>* _right;//右孩子AVLTreeNode<K, V>* _parent;//父亲pair<K, V> _kv;int _bf;//平衡因子，健康的平衡因子绝对值不大于1AVLTreeNode(const pair<K, V>& kv):_bf(0),_kv(kv), _left(nullptr), _right(nullptr),_parent(nullptr){}
};这里可以看到，AVL树的节点与平衡二叉树的节点区别在于AVL树节点有一个平衡因子的存在，也即1.1概念中所述。同时AVL树采用了三叉链结构，好处在于在对树进行操作时，不必额外存储节点的父亲。
1.3 AVL树的插入（健康版）
AVL树的插入规则与平衡二叉树一样，不过在插入时要兼顾平衡因子绝对值不大于1的规则，如果某节点的平衡因子绝对值大于1，则需要进行处理。
与平衡二叉树一样，在插入节点时需要先找到插入的位置，这里我们可以复刻平衡二叉树的代码。
插入之后需要对其平衡因子（后面简称bf）进行判断。
那么插入一个节点其bf应该怎么判断呢？
很简单，bf是以该节点为根的树左右子树高度差，我们可以规定，左边插入节点bf--，右边插入节点bf++，新增的节点bf当然是为0的。
请看上图，上图只是AVL树的具象图之一，但我们所讲的特性已经足够展示。
左边插入，bf--；右边插入，bf++。我们发现当bf等于0时，对树的影响终止，当bf等于1或-1时，影响会继续向上扩散。那么为什么没有bf==2||bf==-2呢？因为如果发生这种状况，说明树有了问题，需要进行处理（在后面的非健康版讲解）。
根据这个逻辑我们先来实现一段代码。
bool insert(const pair<K, V>& kv)
{if (_root == nullptr)//如果树为空，建立根节点_root = new Node(kv);else//插入{Node* cur = _root,*parent=nullptr;//虽然是三叉链结构，但这里的parent仍需要，因为我们找到的位置是nullptrwhile (cur)//找到需要插入位置的父亲{if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;} else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;} elsereturn false;}cur = new Node(kv);if (kv.first < parent->_kv.first)//判断插入的位置是父亲的左还是右{parent->_left = cur;parent->_bf--;} else{parent->_right = cur;parent->_bf++;}while (parent)//进行bf的处理{if (parent->_bf == 0)//如果父亲bf==0，终止影响break;else if (parent->_bf == 1 || parent->_bf == -1)//父bf 1 or-1{//继续向上影响，更新父子节点的位置cur = parent;parent = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//需旋转{//树结构已经发生问题，不满足AVL树的特性，需要进行处理} }}return true;
}1.4 AVL树的旋转（非健康版）
前面的插入是插入后树中节点bf绝对值都不大于1的情况，那么如果有节点的bf绝对值大于1怎么办呢？
这时就需要对其进行处理，所谓处理就是将树的部分进行旋转，使其满足AVL树的特性。
我们来看看。
这里是右旋转。可以看到，右旋转的发生是当cur->bf==-1&&parent->bf==-2时。
1. 右旋图解
右旋代码
void RotateR(Node* parent)//右单旋
{//记录会进行迁移的节点Node* cur = parent->left;Node* CR = cur->_right;parent->_left = CR;if (CR)CR->_parent = parent;cur->_right = parent;Node* grandfather = parent->_parent;//记录parent的父亲parent->_parent = cur;if (parent == _root)//parent为根{_root = cur;cur->_parent = nullptr;}else//不为根{if (parent == grandfather->_left)//判断parent的位置grandfather->_left = cur;elsegrandfather->_right = cur;cur->parent=grandfather;}cur->_bf = 0;//更新bfparent->_bf = 0;}2. 左旋图解
这里是左旋转，左旋转的发生是当cur->bf==1&&parent->bf==2时的。
左旋代码
void RotateL(Node* parent)//左单旋{//记录会进行迁移的节点Node* cur = parent->_right;//cur节点Node* CL = cur->_left;//cur的左孩子parent->_right = CL;//cur->_left变成parent->_rightif (CL)//如果CL存在，更新其父亲，以免触发空指针的解引用CL->_parent = parent;cur->_left = parent;//parent给cur->_leftNode* grandfather = parent->_parent;//先记录parent的父亲parent->_parent = cur;//更新parent的父亲if (parent == _root)//parent为根，将cur置为_root，其父亲为空{_root = cur;cur->_parent = nullptr;}else//不为根，更新其父亲{if (parent == grandfather->_left)grandfather->_left = cur;elsegrandfather->_right = cur;cur->parent=grandfather;}cur->_bf = 0;parent->_bf = 0;}难道就仅限于此了吗？当然不是，我们接着看。
当类似以下结构就需要双旋转了，即parent->bf绝对值为2，cur->bf绝对值为1，且二者一正一负时就需要双旋转。
下图为parent==2&&cur->bf==-1，需要右左双旋。
也就是说当parent==-2&&cur->bf==1需要左右双旋。
3. 右左双旋图解
cur->left->bf==1时
而图中cl即cur->left的bf不同，会产生不同的效果，因为cur->left的子树最终会分别成为parent与cur的子树 .
cur->left->bf==1时
右左双旋代码
void RotateRL(Node* parent)//右左双旋
{Node* cur = parent->_right;Node* CL = cur->_left;int bf = CL->_bf;RotateR(cur);RotateL(parent);CL->_bf = 0;if (bf == -1){cur->_bf = -1;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;parent->_bf = 1;}else{cur->_bf = 0;parent->_bf = 0;}
}4. 左右双旋图解
cur->right->bf==1时
cur->right->bf==-1时
左右双旋代码
void RotateLR(Node* parent)//左右双旋
{Node* cur = parent->_left;Node* CR = cur->_right;int bf = CR->_bf;RotateL(cur);RotateR(parent);CR->bf = 0;if (bf == -1){cur->_bf = 0;parent->bf = 1;}else if (bf == 1){cur->_bf = -1;parent->_bf = 0;}else{cur->_bf = 0;parent->_bf = 0;}总结
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时，执行左单旋
当pSubR的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是，执行右单旋
当pSubL的平衡因子为1时，执行左右双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。
1.5 AVL树的验证
1.5.1 二叉搜索树的验证
只要中序遍历可以得到一个有序序列，就说明是二叉搜索树。
1.5.2 AVL树的验证
AVL树的验证：
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确
验证代码
bool _IsBanlance(Node* cur, int& height)
{if (cur == nullptr){return true;height = 0;}int leftheight = 0, rightheight = 0;//记录每棵树的左树与右树高度if (!_IsBanlance(cur->_left, leftheight) || !_IsBanlance(cur->_right, rightheight))//有任何一棵子树不满足条件return false;int SubHeight = rightheight - leftheight;//每个节点其下树的高度差都是他的平衡因子if (abs(SubHeight) > 1)//高度差{cout << cur->_kv.first <<":"<<cur->_bf<< endl;cout << "高度差错误，不平衡" << endl;return false;}height = leftheight > rightheight ? leftheight + 1 : rightheight + 1;//更新高度return true;
}1.6 AVL树的删除
因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置
1.7 AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即logN。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
