本文转载自微信公众号“bigsai”，作者：bigsai。转载本文请联系bigsai公众号。什么是AVL树大家好，我是bigsai，好久不见，很想你们，今天给大家讲讲AVL树。树这个数据结构大家已经不陌生了，下面简单回顾一下。在树的种类中，通常分为二叉树和多叉树。我们熟悉的二叉树的种类有二叉搜索（排序、搜索）树、二叉平衡树、splay树、红黑树等等。大家熟悉的B树、字典树等多叉树都是经典的多叉树。普通的二叉树，我们研究它的遍历方法，因为它没有规则和约束，查找和插入都是很随机的，所以研究价值不大。但是二叉树的结构很有特点：左孩子和右孩子，不同方向的两个孩子对应二进制01，判断对错，比较大小，所以按照这个结构，所有树的左节点比父节点小，右节点比父节点大，此时就诞生了一颗二叉查找（排序）树。二叉搜索（排序）树的一大特点是提高了搜索效率，因为搜索一个元素位置或检查一个元素是否存在，可以通过直接比较遇到的每个节点来逐步逼近结果的位置。但是二分查找（排序树）一个很大的问题就是当插入的节点非常有序的时候，很可能变成一棵倾斜的树或者深度很高，那么这样的查找效率还是接近于线性的O(n)级，所以这种情况下二叉查找（排序）树的效率是比较低的。于是，人们就有了一个期待：一棵树插节点，小的还是在左边，大的还是在右边，方便查找，但能不能不要这么斜？不，平衡二分查找（AVL）树就是这样完成的。AVL每次插入时都会进行旋转和自平衡，使整棵树始终处于平衡状态，整棵树的查询更稳定（logN）。我们先来看看什么是AVL树：AVL树是一种有平衡条件的二叉查找树。这种平衡条件必须易于维护，并且其深度必须保证为O(logN)。AVL的左右子树的高度差（平衡因子）不大于1，其每棵子树也是一棵平衡二叉树。对于平衡二叉树的最小数目，n0=0；n1=1；nk=n(k-1)+n(k-2)+1；（方法可以类比斐波那契数列）难点：AVL??是一个二叉的Fork排序树，在复杂度不太高的情况下，可以用什么样的规则或法则来达到动态平衡？如果从简单情况模型来看不平衡情况，四种不平衡情况其实很简单，即RR,LL,RL,LR四种不平衡情况。然后也很容易对结果进行平衡（只看结果，不考虑它的附属节点），把中间的值移到最上面，其他相对位置不变：当然，这只是太理想化的情况三节点的是的，很多时候让你找到不平衡点，或者说我们在解决不平衡的时候，需要的是找到第一个不平衡点（从下往上），然后平衡。这里给出两个不平衡点平衡的例子：以上四种不平衡情况可能出现在底部，可能出现在头部，也可能出现在中间节点造成不平衡，我们只需要研究第一个不平衡点，之后求解整棵树树继续平衡。在具体处理上，我们采用递归的方法来解决问题。针对四种不平衡情况分别处理四种不平衡情况，这里对每一种情况进行详细说明。RR平衡旋转（左单旋转）这里RR指的是节点模型的出现，意思是需要左单旋转（记住的时候需要注意RR不是右旋转）！出现这种情况的原因是节点的右边右边比较深。这时候不平衡节点就需要左旋了，再仔细看流程。在向左旋转的过程中，根（oldroot）节点下沉，中间节点（newroot）上浮。中间节点（newroot）的右侧保持不变。它向左浮动，因此需要指向根节点(oldroot)（毕竟它是一棵树）。但是这样一来，newroot发现左节点H是空的。而我们还需要让整棵树完整，满足二叉排序树的规则。刚好oldroot的右边指向newroot，但是现在结构变了，oldroot的右边空了。正好这个位置满足oldroot的右边和newroot的左边，所以我们在这个位置插入H。其中H可以为NULL，但不影响运行！更详细的过程是：而左手代码可以表示为：privatenodegetRRbanlance(nodeoldroot){//右手深，需要左手//TODOAuto-generatedmethodstubnodenewroot=oldroot.right;oldroot。right=newroot.left;newroot.left=oldroot;oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;newroot.height=Math.max(getHeight(newroot.left)),getHeight(newroot.right))+1;//需要重新计算原根的高度returnnewroot;}LL平衡旋转（右单旋转）和右旋转和左旋转相反，但是思路是一样的,按照上面的替换就好了!代码:privatenodegetLLbanlance(nodeoldroot){//LL小,需要向右旋转oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//需要更新原根的高度Sourreturnnewroot;}RL平衡旋转（先右后左）doublerotation）大家可能对这个RL有点疑惑，为什么RR叫左旋，LL叫右旋，这个RL为什么叫先右后左旋转？不用担心，不用担心，这样做的原因是中间节点需要向右旋转一次，然后将上面的节点向左旋转才能平衡。详情可以在下方慢慢阅读。造成这种不平衡情况的第一个原因是ROOT节点右侧的左节点深度更高，使得与左侧的差值大于1。这与我们看到的左手右手不同更早是因为旋转一圈无法达到平衡！对于左右结构，中间（R）最大，两侧（ROOT，R.L）最小，但底部（R.L）大于顶部（ROOT）（R.L在右侧ROOT的），所以如果是平衡的，那么R.L应该在中间，而R应该在右边，而原来的ROOT在左边。这个过程中节点的变化比较大，需要妥善处理每个子节点的移动，使其符合二叉排序树的属性！这种双轮转其实并不难实现。不要被外表所迷惑。我在这里提供双重旋转。两种方法解决。思路（标准答案）1：将RR和LL旋转两次很好处理，因为RR（左旋转）和LL（右旋转）的问题之前已经解决了，所以直接在多于。首先，R节点将LL向右旋转一次。旋转一圈后，R在最右边。这转化为RR不平衡旋转的问题。所以这时候用ROOT向左启动RR就可以完成平衡了。具体过程可以参考下图。思路（个人方法）2：直接根据initial和result分析状态，然后分析每个节点的变化顺序=，手动操作这些节点即可。其实不管你怎么操作，只要最终的结构满足就可以了！首先根据ROOT三个节点的变化，R，R.L，R.L一定在最顶层，left和right分别指向ROOT和R，然后其中R.left，ROOT。右变化（原来分别是R.L和R）暂时为空。而只要根据左右大小关系，就可以将R.L的原有子节点A和B相加。代码为：（注释部分为方案1）privatenodegetRLbanlance(nodeoldroot){//rightleftdeep//nodenewroot=oldroot.right.left;//oldroot.right.left=newroot.right;//newroot.right=oldroot.right;//oldroot.right=newroot.left;//newroot.left=oldroot;//oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;//新根。right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1;//newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//需要从新的金酸中改变原根的高度oldroot.right=getLLbanlance(oldroot.right);oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;returngetRRbanlance(oldroot);}LR平衡旋转（先左后右双旋转）这种情况和RL的情况类似，只是采取相同的操作。根据上面的RL修改，这部分代码为)+1;returngetLLbanlance(oldroot);}代码先实现节点的多个高度属性。用于计算高度（平衡因子）的插入是递归插入。递归是一个来回的过程。going进程插入，returning进程用于更新高度，检查是否平衡。高度的全局递归计算建议不要写，效率太低。事实上，高度变化只与插入和平衡有关。仔细想想，不会有遗漏的！代码写得比较早，如有不规范的命名，请勿喷。importjava.util.ArrayDeque;importjava.util.Queue;publicclassAVLTree{classnode{intvalue;nodeleft;noderight;inheight;publicnode(){}publicnode(intvalue){this.value=value;this.height=0;}publicnode(intvalue,nodeleft,noderight){this.value=value;this.left=left;this.right=right;this.height=0;}}noderoot;//rootpublicAVLTree(){这。root=null;}publicbooleanisContains(intx)//有没有{nodecurrent=root;if(root==null){returnfalse;}while(current.value!=x&¤t!=null){if(x
