对于二叉查找树，树的层数(深度)越少，查找数据的平均查找时间就会越少。二叉排序树在很多情况下都不能保证树的高度是最优的，例如在极端情况，如果插入排序树的数据是有序的，那么二叉树就会退化成为单链，这时查找的时间复杂度也退化成O(n)的了。为了解决这个问题，我们希望二叉树是尽量平衡的，也就是说对于树中的任意一个结点，都能使其左子树上结点的个数和右子树上结点的个数相差不太多。有两种不同的二叉平衡树，分别是AVL树和红黑树。

1、平衡二叉树的概念

平衡二叉树，要求左右子树的深度差别不超过1，且左右子树都是平衡二叉树。换句话说，就是对于树中的任意一个结点，都有该结点的左子树的高度与右子树的高度之差的绝对值小于2。（二叉树的定义总是充满了递归味）

平衡二叉树有多种实现方式，最常见的就有AVL树以及红黑二叉树，AVL树是最早被发明的平衡二叉树。

平衡二叉树的目的是对二叉查找树进行平衡化，以保证树的高度比较优化，从而保证了对树进行操作的时间复杂度不会退化。虽然在实际应用中，平衡二叉树没有红黑树那么普遍，但平衡二叉树中提出的结点旋转的概念是自平衡树的基础。

2、AVL树如何实现自平衡

所谓自平衡，就是在节点发生修改的时候，自己完成树平衡的调整。

平衡因子：每个结点的平衡因子就是该结点的左子树的高度减去右子树的高度，平衡二叉树的每个结点的平衡因子的绝对值不会超过2。

接下来，看两个实际的例子，考虑顺序向二叉查找树中插入数据5,3,6,2,4,1，所得到的二叉查找树的形状如图 2.12(a) 所示。对于数据为 5 的这个结点，它的左子树高度与右子树高度之差为 2，我们可以通过改变5号结点和3号结点的相关指针将其变为如图 2.12(b) 所示的形状。由于3号结点的右孩子指针指向了5号结点，4号结点暂时脱离了二叉树，但注意到5号结点的左孩子指针变为空，我们可以将4号结点挂在5号结点的左孩子上，得到如图 2.12© 。这样，整棵树还继续满足平衡二叉树的性质。这个操作就像把树像旋纽一样向右旋转了下，我们把这个操作形象地称为右旋。

右旋的口诀可以简单总结为“左子作父，父为右子，右孙变左孙”。由此可见，右旋操作的效果是原来的右孩子的深度(注意不是高度)加1，左孙的深度减1，而右孙的深度不变。而左旋的情况与右旋互为镜像，不再赘述。

如果插入的顺序变成了5,2,6,1,3,4，所得到的二叉查找树的形状则如图 2.13(a) 所示。此时，5号结点的左子树与右子树的高度差仍然为2，这时再执行右旋行不行呢？我们可以尝试着做一下，右旋的结果如图 2.13(b) 所示，这时，新的树根2号结点的平衡因子为-2，显然直接右旋并没有使树重新平衡。这是因为右旋时右孙变左孙以后，深度没有变化，而显然造成树不平衡的主要原因在于右孙3号结点的深度过大。为了解决这个问题，尝试把它转化为第一个例子，就是对2号结点进行一次左旋，得到图 2.13© 。这样会使得右孙的深度转移到左孙。现在树的形状与上例相同了，再对这棵树进行右旋操作，会使得左孙深度减1，右孙不变。得到新的树是满足平衡二叉树的性质的，如图 2.13(d) 。

通过上面的两个例子，我们可以找出规律了。当向一棵平衡二叉树中插入一个新的结点时，有可能会使得某个结点的子树高度发生变化，从而影响了这个结点的平衡因子。当该结点的平衡因子为2时，就应该考虑对该点执行右旋操作。在执行右旋之前，还要检查一下左子树上的左孙和右孙的高度，如果是左孙的高度比较大，那么直接右旋就可以重新平衡，如果是右孙的高度比较大，那么就要在左孩子结点上先执行一次左旋。

