对于二叉查找树,树的层数(深度)越少,查找数据的平均查找时间就会越少。二叉排序树在很多情况下都不能保证树的高度是最优的,例如在极端情况,如果插入排序树的数据是有序的,那么二叉树就会退化成为单链,这时查找的时间复杂度也退化成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
评论区