AVL平衡二叉树

时间:2021-12-30 17:30:13

平衡二叉树定义

AVL树也就是所谓的平衡二叉树,查找、删除、插入最坏情况下为O(log n),维持树的平衡只需要几次旋转即可。保证任意一个节点的左子树高度与右子树高度相差不大于1,默认树为空时高度为0。

节点结构

为了后续操作简洁性,先给出节点结构

final class node{
	int value=0;//键值
	int height=1;//节点高度
	node left=null;//左右孩子
	node right=null;
	node(int value){
		this.value=value;
	}
}

旋转类型

维持平衡的操作就是树的旋转,旋转类型可以分为四种:

1.右旋LL类型


AVL平衡二叉树


单个右旋,将k1的右子树作为k2的左子树,k2作为k1的右子树。该操作只是对于k1,k2进行,所以X,Y,X子树的高度不变,在旋转完成后,只需更新k1,k2高度即可

node l_l_rotate(node root){//LL旋转
		node temp=root.left;//将左节点拿出来
		root.left=temp.right;
		temp.right=root;
		root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新原root的height
		root=temp;
		root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新新root的height
		return root;
	}

简单说就是,将节点的左节点的右子树作为节点的左子树,节点作为其原来左节点的右子树。

2.左旋RR性


AVL平衡二叉树


跟右转刚好反过来,k2的左子树作为k1的右子树,k1作为k2的左子树。跟上面一样,更改完成后,更新k1,k2的高度即可

node r_r_rotate(node root){//RR旋转
		node temp=root.right;//将右节点拿出来
		root.right=temp.left;
		temp.left=root;
		root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新原root的height
		root=temp;
		root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新新root的height
		return root;
	}

节点的右节点的左子树作为节点的右子树,节点作为其原来右节点的左子树。

3.先左旋再右旋LR


AVL平衡二叉树


两次操作而已,k1,k2执行RR旋转,然后对k3执行LL右旋操作。

node l_r_rotate(node root){//LR旋转
		root.left=r_r_rotate(root.left);//先RR旋转
		return l_l_rotate(root);//再LL旋转
	}

4.先右旋再左旋RL


AVL平衡二叉树


先对k3,k2执行LL右旋,再对k1执行RR左旋操作。

node r_l_rotate(node root){//RL旋转
		root.right=l_l_rotate(root.right);//先LL旋转
		return r_r_rotate(root);//再LL旋转
	}

(用LL表示右旋操作,是因为LL表示的是结构上是个“左边形”,所以要向右旋转)

判断旋转操作

node check(node root){//检查高度,判断是否需要旋转操作
		root.height=(Math.max(get_height(root.left),get_height(root.right))+1);//更新节点高度
		if(get_height(root.left)-get_height(root.right)==2){//左边增高了
			if(get_height(root.left.left)>=get_height(root.left.right)){//LL型
				root=l_l_rotate(root);//LL旋转
			}else{//LR型
				root=l_r_rotate(root);//LR旋转
			}
		}else if(get_height(root.right)-get_height(root.left)==2){//右边增高了
			if(get_height(root.right.left)>get_height(root.right.right)){//RL型
				root=r_l_rotate(root);//RL旋转
			}else{//RR型
				root=r_r_rotate(root);//RR旋转
			}
		}
		return root;
	}

判断很简单,在插入或者删除操作之后,在从根节点到操作的(插入或删除)的那个节点的这条路径上,更新该路径上的节点的高度,并判断是否需要旋转操作来维持平衡。

插入节点操作

从根节点开始到插入位置的这条路径上,在插入节点操作完成之后之后,需要依次从下(插入节点)向上,更新每个该路径上的节点的高度(height属性)信息,借助上面的check函数,在需要旋转的情况下判断条件,进行旋转操作。

由此可知,插入操作需要以递归函数的方式进行。原因如下:

1.建立新插入的节点与原有节点(父节点)之间的引用关系

例如,待插入节点的value值小于root节点时:root.left=insert(root.left,value);将新建立的节点作为其父节点的左子节点,建立联系。

2.回退时更新父节点的高度(height属性)信息

在完成最底层,带插入位置的插入操作之后,即root.left=new node(value);进行root节点的高度更新

