学过平衡二叉树的朋友一定对它有印象。今天阿粉就和大家一起详细了解AVL树！1.总结在上一篇文章中。我们详细介绍了二叉树的算法和代码实践。我们知道，不同的二叉树形态结构也会对查询效率产生很大的影响，尤其是当树的形态结构变成链状结构时，查询的最后一个元素效率极低，如何解决这个问题呢？关键是如何最小化树的深度，从而提高查询效率。平衡二叉查找树就是基于此出现的！平衡二叉搜索树，该算法由Adel开发，由'son-Vel'skii和Landis发明，也俗称AVL树，来源于两位大神的缩写。它的特点是：它的左子树和右子树都是平衡二叉树；及其左子树的右子树深度与右子树深度之差（平衡因子）的绝对值不超过1；简单的说，为了保证平衡，当前节点的左子树和右子树的高度差不超过1！废话不多说，直入正题，算法思路如下！2.算法思想平衡二叉搜索树的搜索思想，与二叉树相同。每个查询分成两半，只使用一部分查询来达到提供效率的目的。插入、删除同理，最大的区别：每次插入或删除后，需要计算节点的高度，然后根据需要进行调整！如何调整？主要方法有：左旋、右旋！下面分别分析一下插入和删除场景的调整。2.1.插入场景我们来分析一下插入的场景，如下：场景1当我们在40的左边或者右边插入的时候，也就是50的左边，我们只需要绕着80向右旋转，就可以实现树高差为0超过1！场景2当我们在60的左边或者右边插入时，也就是在50的右边，我们需要进行两次旋转。首先，我们将向左旋转50度左右，然后向右旋转80度左右，以实现树高差。超过1！场景3当我们在120的左边或右边插入时，也就是90的右边，我们只需要向左旋转80左右就可以实现树高差不超过1！场景4当我们在左边或者85度向右边插入的时候，也就是90度的左边，需要旋转两次。首先会向右旋转90度左右，再向左旋转80度左右，这样树高差不超过1！总结对于插入的操作，总的来说插入其实只有四种，分别是：单左旋转，单右旋转，左旋转-右旋转，右旋转-左旋转，总结如下：当插入节点位于需要旋转的节点的左节点的左子树中，只需要向右旋转；当插入节点在待旋转节点左节点的右子树中时，需要左旋-右旋；当插入节点在待旋转节点右节点的右子树中时，只需要左旋转；当插入节点位于需要旋转的节点的右节点的左子树时，需要进行右旋-左旋；2.2.删除场景接下来我们来分析一下删除场景！其实删除场景和二叉树的删除思路是一样的。不同的是需要调整。被删除节点所在的树需要逐层判断该节点的高度差是否大于1，如果大于1则向左或向右旋转！当删除的节点只有左子树时，直接将左子树传到上层即可！场景二：当被删除的节点只有右子树时，只需要将右子树转移到上层即可！场景三：当删除的节点有左右子树时，因为当前节点左子树末端的右子树或者当前节点右子树末端的左子树，离当前节点最近节点，找到其中任意一个，然后替换其内容，删除结束节点，即可实现删除！综上所述，第三种场景稍微复杂一点，但基本上就是这么个套路。与二叉树不同的是删除后需要判断树的高度，需要调整树的高度，类似于上面插入的左旋，右旋操作！3、代码实践接下来我们从代码层面来定义树的实体结构，如下：1publicclassAVLNode>{23/**节点关键字*/4Ekey;56/**当前节点树高*/7inheight;89/**当前节点的左子节点*/10AVLNodelChild=null;1112/**当前节点的右子节点*/13AVLNoderChild=null;1415publicAVLNode(Ekey){16this.key=key;17}1819@Override20publicStringtoString(){21return"AVLNode{"+22"key="+key+23",height="+height+24",lChild="+lChild+25",rChild="+rChild+26'}';27}28}我们创建一个Algorithm类AVLSolution，完整实现如下：1publicclassAVLSolution>{23/**定义根节点*/4publicAVLNoderoot=null;56/**7*insert8*@paramkey9*/10publicvoidinsert(Ekey){11System.out.println("insert["+key+"]:");12root=insertAVL(key,root);13}1415privateAVLNodeinsertAVL(Ekey,AVLNodenode){16if(node==null){17returnnewAVLNode(key);18}19//左子树查找20if(key.compareTo(node.key)<0){21//当前节点左子树不为空，继续向下递归搜索22node.lChild=insertAVL(key,node.lChild);23//存在不平衡，只有左子树高于右子树，大于1时调整24if(getHeight(node.lChild)-getHeight(node.rChild)==2){25if(key.compareTo(node.lChild.key)<0){26//如果插入的节点在当前节点左节点的左子树中，则进行单次右旋27node=rotateRight(node);28}else{29//如果插入的节点位于当前节点左节点的右子树中，则先左旋再右旋30node=rotateLeftRight(node);31}32}33}elseif(key.compareTo(node.key)>0){34//当前节点右子树不为空，继续向下递归查找35node.rChild=insertAVL(key,node.rChild);36//存在不平衡，只会是右子树比左子树高，大于1时才调整37if(getHeight(node.rChild)-getHeight(node.lChild)==2){38if(key.compareTo(node.rChild.key)<0){39//如果插入的节点在当前节点右节点的左子树中，则先右旋再左旋40node=rotateRightLeft(node);41}else{42//如果插入的节点在当前节点中为右节点的右子树，进行单次左旋转43node=rotateLeft(node);44}45}46}else{47//key已经存在，直接返回48}49//由于节点插入，树高发生变化，更新节点高度50node.height=updateHeight(node);51returnnode;52}5354/**55*delete56*@paramkey57*/58publicvoiddelete(Ekey){59root=deleteAVL(key,root);60}6162privateAVLNodedeleteAVL(Ekey,AVLNodenode){63if(node==null){64returnnull;65}66if(key.compareTo(node.key)<0){67//左子树查找68node.lChild=deleteAVL(key,node.l子）；69//可能会出现右子树比左子树高270if(getHeight(node.rChild)-getHeight(node.lChild)==2){71node=rotateLeft(node);72}73}elseif(key.compareTo(node.key)>0){74//右子树查找75node.rChild=deleteAVL(key,node.rChild);76//可能出现左子树比右子树高277if(getHeight(node.lChild)-getHeight(node.rChild)==2){78node=rotateRight(node);79}80}else{81//找到目标元素，三种情况下删除82//1.当前节点没有左子树，直接返回当前Node右子树83//2。当前节点没有右子树，直接返回当前节点右子树84//3。当当前节点有左子树和右子树时，找到当前节点最右子树末尾的左子树，替换去掉85if(node.lChild==null){86returnnode.rChild;87}88if(node.rChild==null){89returnnode.lChild;90}91//找到当前节点右子树末尾的左子树为右子树的最小节点92AVLNodeminLChild=searchDeleteMin(node.rChild);93//删除最小节点，如果高度发生变化，则调整它94minLChild.rChild=deleteMin(node.rChild);95minLChild.lChild=node.lChild;//将当前节点的左子树转移到最小节点9697node=minLChild;//覆盖当前节点98//因为右子树的高度变低了，所以可能需要调整99if(getHeight(node.lChild)-getHeight(node.rChild)==2){100node=rotateRight(node);101}102}103node.height=updateHeight(node);104returnnode;105}106107/**108*搜索109*@paramkey110*@return111*/112publicAVLNodesearch(Ekey){113returnsearchAVL(key,root);114}115116privateAVLNodesearchAVL(Ekey,AVLNodenode){117if(node==null){118returnnull;119}120//左子树搜索121if(key.compareTo(node.key)<0){122returnsearchAVL(key,node.lChild);123}elseif(key.compareTo(node.key)>0){124returnsearchAVL(key,node.rChild);125}else{126//key已经存在，直接返回127returnnode;128}129}130131/**132*找到要删除的元素133*@paramnode134*@return135*/136privateAVLNodesearchDeleteMin(AVLNodenode){137if(node==null){138returnnull;139}140while(node.lChild!=null){141node=node.lChild;142}143returnnode;144}145146/**147*删除元素148*@paramnode149*@return150*/151privateAVLNodedeleteMin(AVLNodenode){152if(node==null){153returnnull;154}155if(node.lChild==null){156returnnode.rChild;157}158//移除最小节点159node.lChild=deleteMin(node.lChild);160//此时移除左边节点，判断平衡高度是否为destroyed161if(getHeight(node.rChild)-getHeight(node.lChild)==2){162//调整163node=rotateLeft(node);164}165returnnode;166167}168169/**170*单向左旋转171*@paramnode172*@return173*/174privateAVLNoderotateLeft(AVLNodenode){175System.out.println("节点："+node.key+",单向左旋转");176AVLNodex=node.rChild;//获取旋转节点的右节点177node.rChild=x.lChild;//传递旋转节点右节点的左节点作为旋转节点的右子树178x.lChild=node;//使用旋转节点作为旋转节点右子树的左子树179180//更新调整节点的高度（先调整Rotatenode节点）181node.height=updateHeight(node);182x.height=updateHeight(x);183returnx;184}185186/**187*单右旋转188*@return189*/190privateAVLNoderotateRight(AVLNodenode){191System.out.println("Node:"+node.key+",singlerightrotation");192AVLNodex=node.lChild;//获取旋转节点的左节点193node.lChild=x.rChild;//传递右节点旋转节点的左子树作为旋转节点的左子树194x.rChild=node;//将旋转节点作为旋转节点左子树的右子树195196//更新调整节点的高度（先调整旋转node节点）197node.height=updateHeight(node);198x.height=updateHeight(x);199returnx;200}201202/**203*左旋-右旋204*@paramnode205*@return206*/207privateAVLNoderotateLeftRight(AVLNodenode){208System.out.println("Node:"+node.key+",rotateleft-rotateright");209//首先执行当前节点左旋转210node.lChild=rotateLeft(node.lChild);211//当前节点右旋转212returnrotateRight(node);213}214215/**216*向右旋转-向左旋转217*@paramnode218*@return219*/220privateAVLNoderotateRightLeft(AVLNodenode){221System.out.println("node:"+node.key+",rotateright-rotateleft");222//先将当前节点的右节点旋转右223node.rChild=rotateRight(node.rChild);224returnrotateLeft(node);225226}227228/**229*获取节点高度，若为空则等于-1230*@paramnode231*@return232*/233privateintgetHeight(AVLNodenode){234returnnode!=null?node.height:-1;235}236237/**238*updateNodeheight239*@paramnode240*@return241*/242privateintupdateHeight(AVLNodenode){243//比较当前节点的左子树和右子树的高度，得到节点高度244returnMath.max(getHeight(node.lChild),getHeight(node.rChild))+1;245}246247/**248*前序遍历249*@paramnode250*/251publicvoidfrontTreeIterator(AVLNodenode){252if(node!=null){253System.out.println("key:"+node.key);254frontTreeIterator(node.lChild);//遍历当前节点的左子树255frontTreeIterator(node.rChild);//遍历当前节点的右子树256}257}258259/**260*顺序遍历261*@paramnode262*/263publicvoidmiddleTreeIterator(AVLNodenode){264if(node!=null){265middleTreeIterator(node.lChild);//遍历当前节点的左子树266System.out.println("key:"+node.key);267middleTreeIterator(node.rChild);//遍历当前节点的右子树268}269}270271/**272*后序遍历273*@paramnode274*/275publicvoidbackTreeIterator(AVLNodenode){276if(node!=null){277backTreeIterator(node.lChild);//遍历当前节点的左子树278backTreeIterator(node.rChild);//遍历当前节点的右子树279System.out.println("key:"+node.key);280}281}282283}测试代码，如下：1publicclassAVLClient{23publicstaticvoidmain(String[]args){4//创建一个Integer数据结构5AVLSolutionavlTree=newAVLSolution();67//插入节点8System.out.println("========插入元素========");9avlTree.insert(newInteger(100));10avlTree.insert(newInteger(85));11avlTree.insert(newInteger(120));12avlTree.insert(newInteger(60));13avlTree.insert(newInteger(90)));14avlTree.insert(newInteger(80));15avlTree.insert(newInteger(130));16System.out.println("========中序遍历元素========");1718//中序遍历19avlTree.middleTreeIterator(avlTree.root);20System.out.println("========找到key为100的元素========");2122//查询节点23AVLNodesearchResult=avlTree.search(120);24System.out.println("搜索结果："+searchResult);25System.out.println("========删除键90元素========");2627//删除节点28avlTree.delete(90);29System.out.println("========再按顺序遍历元素========");3031//中序遍历32avlTree.middleTreeIterator(avlTree.root);33}34}的输出结果如下：4.总结平衡二叉树搜索树，俗称AVL树，查询时，操作与普通二叉树搜索树上的搜索操作相同；插入时，每个插入节点操作最多只需要单次旋转或两次旋转；如果是动态删除，删除后，必须检查被删除节点到根节点路径上的所有节点点的平衡因子，即高度差，如果超过1则需要调整，以及它最多可能需要O(logN)次旋转。总的来说，平衡二叉树比普通的二叉搜索树要好！5、参考[1]简书-nicktming-二叉平衡树：https://www.jianshu.com/p/22c00b3731f5[2]iteye-Heart.X.Raid-平衡二叉搜索树[AVL]：https：//www.iteye.com/blog/hxraid-609949
