AVL树简介

AVL树是一种高度平衡的二叉树，在定义树的每个结点的同时，给树的每一个结点增加成员 平衡因子bf ，定义平衡因子为右子树的高度减去左子树的高度。AVL树要求所有节点左右子树的高度差不超过2，即bf的绝对值小于2。

当我们插入新的结点之后，平衡树的平衡状态将会被破坏，因此我们需要采用相应的调整算法使得树重新回归平衡。

预备知识

前文说当插入新的结点时，树的结构可能会发生破坏，因此我们设定了一套调整算法。调整可分为两类：一类是结构调整，即改变树中结点的连接关系，另一类是平衡因子的调整，使平衡因子重新满足AVL树的要求。调整过程包含四个基本的操作，左旋转，右旋转，右左双旋，左右双旋。

平衡树的旋转，目的只有一个，降低树的高度，高度降低之后，就大大简化了在树中查找结点时间复杂度。

左旋：

10、20为树的三个结点。当在20的右子树插入一个结点之后，如图。当Parent结点的平衡因子为2，cur结点的平衡因子为1时进行左旋。

将parent的right指针，指向cur的left结点；同时cur的left指针，指向parent结点。cur结点继承了原来parent结点在该树（子树）中的根节点的位置，如果原来的parent结点还有父结点，cur需要和上一层的结点保持连接关系。（这里我们允许cur的左子树为NULL）

可以看到，旋转之后，原来的parent结点和cur结点的平衡因子都变为0。

//左旋转代码实现：voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL!=NULL)subRL->_parent=parent;Node*ppNode=parent->_parent;subR->_left=parent;parent->_parent=subR;if(ppNode==NULL){_root=subR;subR->_parent=NULL;}else{if(parent==ppNode->_left)ppNode->_left=subR;if(parent==ppNode->_right)ppNode->_right=subR;subR->_parent=ppNode;}parent->_bf=0;subR->_bf=0;}

右旋：

右旋和左旋的原理类似，和左旋成镜像关系。当parent结点的平衡因子变为 -2，cur结点的平衡因子变为-1 时，进行右旋。

将 parent 结点的左指针，指向cur结点的右子树，cur结点的右指针，指向parent结点。同时，cur结点将要继承在该子树中parent结点的根节点的位置。即如果parent结点有它自己的父节点，cur将要和parent结点的父节点保持指向关系。（这里同样允许cur的右子树为NULL）

旋转之后，也可以发现，parent 和 cur结点的平衡因子都变为0。

//右旋转代码实现voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR!=NULL){subLR->_parent=parent;}Node*ppNode=parent->_parent;subL->_right=parent;parent->_parent=subL;if(ppNode==NULL){_root=subL;subL->_parent=NULL;}else{if(parent==ppNode->_left)ppNode->_left=subL;elseppNode->_right=subL;subL->_parent=ppNode;}parent->_bf=0;subL->_bf=0;}

右左双旋：

理解了左单旋和右单旋的情况，双旋实现起来就简单了些。

上图给出了右左双旋的情况，可以看到，当parent 的平衡因子为2，cur 的平衡因子为-1时，满足右左双旋的情况。

右左双旋的实现，可分为三步。

1>以parent->_right 结点为根进行右旋转

2>以parent结点为根进行左旋转

3>进行调整。

前两步应该理解起来问题不大，但右左旋转之后，为什么还要多一步调整呢？原因就在于我的新增结点是在key=20结点（cur结点的左孩子）的左子树还是右子树插入的，还有可能20就是我的新增结点，即h=0。三种情况造成的直接后果就是cur的左孩子结点的平衡因子不同。这将是我们区分三种情况的依据。

这里有个问题值得注意，为了提高代码的复用性，我们在双旋的实现中调用了单旋的函数，但在单旋最后，我们都会将parent 和cur 结点的bf 置0。因此，在单旋之前我们需要保存cur->_left结点的平衡因子。（如上图）

//右左旋转voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;size_tbf=subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf==0){parent->_bf=0;subR->_bf=0;subRL->_bf=0;}elseif(bf==1){subR->_bf=0;parent->_bf=-1;subRL->_bf=0;}else{parent->_bf=0;subR->_bf=1;subRL->_bf=0;}}

左右双旋：

左右双旋和右左双旋其实也差不多，当满足parent的平衡因子为-2，且cur 的平衡因子为1时，进行左右双旋。

和右左双旋的概念类似，我们依旧要先调用单旋函数，之后再进行调整。也需要注意插入节点的位置不同带来的影响，提前对cur的右节点的平衡因子进行保存。这里同样给出图示和代码，不再过多赘述。

