AVL树又称为高度平衡的二叉搜索树,是1962年由两位俄罗斯数学家G.M.Adel’son-Vel’skii和E.M.Landis提出的。ALV树提高了二叉搜索树树的搜索效率。为此,就必须每向二叉搜索树插人一个新结点时调整树的结构,使得二叉搜索树保持平衡,从而尽可能降低树的高度,减少树的平均搜索长度。

一、AVL树的概念

        AVL树是自平衡的二叉搜索树，AVL树可以为空树。AVL树的左子树和右子树的高度差的绝对值最大不超过1,每个结点的左右子树都是AVL树。

        平衡因子（balance factor，简称bf）：左右子树的高度差即为平衡因子的值，比如左子树高度为1，右子树高度为2，那么平衡因子的计算在这里我们规定为右子树的高度减去左子树的高度，也就是1。

        一棵简单的AVL树的图示：

        红色数字标注的是对应结点的平衡因子。

        因为ALV树的左右子树能够保持高度差不超过1，所以假设AVL树有n个结点，那么该二叉树的高度为,平均搜索长度为搜索高度次。

二、树结点的定义

//AVL树结点的定义
template<class K,class V>
struct AVLTreeNode
{pair<K, V> _kv;	//键值对AVLTreeNode<K, V>* _pLeft;AVLTreeNode<K, V>* _pRight;AVLTreeNode<K, V>* _pParent; //指向父亲结点int _bf; //平衡因子AVLTreeNode(const pair<K, V>& kv) :_kv(kv.first, kv.second),_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_bf(0){}
};

三、接口声明以及部分接口的定义 

接口声明：

//AVL树
template<class K, class V>
class AVLTree
{
private:typedef AVLTreeNode<K, V> Node;typedef pair<K, V> ValueType;Node* _root;//根结点//递归的辅助实现的：void _inOrder(Node* root);	//中序遍历void destroy(Node* root);	//后序遍历析构int _height(Node* root);//计算树的高度int _size(Node* root);//计算树的结点个数bool _checkTree(Node* root);//检测树的因子是否正确,树是否平衡。//旋转void rotateL(Node* parent);//左单旋void rotateR(Node* parent);//右单旋void rotateLR(Node* parent);//左右双旋void rotateRL(Node* parent);//右左双旋
public:AVLTree() :_root(nullptr) {}	//构造~AVLTree();	//析构bool insert(const ValueType& x);	//插入bool erase(const K& key);	//删除int size();	//计算树的结点个数int height();	//计算树的高度Node* find(const K& key);	//查找void inOrder();	//中序遍历节点并打印valbool checkTree();	//检测树的因子是否正确,树是否平衡。
};

部分接口的定义比较简单，直接给出：