3、不平衡的4种情况

不平衡的四种情况即，左左，左右，右左，右右四种。其实不管怎么转，其实只是重新改变不平衡节点的左右子树，因此，我们只需要记住不平衡节点的左右子树的左右子树分别该如何得到，就可以。

3.1 左左情况

因为左边的过长，所以要把左边的过长的部分从中间折断，这样就可以把3层节点来弄成两层，这样就可以平衡。

因此可以看出，新的左子树的左子树为原不平衡节点K2的左子树的左子树的左子树。新的右子树的左子树为不平衡点的左子树的右子树，新右子树的右子树为不平衡点的右子树，右子树的节点为不平衡节点的值，不平衡点值为原不平衡点左子树的值。

BalancedBinaryNode newleftnode=balancedBinaryNode.left.left;
BalancedBinaryNode newrightnode=new BalancedBinaryNode();
newrightnode.left=balancedBinaryNode.left.right;
newrightnode.right=balancedBinaryNode.right;
newrightnode.data=balancedBinaryNode.data;
balancedBinaryNode.data=balancedBinaryNode.left.data;
balancedBinaryNode.left=newleftnode;
balancedBinaryNode.right=newrightnode;

分析： 因为左边过长，所以要折半，即把不平衡点左子树的值作为这部分树的根，那么，根的左子树，也就是新的左子树，所有值都比根要小，而新的右子树要比根大。所以，比根小的只有根的左子树比他小，所以：新的左子树就是新根原来的左子树：即BalancedBinaryNode newleftnode=balancedBinaryNode.left.left;。剩下的三部分很好理解，新根原来的右子树、原根的右子树、原根的大小关系，很明显：新根原来的右子树<原根<原根的右子树，所以将原根作为新根的右子树，也就是新的右子树，将新根的右子树作为新右子树的左子树，将原根的右子树作为新子树的右子树。

3.2 右右情况

与左左情况原理相同，只需要左换右即可

3.3 左右情况

说实话，这个做法很完美，但是，理解起来有点困难，尤其是没空间想象能力较差。那我们现在来看一看能不能从结果找到什么。

首先，既然是左右了，那么一定是存在不平衡点、不平衡点左孩子、不平衡点左孩子的有孩子（原因是左右就是左子树的右子树插入孩子），很显然大小关系：不平衡点左孩子<不平衡点左孩子的右孩子<不平衡点，所以平衡成一颗新树就是新根节点一定是不平衡节点的左孩子的右孩子，那么新左子树是不平衡点的左孩子，新右子树是不平衡点 ok，来看左右子节点的左右子树分别是啥，先看新左子树的左子树，比新左子树小的只有原来树中比它小的，那就是原树种不平衡点左子树（新左子树）的左子树，同理，新右子树的右子树就是原不平衡点（新右子树）的右子树。现在还剩下不平衡点的左子树的右子树（新根节点）的左右子树，先看左子树，小于新根节点，所以只能是位于新左子树的一部分，但是，它由于属于新左子树原来右子树的一部分，所以大于新左子树，所以为左子树的右子树，同理，新根节点的原右子树就是右子树的左子树。

所以结论就是：

根节点的值是：不平衡点的左子树的右子树的值

根的左子树节点是：不平衡点的左子树的值

根的右子树节点是：不平衡点的值

新左子树的左子树是：不平衡点的左子树的左子树

新左子树的右子树是：不平衡点左子树的右子树的左子树

新右子树的左子树是：不平衡点左子树的右子树的右子树

新右子树的右子树是：不平衡点的右子树

