侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 285 篇文章
  • 累计创建 125 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

平衡二叉树的实现之AVL树

孔子说JAVA
2019-11-05 / 0 评论 / 0 点赞 / 68 阅读 / 8,771 字 / 正在检测是否收录...

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

image-1649583723023

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

image-1649583746231

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

3、不平衡的4种情况

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

3.1 左左情况

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

image-1649583805999

因此可以看出,新的左子树的左子树为原不平衡节点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 左右情况

image-1649583871567

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

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

所以结论就是:

  1. 根节点的值是:不平衡点的左子树的右子树的值
  2. 根的左子树节点是:不平衡点的左子树的值
  3. 根的右子树节点是:不平衡点的值
  4. 新左子树的左子树是:不平衡点的左子树的左子树
  5. 新左子树的右子树是:不平衡点左子树的右子树的左子树
  6. 新右子树的左子树是:不平衡点左子树的右子树的右子树
  7. 新右子树的右子树是:不平衡点的右子树

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
0

评论区