//AVL树
template<class K, class V>
class AVLTree
{
private:typedef AVLTreeNode<K, V> Node;typedef pair<K, V> ValueType;Node* _root;//根结点//递归的辅助实现的：void _inOrder(Node* root)	//中序遍历{if (!root)return;_inOrder(root->_pLeft);cout << root->_kv.first << " -> " << root->_kv.second << " bf = " << root->_bf << endl;_inOrder(root->_pRight);}void destroy(Node* root)	//后序遍历析构{if (!root)return;destroy(root->_pLeft);destroy(root->_pRight);delete root;}int _height(Node* root)//计算树的高度{if (root == nullptr)return 0;int leftHeight = _height(root->_pLeft);int rightHeight = _height(root->_pRight);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int _size(Node* root)	//计算树的结点个数{if (root == nullptr)return 0;return _size(root->_pLeft) + _size(root->_pRight) + 1;}bool _checkTree(Node* root)	//检测树的因子是否正确,树是否平衡。{if (root == nullptr)return true;int leftHeight = _height(root->_pLeft);int rightHeight = _height(root->_pRight);int bf = rightHeight - leftHeight;if (root->_bf != bf){cout << "结点的因子计算错误:" << root->_kv.first << "的bf为" << root->_bf << " 而正确的bf为" << bf << endl;return false;}if (bf >= 2 || bf <= -2){cout << root->_kv.first << "的左右子树高度差超过1，树不平衡" << endl;return false;}return _checkTree(root->_pLeft) && _checkTree(root->_pRight);}//旋转void rotateL(Node* parent);//左单旋void rotateR(Node* parent);//右单旋void rotateLR(Node* parent);//左右双旋void rotateRL(Node* parent);//右左双旋
public:AVLTree() :_root(nullptr) {}	//构造~AVLTree()	//析构{destroy(_root);_root = nullptr;}bool insert(const ValueType& x);	//插入bool erase(const K& key);	//删除int size()	//计算树的结点个数{return _size(_root);}int height()	//计算树的高度{return _height(_root);}Node* find(const K& key)	//查找{Node* pCur = _root;while (pCur){if (key > pCur->_kv.first)pCur = pCur->_pRight;else if (key < pCur->_kv.first)pCur = pCur->_pLeft;elsereturn pCur;}//找不到return nullptr;}void inOrder()	//中序遍历节点并打印val{_inOrder(_root);}bool checkTree()	//检测树的因子是否正确,树是否平衡。{return _checkTree(_root);}
};//AVL树结点的定义
template<class K,class V>
class AVLTreeNode
{pair<K, V> _kv;	//键值对AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent; //指向父亲结点int _bf; //平衡因子AVLTreeNode(const pair<K, V>& kv) :_kv(kv.first, kv.second),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

        这里重点介绍的是AVL树的四种旋转以及在插入和删除结点时该如何使用旋转来使搜索树从不平衡变平衡。 

四、AVL树的四种旋转

（一）、左单旋转

        如果在插入新结点之前AVL树的形状如下图所示：

        其中圆形框代表一个结点，旁边标注的数字为平衡因子，矩形框表示结点的子树，h是子树的高度。如果h = 0，说明子树为空；如果h > 0说明子树存在。

        此时，该搜索二叉树满足AVL树的要求。

        接着在结点parent的右子树上较高的一侧插入一个新的结点，也就是在γ子树上插入一个新的结点x。这时，由于γ子树的高度发生了变化，需要向上调整双亲结点的平衡因子，因此结点sub的平衡因子从0变为了1，结点parent的平衡因子从1变为了2。此时结点parent的平衡因子大于1，左右子树的高度不平衡。因为parent和sub的平衡因子同号，即正负相同，右子树偏高，需要进行左单旋操作。

        我们需要以结点parent为旋转轴，让sub结点逆时针旋转。让sub的左子树subL成为结点parent的右子树，结点parent成为结点sub的左子树。并更新sub和parent的平衡因子为0。

        旋转后可以看出，结点sub的左右子树高度相同，搜索二叉树又恢复了平衡，结点sub和结点parent的平衡因子都为0。

         左单旋代码：

	//旋转void rotateL(Node* parent)//左单旋{Node* sub = parent->_pRight;Node* subL = sub->_pLeft;Node* pPrev = parent->_pParent; //parent的前驱结点parent->_pRight = subL;	//结点subL成为parent的右子树if (subL)	//将结点subL的前驱结点改为结点parentsubL->_pParent = parent;sub->_pLeft = parent;	//parent成为sub的左结点parent->_pParent = sub;//处理前驱结点prev和结点subif (pPrev == nullptr)	//说明结点parent原来为根结点{_root = sub;	//sub成为新的根节点sub->_pParent = nullptr;}else{if (pPrev->_pLeft == parent)pPrev->_pLeft = sub;elsepPrev->_pRight = sub;sub->_pParent = pPrev;}//更新平衡因子sub->_bf = parent->_bf = 0;}

（二）、右单旋转 

        右单旋转其实就是左单旋转对称的情况。

        如果在插入新结点X之前AVL树的形状如下图所示：

        此时，该搜索二叉树满足AVL树的要求。        