参考代码:

node insert(node root,int value){//插入节点
		if(root==null){//找到插入位置
			node t=new node(value);//创建该节点
			return t;
		}
		if(root.value==value){//相等就算了,不过此处没有优化,相等的节点上层仍需要check检查
			System.out.println("already exists");
			return root;
		}
		if(value<root.value){//左子树上创建节点
			root.left=insert(root.left,value);
			
		}else{//右子树上创建节点
			root.right=insert(root.right,value);
		}
		root=check(root);//检查高度,判断是否需要旋转操作
		return root;
	}

删除节点操作

删除节点有两个情况

1.待删除的节点具有左子树和右子树

这种情况下待删除的节点可以看做是个官二代,要把他删除了,但有权有势的人家直接找了个替罪羊,自己改个名字照样活的自在。真实情况应该是,将节点删除,在其左子树和右子树中,选择较高的一个子树的极值,放于删除节点出,无图无真相

AVL平衡二叉树


要删除节点5,则在节点5左子树和右子树中选择较高的一个,这里一样高就随便选了,比如选择右子树,则选择右子树的最小值,即6,放到节点5的位置上;如果选择左子树,则选择最大值,即3,放到5的位置上。然后删除选择的6或者3节点。所以可以看出来,这操作其实根本就不是删除5,而是删除左子树的最大值或者右子树的最小值,5节点一直存在,不过就是换个value值而已,对象不变。

这样的好处,一个是操作简单,不用创建新对象,直接在原对象上修改即可,另外就是可以在删除操作中维持二叉树的平衡,不需要进行旋转操作(当然更新高度还是要有的)

2.待删除的节点不同时具有左子树和右子树

当然不可能每个节点都是官二代,待删除的节点可能是叶子节点或者只有一个子树不为空的节点,此时就需要放弃节点对象了。

删除操作仍然是以递归的形式进行的,原理相同,从根到待删除的节点,在该影响路径上,由下向上依次递归更新。在从根节点找到官二代节点的情形中,同样如此,不过就是换个方向继续向下而已,所以方式一致。

参考代码:

node delete(node root,int value){//根据值来删除节点
		if(root==null){//即使没找到也会check检查height
			System.out.println("not found");
			return null;
		}
		if(value<root.value){//左子树上去找
			root.left=delete(root.left,value);
		}else if(value>root.value){//右子树上去找
			root.right=delete(root.right,value);
		}else{//找到了
			if(root.left!=null&&root.right!=null){//左右都不等于null,删除之后仍然平衡
				if(root.left.height>root.right.height){//只是需要更新height
					root.value=max(root.left);//取左子树最大值
					root.left=delete(root.left,root.value);//删除该最大值
				}else{
					root.value=min(root.right);//取右子树最小值
					root.right=delete(root.right,root.value);//删除该最小值
				}
			}else{//左右子树部分或者全部为null
				root=(root.left!=null?root.left:root.right);
				return root;
			}
		}
		root=check(root);
		return root;
	}

参考示例:

建立平衡二叉树:1,2,3,7,8,9,4,5,6

删除:4,6

AVL平衡二叉树

插入3节点时,RR旋转

AVL平衡二叉树

插入8节点时,RR旋转

AVL平衡二叉树

插入9节点,RR旋转

AVL平衡二叉树

AVL平衡二叉树

添加6节点后,RR左旋

删除4,6操作

AVL平衡二叉树

删除6节点,LL右旋

参考代码:

public class t{
	public static void main(String[] args){
		int[] arr=new int[]{1,2,3,7,8,9,4,5,6};
		tree tr=new tree();
		for(int i:arr){
			tr.insert(i);
		}
		tr.delete(4);
		tr.delete(6);
		tree.pre_show(tr);
    }
}
final class node{
	int value=0;//键值
	int height=1;//节点高度
	node left=null;//左右孩子
	node right=null;
	node(int value){
		this.value=value;
	}
}

