对于二叉查找树，树的层数(深度)越少，查找数据的平均查找时间就会越少。二叉排序树在很多情况下都不能保证树的高度是最优的，例如在极端情况，如果插入排序树的数据是有序的，那么二叉树就会退化成为单链，这时查找的时间复杂度也退化成O(n)的了。为了解决这个问题，我们希望二叉树是尽量平衡的，也就是说对于树中的任意一个结点，都能使其左子树上结点的个数和右子树上结点的个数相差不太多。有两种不同的二叉平衡树，分别是AVL树和红黑树。
平衡二叉树的概念
平衡二叉树，要求左右子树的深度差别不超过1，且左右子树都是平衡二叉树。换句话说，就是对于树中的任意一个结点，都有该结点的左子树的高度与右子树的高度之差的绝对值小于2。（二叉树的定义总是充满了递归味）
平衡二叉树有多种实现方式，最常见的就有AVL树以及红黑二叉树，AVL树是最早被发明的平衡二叉树。
平衡二叉树的目的是对二叉查找树进行平衡化，以保证树的高度比较优化，从而保证了对树进行操作的时间复杂度不会退化。虽然在实际应用中，平衡二叉树没有红黑树那么普遍，但平衡二叉树中提出的结点旋转的概念是自平衡树的基础。
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(c) 。这样，整棵树还继续满足平衡二叉树的性质。这个操作就像把树像旋纽一样向右旋转了下，我们把这个操作形象地称为右旋。
右旋的口诀可以简单总结为“左子作父，父为右子，右孙变左孙”。由此可见，右旋操作的效果是原来的右孩子的深度(注意不是高度)加1，左孙的深度减1，而右孙的深度不变。而左旋的情况与右旋互为镜像，不再赘述。
如果插入的顺序变成了5,2,6,1,3,4，所得到的二叉查找树的形状则如图 2.13(a) 所示。此时，5号结点的左子树与右子树的高度差仍然为2，这时再执行右旋行不行呢？我们可以尝试着做一下，右旋的结果如图 2.13(b) 所示，这时，新的树根2号结点的平衡因子为-2，显然直接右旋并没有使树重新平衡。这是因为右旋时右孙变左孙以后，深度没有变化，而显然造成树不平衡的主要原因在于右孙3号结点的深度过大。为了解决这个问题，尝试把它转化为第一个例子，就是对2号结点进行一次左旋，得到图 2.13(c) 。这样会使得右孙的深度转移到左孙。现在树的形状与上例相同了，再对这棵树进行右旋操作，会使得左孙深度减1，右孙不变。得到新的树是满足平衡二叉树的性质的，如图 2.13(d) 。
通过上面的两个例子，我们可以找出规律了。当向一棵平衡二叉树中插入一个新的结点时，有可能会使得某个结点的子树高度发生变化，从而影响了这个结点的平衡因子。当该结点的平衡因子为2时，就应该考虑对该点执行右旋操作。在执行右旋之前，还要检查一下左子树上的左孙和右孙的高度，如果是左孙的高度比较大，那么直接右旋就可以重新平衡，如果是右孙的高度比较大，那么就要在左孩子结点上先执行一次左旋。
不平衡的4种情况
不平衡的四种情况即，左左，左右，右左，右右四种。其实不管怎么转，其实只是重新改变不平衡节点的左右子树，因此，我们只需要记住不平衡节点的左右子树的左右子树分别该如何得到，就可以。
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;。剩下的三部分很好理解，新根原来的右子树、原根的右子树、原根的大小关系，很明显：新根原来的右子树<原根<原根的右子树，所以将原根作为新根的右子树，也就是新的右子树，将新根的右子树作为新右子树的左子树，将原根的右子树作为新子树的右子树。
2、右右情况
与左左情况原理相同，只需要左换右即可
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;
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