        接着在结点parent的左子树上较高的一侧插入一个新的结点，也就是在γ子树上插入一个新的结点x。这时，由于γ子树的高度发生了变化，需要向上调整双亲结点的平衡因子，因此结点sub的平衡因子从0变为了-1，结点parent的平衡因子从-1变为了-2。此时结点parent的平衡因子小于1，左右子树的高度不平衡。因为parent和sub的平衡因子同号，即正负相同，左子树偏高，需要进行右单旋操作。        我们需要以结点parent为旋转轴，让sub结点顺时针旋转。让sub的右子树subR成为结点parent的左子树，结点parent成为结点sub的右子树，并且更新sub和parent的平衡因子为0。        旋转后可以看出，结点sub的左右子树高度相同，搜索二叉树又恢复了平衡，结点sub和结点parent的平衡因子都为0。

        右单旋转代码：

	void rotateR(Node* parent)//右单旋{Node* sub = parent->_pLeft;Node* subR = sub->_pRight;Node* pPrev = parent->_pParent;	//parent的前驱结点parent->_pLeft = subR;	//结点subR成为parent的左子树if (subR)	//将结点subR的前驱结点改为结点parentsubR->_pParent = parent;sub->_pRight = parent;	//parent成为sub的右结点parent->_pParent = sub;//处理前驱结点prev和结点subif (pPrev == nullptr)	//说明结点parent原来为根结点{_root = sub;	//sub成为新的根节点sub->_pParent = nullptr;}else{if (pPrev->_pLeft == parent)pPrev->_pLeft = sub;elsepPrev->_pRight = sub;sub->_pParent = pPrev;}//更新平衡因子sub->_bf = parent->_bf = 0;}

（三）、左右双旋 

        有的时候，单次旋转不能解决搜索树不平衡的问题。比如下面这个情况：

        单旋根本解决不了问题，旋转两次还回到了起点。这种情况需要进行左右双旋。

         如果在插入新结点X之前AVL树的形状如下图所示：

        此时，该搜索二叉树满足AVL树的要求。

        接着在结点parent的左子树的右子树插入一个新的结点，也就是在β子树或者γ子树（这里选择了β）上插入一个新的结点x。这时，由于β的高度发生了变化，需要向上调整双亲结点的平衡因子，因此结点subR的平衡因子从0变为了-1，结点sub的平衡因子从0变为了1，结点parent的平衡因子从-1变为了-2。此时结点parent的平衡因子小于1，左右子树的高度不平衡。因为parent和sub的平衡因子异号，即正负不相同，结点sub的右子树偏高而parent的左子树偏高，需要进行先左后右的双旋操作。

以sub为轴，subR逆时针旋转，进行一次左单旋：

        然后再以parent为轴，subR顺时针旋转，进行一次右单旋，并且根据实际情况更新parent，sub以及subR的平衡因子，这里更新后的平衡因子分别为1,0,0。

        我们可以将左右双旋前后的结构进行对比，发现双旋的结果可以概括为：将subR平移上去作为该树的根，subR的左右子树β和γ分配给了sub和parent。

        所以根据双旋结果可以知道，如果新节点x插入到了γ子树下面，那么parent，sub以及subR结点的平衡因子分别为0,-1,0。

        还有一种特殊情况需要处理，上面的情况都是h > 1的情况，如果h = 0的话，AVL树的情况如下。

        此时插入的结点在sub的右边。

        parent的平衡因子小于1，sub的平衡因子等于1，parent和sub的平衡因子异号，需要进行左右双旋。

        此时parent、sub以及subR的平衡因子都为0。

左右双旋代码：

void rotateLR(Node* parent)//左右双旋
{Node* sub = parent->_pLeft;Node* subR = sub->_pRight;//得到subR的平衡因子，//如果为-1，则新结点插入到了subR的左边,也就是β下//如果为 1，则新节点插入到了subR的右边，也就是γ下//如果为0，则是h = 0的情况。int bf = subR->_bf;//复用左和右单旋的代码哈哈rotateL(sub);rotateR(parent);//这里旋转完后，parent、sub以及subR的平衡因子都被置为0了//按照情况调整平衡因子的值if (bf == -1) //新节点插入到了subR的左边subR->_pRight->_bf = 1;else if (bf == 1)	//新节点插入到了subR的右边subR->_pLeft->_bf = -1;//若bf为0，可以啥也不干。
}

