上一篇文章我们已经讲到二叉排序树，相信大家经过学习后，对树这种较为复杂但是开销小效率高的数据结构有了一些了解，但是二叉排序树依旧存在着一些问题，在某些特殊情况下，它的操作也相对不会那么简便，我们来看这样一个二叉排序树
如果在上面这个二叉排序树中查找9这个结点，则要将整个结点都遍历一遍，时间复杂度就变成了O(n)，几乎就是一个链表了，甚至比链表开销还大，因为它还要判断左子树是否为空。
这时候可能有小伙伴就发现了一件事情：插入的数据如果越有序，则形成的二叉排序树越接近链表。
为了防止这种情况的出现，平衡二叉树横空出世了。平衡二叉树，即树的两端看起来是平衡的，让树左右两边的节点数尽可能一样多。将上面这棵树进行平衡之后结构如下所示：
基本介绍平衡二叉树，又称AVL树，可以保证查询效率较高
他是一棵空树，或是左右两个子树的高度差不超过1，并且左右子树也是平衡二叉树
平衡二叉树是如何实现平衡的呢？三种方法：在插入或删除时左旋转、右旋转和双旋转
2、计算AVL树的高度当前结点的高度
从当前结点开始，循环递归往下遍历，每次返回左子树和右子树的最大值，每次递归完成进行+1
publicintheight(){returnMath.max(left==null?0:left.height(),right==null?0:right.height())+1;}
计算左子树的高度
判断左子结点是否为空，是则返回0
否则，调用左子树的高度
publicintheightLeft(){if(left==null){return0;}returnleft.height();}
计算右子树的高度
判断右子节点是否为空，是则返回0
否则，调用右子树的高度
publicintheightRight(){if(right==null){return0;}returnright.height();}3、左旋转
根据以下图片（左）可以发现，右子树的高度为3，左子树的高度为1，右子树的高度减去左子树的高度大于1，因此这不是一棵平衡二叉树，所以我们需要对这棵树进行左旋转，让它平衡。
根据根节点创建一个新结点newNode（如下图，创建节点4）
让newNode的右子节点指向根节点的右节点的左节点（即5），左节点指向根节点的左节点（即3）
将根节点替换为根节点的右节点（即6）
将新根节点的右子节点指向根节点的右子节点的有自己点（即7）
将根节点的左子节点指向newNode
/***左旋转*/publicvoidleftRotate(){//根据根节点创建一个新结点Nodenode=newNode(value);//把新结点的左子树设置成当前结点的左子树node.left=left;//把新结点的右子树设置成当前结点的右子树的左子树node.right=right.left;//把当前结点的值替换成右子结点的值value=right.value;//把当前结点的右子树设置成当前结点右子树的右子树right=right.right;//把当前结点的左子树设置成新结点left=node;}4、右旋转
右旋转和左旋转有着异曲同工之妙，只是它们旋转的方向不同，当左子树的高度比右子树的高度多于2的时候，我们需要进行右旋转
复制一个根节点10为newNode
让newNode的左子节点指向根节点的左子节点的右子节点
让newNode的右子节点指向根节点的右子节点
让根节点的左子节点成为新根节点
让新根节点的右节点指向newNode
/***右旋转*/publicvoidrightRotate(){Nodenode=newNode(value);node.right=right;node.left=left.right;value=left.value;left=left.left;right=node;}5、双旋转
只进行一次左旋转或是右旋转，有时候是不足以将一颗二叉排序树转化为平衡二叉树的。如下图所示，二叉树的左子树比右子树高出2个层次，因此需要进行右旋转，但是经过右旋转之后我们发现，这依旧不是一个平衡二叉树。
实际上，右旋转的本质是将左子树的右子树移到右子树的部分去，也就是将7和8移动到右子树去，因此，如果左子树的左子树比右子树高度高的话，那没有什么问题，但是右子树比左子树高了，那么问题就出现了。
所以，我们需要对左子树进行左旋转，再对整棵树进行右旋转。
而对于与之相反的树，也是相同的操作，这就是双循环。如图所示：
我们在添加的方法中加入判断
在进行左旋转时：
如果右子树的左子树高度大于右子树的右子树高度，则先对右子树进行右旋转
进行右旋转时：
如果左子树的右子树高度大于左子树的左子树的高度，则先对左子树进行左旋转
//当添加完一个节点时候，就应该判断是否失去平衡if(heightRight()-heightLeft()1){//如果右子树的左子树高度大于右子树的右子树高度，则对右子树进行右旋转if(right!=nullright.heightLeft()right.heightRight()){right.rightRotate();}leftRotate();}elseif(heightRight()-heightLeft()-1){//如果左子树的右子树高度大于左子树的左子树的高度，则对左子树进行左旋转if(left!=nullleft.heightRight()left.heightLeft()){left.leftRotate();}rightRotate();}
如果我们想要在插入结点、删除结点的时候时刻保持着这一棵树为平衡二叉树，我们只需要在插入和删除的方法的末尾添加上判断以及旋转的方法，保证每次插入和删除时进行平衡二叉树的旋转就可以了。