平衡二叉树概述
上一篇讲过的二叉排序树，使在二叉树中查找结点变得比较快，但也会有个别情况，例如：
int[] arr = new int[]{1,2,3,4,5,6,7,};
像这种有序数组组成的二叉树就会是这样
而这样的二叉树查找并不会比其他的查找方式更快。因此，针对二叉排序树的这一短板，平衡二叉树在二叉排序树的基础上做了优化。
平衡二叉树：也叫AVL数，本质上也是一棵二叉排序树，但是它所做的优化是：每个结点的左右子树高度差不超过1，所以无论你是有序还是无序的，最终结果都不会出现上图的情况。
单旋转
当二叉排序树出现左右子树不平衡时，就会利用单旋转来改变树结构使其平衡，所以单旋转的基础就是二叉排序树的遍历添加节点的过程
public class BinarySortTreeNode {int value;BinarySortTreeNode left;BinarySortTreeNode right;public BinarySortTreeNode(int value) {this.value = value;}public void middleShow(){if (left != null){left.middleShow();}System.out.println(this.value);if (right != null){right.middleShow();}}/***返回当前树的高度* @return*/public int TreeHight(){return Math.max(left==null?0:left.TreeHight(),right==null?0:right.TreeHight())+1;}/*** 返回左子树的高度* @return*/public int leftHight(){if (left == null){return 0;}return left.TreeHight();}/*** 返回右子树的高度* @return*/public int rightHight(){if (right == null){return 0;}return right.TreeHight();}/*** 添加结点的方法* @param node*/public void add(BinarySortTreeNode node) {//如果传入的节点为空，则直接返回if (node == null){return;}//如果不为空，咋将当前结点与传入结点的值作比较if (node.value<this.value){//如果传入结点比当前结点小，则作为当前节点的左子结点if (this.left == null){//如果当前结点的左子结点为空，则直接作为当前结点的左子结点this.left = node;}else {//如果不为空，则继续向左子结点递归this.left.add(node);}}else{//如果传入结点比当前结点大，则作为当前结点的右子结点if (this.right == null){//如果右子结点为空，则直接作为右子结点this.right = node;}else {//如果不为空，则继续向右子结点递归this.right.add(node);}}//查询是否左右子树高度相差大于1，如果是，则进行左右旋转if (leftHight()-rightHight()>=2){//如果左子树比右子树高，进行右旋转rightRotate();}if (rightHight()-leftHight()>=2){//相反则进行左旋转leftRotate();}}private void leftRotate() {//创建一个值为当前结点值的新结点BinarySortTreeNode newNode = new BinarySortTreeNode(value);//将新结点的右子树设置为当前结点的右子树的左子树newNode.right = right.left;//将新结点的左子树设置为当前结点的左子树newNode.left = left;//当前值改为其右子树的值value = right.value;//当前值的右子树改为右子树的右子树right = right.right;//当前点的左子树设置为新结点left = newNode;}/*** 右旋转*/private void rightRotate() {//首先创建一个新结点,值等于当前结点的值BinarySortTreeNode newNode = new BinarySortTreeNode(value);//把新结点的右子树设置成当前结点的右子树newNode.right = right;//把新结点的左子树设置成当前结点的左子树的右子树newNode.left = left.right;//把当前值换成左子结点的值value = left.value;//把当前结点的左子树设置成左子树的左子树left = left.left;//把当前结点的右子树设置为新结点right = newNode;}}
双旋转
如果一个平衡二叉树突然插入一个如图所示的结点，那么你会发现单纯的进行一次单旋转并不能将其转换为平衡二叉树，这时就用到了双旋转，即在单旋转判断的基础上再加一层判断
//查询是否左右子树高度相差大于1，如果是，则进行左右旋转if (leftHight()-rightHight()>=2){//如果左子树比右子树高，且出现左子树的左子子树比右子子树小，进行双旋转if (left!=null&&left.leftHight()<left.rightHight()){left.leftRotate();rightRotate();}//正常则单旋转rightRotate();}if (rightHight()-leftHight()>=2){//相反则进行双旋转或左旋转if (right!=null&&right.rightHight()<right.leftHight()){right.rightRotate();leftRotate();}leftRotate();}