 （四）、右左双旋

        右左双旋的情况就是左右双旋情况的对称。这里快速用几张图演示一下。

        假设有这样一颗AVL树：

        若将新结点插入到γ下，进行右左单旋。更新parent、sub、subR的平衡因子为0,1,0。

       若将新结点插入到β下，进行右左单旋，更新parent、sub、subR的平衡因子为-1,0,0。

        当h = 0时。 进行右左单旋，更新parent、sub、subR的平衡因子为0,0,0。

 右左单旋代码：

void rotateRL(Node* parent)//右左双旋
{Node* sub = parent->_pRight;Node* subL = sub->_pLeft;//得到subL的平衡因子，//如果为-1，则新结点插入到了subL的左边,也就是γ下//如果为 1，则新节点插入到了subL的右边，也就是β下//如果为0，则是h = 0的情况。int bf = subL->_bf;//继续复用左和右单旋rotateR(sub);rotateL(parent);if (bf == -1) //新节点插入到了subL的左边subL->_pRight->_bf = 1;else if (bf == 1)	//新节点插入到了subL的右边subL->_pLeft->_bf = -1;//若bf为0，可以啥也不干。
}

五、插入操作

        在实现了四种旋转后，可以进行插入操作了。

        首先需要找到新结点插入的位置，然后从插入的位置起向上回溯调整双亲结点的平衡因子。如果插入的结点在双亲结点的左边，那么双亲结点的平衡因子减一，如果插入的结点在双亲结点的右边，那么双亲结点的平衡因子加一。

        每一次回溯调整了双亲结点的平衡因子后，需要判断是否还需要进行向上调整或是否需要进行旋转操作。

        平衡因子有以下几种情况和处理方法。

插入的代码如下：

bool insert(const ValueType& x)	//插入
{//找到x所插入的位置Node* pCur = _root;Node* pPos = nullptr;while (pCur){pPos = pCur;//x的first小往左走，大往右走if (pCur->_kv.first > x.first)pCur = pCur->_pLeft;else if (pCur->_kv.first < x.first)pCur = pCur->_pRight;elsereturn false;	//插入的值已存在，插入失败}//如果树为空，那么插入的结点即为根节点if (pPos == nullptr){_root = new Node(x);return true;}//插入该结点Node* pChild = new Node(x);if (x.first > pPos->_kv.first){pPos->_pRight = pChild;pPos->_pRight->_pParent = pPos;}else{pPos->_pLeft = pChild;pPos->_pLeft->_pParent = pPos;}//向上调整平衡因子Node* pParent = pPos;while (pParent)	//最坏的情况调整到根{//插入的结点在左子树,双亲结点的平衡因子--if (pParent->_pLeft == pChild)	{pParent->_bf--;}else //插入的结点在右子树，双亲节点的平衡因子++{pParent->_bf++;}//判断是否需要进行旋转或结束向上调整操作if (pParent->_bf == 0)break;	//结束向上调整else if (pParent->_bf == -2)  //左子树偏高,需要进行旋转{if (pChild->_bf == -1)	//同号，进行右单旋rotateR(pParent);else if (pChild->_bf == 1)  //异号，进行左右单旋rotateLR(pParent);break;}else if (pParent->_bf == 2)	//右子树偏高{if (pChild->_bf == 1)	//同号，进行左单旋rotateL(pParent);else if (pChild->_bf == -1)  //异号，进行右左单旋rotateRL(pParent);break;}else if (pParent->_bf == -1 || pParent->_bf == 1)	//需要继续向上调整{pChild = pParent;pParent = pParent->_pParent;}else{//因子情况出错assert(false);}}return true;
}

六、删除操作 

AVL树的删除操作和二叉搜索树的删除操作类似。

1、如果待删除的结点pos最多只有一个孩子child（当pos没有孩子时child指向空），pos结点的双亲结点为parent，只需要将parent原指向pos的指针改为指向pos的孩子child，然后再删除pos结点即可。

2、如果待删除的结点pos有两个孩子（都不为空），则需要pos结点的数据和pos结点的右子树的最小值结点rightMin或左子树的最大值leftMax结点的值进行交换，然后将pos指向rightMin或leftMax，这个时候pos指向的结点最多只有一个孩子child，这样就转化为了第一种情况的删除操作。