//左右双旋voidRotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;size_tbf=subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf==0){parent->_bf=0;subL->_bf=0;subLR->_bf=0;}elseif(bf==1){parent->_bf=0;subL->_bf=-1;subLR->_bf=0;}else{parent->_bf=1;subL->_bf=0;subLR->_bf=0;}}

插入算法

首先我们给出结点的定义和相应的构造函数，其中，_key为关键码，_value为值。

template<typenameK,typenameV>structAVLTreeNode{int_bf;K_key;V_value;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;AVLTreeNode(constK&key,constV&value):_bf(0),_key(key),_value(value),_left(NULL),_right(NULL),_parent(NULL){}};

接下来我们分析的是插入结点的几种情况：

1、树为空树(_root == NULL）

给根节点开辟空间并赋值，直接结束

if(_root==NULL){_root=newNode(k,v);returntrue;}

2、树不为空树

要在树中插入一个结点，大致可分为几步。

1>找到该结点的插入位置

2>插入结点之后，调整该结点与parent结点的指向关系。

3>向上调整插入结点祖先结点的平衡因子。

由于AVL树是二叉搜索树，通过循环，比较待插入结点的key值和当前结点的大小，找到待插入结点的位置。同时给该节点开辟空间，确定和parent节点的指向关系。

//找到待插入结点位置Node*cur=_root;Node*parent=NULL;while(cur!=NULL){parent=cur;if(k>cur->_key){cur=cur->_right;}elseif(k<cur->_key){cur=cur->_left;}else{returnfalse;}}//插入节点，建立指向关系cur=newNode(k,v);if(k<parent->_key){parent->_left=cur;cur->_parent=parent;}else{parent->_right=cur;cur->_parent=parent;}

插入结点之后，对该AVL树结点的平衡因子进行调整。由于插入一个结点，其祖先结点的循环因子都可能发生改变，所以采用循环的方式，向上调整循环因子。

由上图可知，当插入节点之后，该结点的向上的所有祖先结点的平衡因子并不是都在变化，当向上调整直到某一结点的平衡因子变为 0 之后，将不再向上调整，因为此时再向上的结点的左右子树高度差没有发生变化。

接下来是向上调整平衡因子。

由于存在要向上调整，这里定义两个指针，parent 指针和 cur 指针。当开始循环之后，首先进行调整 parent 指针的平衡因子。调整之后，判断平衡因子。

平衡因子为 0 ，则直接跳出循环。

平衡因子为 1 或 -1 时，继续向上调整，进行下次循环。

平衡因子为 2 或 -2 时，就要用到我们一开始提到的算法--->平衡树的旋转

while(parent){//调整parent的bfif(k<parent->_key){parent->_bf--;}else{parent->_bf++;}//如果parent的bf为0，表面插入结点之后，堆parent以上节点的bf无影响if(parent->_bf==0){returntrue;}elseif(abs(parent->_bf)==1)//为1、-1时继续向上调整{cur=parent;parent=cur->_parent;}else//2、-2为2、-2时进行旋转调整{if(parent->_bf==2){if(cur->_bf==1){RotateL(parent);break;}elseif(cur->_bf==-1){RotateRL(parent);break;}}else//parent->_bf==-2{if(cur->_bf==-1){RotateR(parent);break;}elseif(cur->_bf==1){RotateLR(parent);break;}}}}

到这里，插入算法就已经结束，接下来给出两个函数，用以对我们刚刚构建好的AVL树进行判断，看是否满足我们的条件。

boolIsBalance(){intsz=0;return_IsBalance_better(_root,sz);}bool_IsBalance(Node*root,int&height){if(root==NULL)returntrue;intleftheight=0;if(_IsBalance(root->_left,leftheight)==false)returnfalse;intrightheight=0;if(_IsBalance(root->_right,rightheight)==false)returnfalse;height=leftheight>rightheight?leftheight:rightheight;returnabs(leftheight-rightheight)<2&&(root->_bf==rightheight-leftheight);}

关于完整的AVL树的代码，会在下面给出，这里想多说一点的是，AVL树是一棵高度平衡的二叉树，当我们构建好这样一棵二叉树之后，进行查找、插入、删除相应结点的时候，效率肯定是最高的，时间复杂度为O(logN),但实际应用中，比起和他类似的红黑树，AVL的实现难度和由于AVL树的高要求(abs(bf) <2)导致的插入结点要多次调整，AVL树的使用相对较少。