final class tree{
	node root=null;
	tree(){}
	void insert(int value){
		if(root==null){
			root=new node(value);
		}else{
			root=insert(root,value);
		}
	}
	node insert(node root,int value){//插入节点
		if(root==null){//找到插入位置
			node t=new node(value);//创建该节点
			return t;
		}
		if(root.value==value){//相等就算了,不过此处没有优化,相等的节点上层仍需要check检查
			System.out.println("already exists");
			return root;
		}
		if(value<root.value){//左子树上创建节点
			root.left=insert(root.left,value);
			
		}else{//右子树上创建节点
			root.right=insert(root.right,value);
		}
		root=check(root);//检查高度,判断是否需要旋转操作
		return root;
	}
	int get_height(node t){//节点高度,空树高度为0
		return t==null?0:t.height;
	}
	node check(node root){//检查高度,判断是否需要旋转操作
		root.height=(Math.max(get_height(root.left),get_height(root.right))+1);//更新节点高度
		if(get_height(root.left)-get_height(root.right)==2){//左边增高了
			if(get_height(root.left.left)>=get_height(root.left.right)){//LL型
				root=l_l_rotate(root);//LL旋转
			}else{//LR型
				root=l_r_rotate(root);//LR旋转
			}
		}else if(get_height(root.right)-get_height(root.left)==2){//右边增高了
			if(get_height(root.right.left)>get_height(root.right.right)){//RL型
				root=r_l_rotate(root);//RL旋转
			}else{//RR型
				root=r_r_rotate(root);//RR旋转
			}
		}
		return root;
	}
	void delete(int value){
		root=delete(root,value);
	}
	node delete(node root,int value){//根据值来删除节点
		if(root==null){//即使没找到也会check检查height
			System.out.println("not found");
			return null;
		}
		if(value<root.value){//左子树上去找
			root.left=delete(root.left,value);
		}else if(value>root.value){//右子树上去找
			root.right=delete(root.right,value);
		}else{//找到了
			if(root.left!=null&&root.right!=null){//左右都不等于null,删除之后仍然平衡
				if(root.left.height>root.right.height){//只是需要更新height
					root.value=max(root.left);//取左子树最大值
					root.left=delete(root.left,root.value);//删除该最大值
				}else{
					root.value=min(root.right);//取右子树最小值
					root.right=delete(root.right,root.value);//删除该最小值
				}
			}else{//左右子树部分或者全部为null
				root=(root.left!=null?root.left:root.right);
				return root;
			}
		}
		root=check(root);
		return root;
	}
	int max(node root){
		if(root==null){
			System.out.println("search and not found");
			return -1;
		}
		while(root.right!=null){
			root=root.right;
		}
		return root.value;
	}
	int min(node root){
		if(root==null){
			System.out.println("search and not found");
			return -1;
		}
		while(root.left!=null){
			root=root.left;
		}
		return root.value;
	}
	node l_l_rotate(node root){//LL旋转
		node temp=root.left;//将左节点拿出来
		root.left=temp.right;
		temp.right=root;
		root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新原root的height
		root=temp;
		root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新新root的height
		return root;
	}
	node r_r_rotate(node root){//RR旋转
		node temp=root.right;//将右节点拿出来
		root.right=temp.left;
		temp.left=root;
		root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新原root的height
		root=temp;
		root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新新root的height
		return root;
	}
	node l_r_rotate(node root){//LR旋转
		root.left=r_r_rotate(root.left);//先RR旋转
		return l_l_rotate(root);//再LL旋转
	}
	node r_l_rotate(node root){//RL旋转
		root.right=l_l_rotate(root.right);//先LL旋转
		return r_r_rotate(root);//再LL旋转
	}
	static void pre_show(tree tr){//前序遍历树
		pre_show(tr.root);
	}
	static void pre_show(node root){//前序遍历树
		if(root!=null){
			System.out.println("value:"+root.value+",height:"+root.height);
			pre_show(root.left);
			pre_show(root.right);
		}
	}
}

结果:

E:\>java t
value:7,height:4
value:2,height:3
value:1,height:1
value:5,height:2
value:3,height:1
value:8,height:2
value:9,height:1

总结

平衡二叉树提供复杂度为O(Log n)的查询、修改操作,通过对树的旋转来保持树的平衡性质。



参考:http://www.cnblogs.com/skywang12345/p/3576969.html#top