         删除结点后，子树高度的变化会影响到路径上的祖宗结点的平衡因子，所以需要从删除的结点pos的位置向上回溯更新双亲结点parent的平衡因子。如果删除的结点在双亲结点parent的左边，则parent的平衡因子加一，如果删除的结点在双亲结点parent的右边，则平衡因子减一。然后根据平衡因子更新后的值判断还需不需要继续进行向上调整或旋转操作。

        下面来考察平衡因子变化的几种情况和需要对其进行的操作。

        情况1：当双亲结点parent的平衡因子原来为0时，删除一个结点后，平衡因子更新为-1或1。

        在parent的左或右子树中删除一个结点，并且更新parent的平衡因子。

        或者：

        删除后发现以parent为根的这棵树的高度和之前相比没有发生变化，还是h，所以结束向上调整平衡因子的操作。

        情况二： 当双亲结点parent的平衡因子原来为-1或1时，删除一个结点后，parent的平衡因子更新为0。

        或者：

        此时，以parent为根的这棵子树的高度和原来相比高度减少了1，所以我们需要继续向上回溯调整双亲结点的平衡因子。

        情况3：parent原来的平衡因子为-1或1，删除结点后，parent结点的平衡因子更新为了-2或2，说明删除的结点在parent较矮的子树上，造成了parent的左右子树不平衡，需要进行旋转操作。

        当parent原来的平衡因子为1的情况：

1、parent平衡因子为1，sub结点的平衡因子为0。

        删除的结点在左子树上，parent的平衡因子变为2。

        以parent为轴，sub逆时针旋转，进行一次左单旋转操作。

        旋转后更新parent和sub的平衡因子分别为1和-1，此时以sub为根的树的高度和原来相比没有变化，高度为h + 2，可以结束向上回溯过程了。

2、parent平衡因子为1，sub结点的平衡因子为1。

        删除的结点在左子树上，parent的平衡因子变为2。

        再以parent为轴，sub逆时针旋转，进行一次左单旋转操作。

        旋转后更新parent和sub的平衡因子分别为0和0，此时以sub为根的树的高度和原来相比减少了1，高度为h + 1，需要继续回溯进行向上调整平衡因子的操作。

3、parent的平衡因子为1，sub的平衡因子为-1，subL的平衡因子可以为-1或0或1。

       当删除的结点在parent的左子树上，parent的平衡因子变为2。

        因为parent的平衡因子和sub的平衡因子异号，所以需要进行右左双旋操作。旋转过程：

        以sub为轴，subL顺时针旋转，进行一次右单旋转。

        以parent为轴，subL逆时针旋转，进行一次左单旋转。

        如果α子树的高度为h - 1，β子树的高度为h -2，那么parent，sub，subL的平衡因子分别为0,1,0。

        如果α子树的高度为h - 2，β子树的高度为h -1，那么parent，sub，subL的平衡因子分别为-1,0,0。

        如果α子树的高度为h - 1，β子树的高度为h -1，那么parent，sub，subL的平衡因子分别为0,0,0。

        旋转后以subL为根的这棵树的高度和原来的高度相比减少了1，为h + 1，需要继续回溯进行向上调整的操作。

        上面是parent原来的平衡因子为1的情况。