BalancedBinaryNode newleftnode=new BalancedBinaryNode();
BalancedBinaryNode newrightnode=new BalancedBinaryNode();
newleftnode.data=balancedBinaryNode.left.data;
newleftnode.left=balancedBinaryNode.left.left;
newleftnode.right=balancedBinaryNode.left.right.left;
newrightnode.data=balancedBinaryNode.data;
newrightnode.left=balancedBinaryNode.left.right.right;
newrightnode.right=balancedBinaryNode.right;
balancedBinaryNode.data=balancedBinaryNode.left.right.data;
balancedBinaryNode.left=newleftnode;
balancedBinaryNode.right=newrightnode;

3.4 右左情况

右左理解方式一样。

4、AVL树代码实现

public class BalanceBinaryTree {
	public static class BalancedBinaryNode{
		public int data;
		public BalancedBinaryNode left;
		public BalancedBinaryNode right;
		public int ceng ;
		public int du;
	}
	public static BalancedBinaryNode init(int data){
		BalancedBinaryNode root=new BalancedBinaryNode();
		root.data=data;
		root.left=null;
		root.right=null;
		root.du=0;
		return root;
	}
	public static void add(BalancedBinaryNode root,int data){
		BalancedBinaryNode temp=root;
		BalancedBinaryNode newNode=new BalancedBinaryNode();
		newNode.left=null;newNode.right=null;newNode.data=data;
		while(true){
			if(data<temp.data){
				if(temp.left!=null){
					temp=temp.left;
				}else{
					temp.left=newNode;
					return ;
				}
			}else if(data>temp.data){
				if(temp.right!=null){
					temp=temp.right;
				}else{
					temp.right=newNode;
					return ;
				}
			}else{
				return;
			}
		}
		
	}
	public static void balance(BalancedBinaryNode root,int data){
		Queue<BalancedBinaryNode> queue=new LinkedList<>();
		if(root==null){
			return ;
		}
		queue.add(root);
		root.ceng=1;
		BalancedBinaryNode balancedBinaryNode;
		while(queue.size()!=0){
			balancedBinaryNode=queue.poll();
			int leftheaght=balancedBinaryNode.left==null?0:getDu(balancedBinaryNode.left);
			int rightheaght=balancedBinaryNode.right==null?0:getDu(balancedBinaryNode.right);
			//该节点平衡
			if(Math.abs(leftheaght-rightheaght)<2){
				if(balancedBinaryNode.left!=null){
					queue.add(balancedBinaryNode.left);
				}
				if(balancedBinaryNode.right!=null){
					queue.add(balancedBinaryNode.right);
				}
			}
			//否则不平衡
			else{
				
				if(leftheaght>rightheaght){
					if(data<balancedBinaryNode.left.data){
						leftAndLeft(balancedBinaryNode);
					}else{
						leftandright(balancedBinaryNode);
					}
				}else{
					if(data<balancedBinaryNode.right.data){
						System.out.println("右左");
						rightandleft(balancedBinaryNode);
					}else{
						rightandright(balancedBinaryNode);
					}
				}
			}
		}
	}
	//左左的平衡
	public static void leftAndLeft(BalancedBinaryNode balancedBinaryNode){
		BalancedBinaryNode newleftnode=balancedBinaryNode.left.left;
		BalancedBinaryNode newrightnode=new BalancedBinaryNode();
		newrightnode.left=balancedBinaryNode.left.right;
		newrightnode.right=balancedBinaryNode.right;
		newrightnode.data=balancedBinaryNode.data;
		balancedBinaryNode.data=balancedBinaryNode.left.data;
		balancedBinaryNode.left=newleftnode;
		balancedBinaryNode.right=newrightnode;
	}
	//右右的平衡
	public static void rightandright(BalancedBinaryNode balancedBinaryNode){
		BalancedBinaryNode newleftnnode=new BalancedBinaryNode();
		BalancedBinaryNode newrightnode=balancedBinaryNode.right.right;
		newleftnnode.left=balancedBinaryNode.left;
		newleftnnode.right=balancedBinaryNode.right.left;
		newleftnnode.data=balancedBinaryNode.data;
		balancedBinaryNode.data=balancedBinaryNode.right.data;
		balancedBinaryNode.left=newleftnnode;
		balancedBinaryNode.right=newrightnode;
	}
	//左右的平衡
	public static void leftandright(BalancedBinaryNode balancedBinaryNode){
		BalancedBinaryNode newleftnode=new BalancedBinaryNode();
		BalancedBinaryNode newrightnode=new BalancedBinaryNode();
		newleftnode.data=balancedBinaryNode.left.data;
		newleftnode.left=balancedBinaryNode.left.left;
		newleftnode.right=balancedBinaryNode.left.right.left;
		newrightnode.data=balancedBinaryNode.data;
		newrightnode.left=balancedBinaryNode.left.right.right;
		newrightnode.right=balancedBinaryNode.right;
		balancedBinaryNode.data=balancedBinaryNode.left.right.data;
		balancedBinaryNode.left=newleftnode;
		balancedBinaryNode.right=newrightnode;
	}
	//右左的旋转
	public static void rightandleft(BalancedBinaryNode balancedBinaryNode){
		BalancedBinaryNode newleftnode=new BalancedBinaryNode();
		BalancedBinaryNode newrightnode=new BalancedBinaryNode();
		newleftnode.data=balancedBinaryNode.data;
		newleftnode.left=balancedBinaryNode.left;
		newleftnode.right=balancedBinaryNode.right.left.left;
		newrightnode.data=balancedBinaryNode.right.data;
		newrightnode.left=balancedBinaryNode.right.left.right;
		newrightnode.right=balancedBinaryNode.right.right;
		balancedBinaryNode.data=balancedBinaryNode.right.left.data;
		balancedBinaryNode.left=newleftnode;
		balancedBinaryNode.right=newrightnode;
		
		
	}
	//获得某个节点的度
	public static int getDu(BalancedBinaryNode binaryNode){
		int result=0;
		if(binaryNode.left==null && binaryNode.right==null){
			result=1;
		}else if(binaryNode.left==null){
			result=1+getDu(binaryNode.right);
 
		}else if(binaryNode.right==null){
			result=1+getDu(binaryNode.left);
		}else{
			result=1+Math.max(getDu(binaryNode.left),getDu(binaryNode.right));
 
		}
		return result;
	}
	//
	public static void show(BalancedBinaryNode root){
		Queue<BalancedBinaryNode> queue=new LinkedList<>();
		if(root==null){
			System.out.println("空的");
			return ;
		}
		queue.add(root);
		root.ceng=1;
		BalancedBinaryNode balancedBinaryNode;
		while(queue.size()!=0){
			balancedBinaryNode=queue.poll();
			if(balancedBinaryNode.left!=null){
				balancedBinaryNode.left.ceng=balancedBinaryNode.ceng+1;
				queue.add(balancedBinaryNode.left);
			}
			if(balancedBinaryNode.right!=null){
				balancedBinaryNode.right.ceng=balancedBinaryNode.ceng+1;
				queue.add(balancedBinaryNode.right);
			}
			System.out.println("数据为："+balancedBinaryNode.data+" 所在层数 "+balancedBinaryNode.ceng);
		}
	}
	
	public static void main(String args[]) {
		int data[]={62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
//		int data[]={1,2,3,4,5,6,7,8};
		BalancedBinaryNode root=BalanceBinaryTree.init(data[0]);
		for(int i=1;i<data.length;i++){
			BalanceBinaryTree.add(root, data[i]);
			BalanceBinaryTree.balance(root,data[i]);
		}
		BalanceBinaryTree.show(root);
	}
}

// 右左
// 数据为：58 所在层数 1
// 数据为：47 所在层数 2
// 数据为：88 所在层数 2
// 数据为：35 所在层数 3
// 数据为：51 所在层数 3
// 数据为：73 所在层数 3
// 数据为：99 所在层数 3
// 数据为：37 所在层数 4
// 数据为：62 所在层数 4
// 数据为：93 所在层数 4

目录CONTENT

平衡二叉树的实现之AVL树