        然后就是当parent原来的平衡因子为-1的情况：处理的方法就是上面的所有情况的对称，这里快速用图演示过程，细节不再赘述。

1、parent平衡因子为-1，sub结点的平衡因子为0。

2、parent平衡因子为-1，sub结点的平衡因子为-1。

3、parent平衡因子为-1，sub结点的平衡因子为1。

代码如下：

bool erase(const K& key)	//删除
{Node* pPos = _root;//找到要删除的结点while (pPos){if (pPos->_kv.first > key)pPos = pPos->_pLeft;else if (pPos->_kv.first < key)pPos = pPos->_pRight;elsebreak;}if (pPos == nullptr)	//找不到要删除的结点return false;//如果要删除的结点有两个孩子，需要转化为情况一if (pPos->_pLeft && pPos->_pRight)	{Node* pRightMin = pPos->_pRight;	//寻找pPos右子树的最小结点while (pRightMin->_pLeft){pRightMin = pRightMin->_pLeft;}//交换pPos和pRightMin的值pPos->_kv = pRightMin->_kv;pPos = pRightMin;	//转化为删除结点pRightMin}//此时pPos至少有一个孩子，先不删除pPos，当向上调整好平衡因子后再回来删除//如果删除的结点是根结点if (pPos->_pParent == nullptr){Node* pChildOfPos = nullptr;if (pPos->_pLeft != nullptr)pChildOfPos = pPos->_pLeft;elsepChildOfPos = pPos->_pRight;//让根的子树的根成为整棵树的根,根可能没有孩子，会为空_root = pChildOfPos;if(pChildOfPos)pChildOfPos->_pParent = nullptr;delete pPos;return true;}//先向上调整好祖先的平衡因子再回来删除pPosNode* pChild = pPos;Node* pParent = pPos->_pParent;while (pParent)	//最坏向上回溯到根节点{if (pParent->_pLeft == pChild)	//待删除的结点在parent的左边pParent->_bf++;else  //待删除的结点在parent的右边pParent->_bf--;//根据因子的情况判断是否需要继续进行向上调整或旋转if (pParent->_bf == -1 || pParent->_bf == 1)//情况一：删除结点后高度不变break;else if (pParent->_bf == 0)//情况二：需要继续进行向上调整{pChild = pParent;pParent = pParent->_pParent;}else if (pParent->_bf == -2 || pParent->_bf == 2)	//情况三：旋转{Node* sub = nullptr;if (pParent->_bf == -2)sub = pParent->_pLeft;elsesub = pParent->_pRight;if (pParent->_bf == 2 && sub->_bf == 0)	//左单旋,旋转后高度不变{rotateL(pParent);//更新因子pParent->_bf = 1;sub->_bf = -1;break;}else if (pParent->_bf == 2 && sub->_bf == 1)	//左单旋,旋转后高度变化{rotateL(pParent);//需要继续进行向上调整pParent = sub; //旋转后sub为新的根节点，所以要从这里开始回溯pChild = pParent;pParent = pParent->_pParent;}else if (pParent->_bf == 2 && sub->_bf == -1)	//右左双旋,旋转后高度变化{rotateRL(pParent);//需要继续进行向上调整pParent = pParent->_pParent; //旋转后parent的parent为新的根节点，所以要从这里开始回溯pChild = pParent;pParent = pParent->_pParent;}else if (pParent->_bf == -2 && sub->_bf == 0)	//右单旋，旋转后高度不变{rotateR(pParent);//更新平衡因子pParent->_bf = -1;sub->_bf = 1;break;}else if (pParent->_bf == -2 && sub->_bf == -1)	//右单旋，旋转后高度变化{rotateR(pParent);//需要继续进行向上调整pParent = sub; //旋转后sub为新的根节点，所以要从这里开始回溯pChild = pParent;pParent = pParent->_pParent;}else if (pParent->_bf == -2 && sub->_bf == 1)	//左右双旋，旋转后高度变化{rotateLR(pParent);//需要继续进行向上调整pParent = pParent->_pParent; //旋转后parent的parent为新的根节点，所以要从这里开始回溯pChild = pParent;pParent = pParent->_pParent;}else{assert(false);}}else  //因子情况不存在{assert(false);}}