精华内容
下载资源
问答
  • 平衡二叉树的删除

    千次阅读 多人点赞 2018-03-05 11:16:58
    平衡二叉树的删除也涉及到删除后的连接问题。其删除一般分为4种情况: 1)删除叶子结点; 2)删除左子树为空,右子树不为空的结点: 3)删除左子树不为空,右子树为空的结点; 4)删除左右子树都不为空的结点。 ...

    平衡二叉树的删除也涉及到删除后的连接问题。其删除一般分为4种情况:
    1)删除叶子结点;
    2)删除左子树为空,右子树不为空的结点:
    3)删除左子树不为空,右子树为空的结点;
    4)删除左右子树都不为空的结点。

    删除叶子结点很简单,直接删除即可,此处不再赘述。接下来分别学习其他三种删除情况。

    左子树为空,有子树不为空


    以图中的平衡二叉树为例。
    现要删除结点105,结点105有右子树,没有左子树,则删除后,只需要将其父结点与其右子树连接即可。
    这里写图片描述
    删除结点会使相应子树的高度减小,可能会导致树失去平衡,如果删除结点后使树失去平衡,要调整最小不平衡子树使整棵树达到平衡。插入和删除一样,在删除的过程中要时刻保持树的平衡性。

    做子树不为空,右子树为空


    要删除一个结点,结点有左子树没有右子树,这种情况与上一种情况相似,只需要将其父结点与其左子树连接即可。例如要删除图中的结点100,其删除过程如图所示:
    这里写图片描述

    左右子树均不为空


    如果要删除的结点既有左子树又有右子树,则要分情况进行讨论。

    (1)如果该结点x的平衡因子为0或者1 ,找到其左子树中具有最大值的结点max,将max的内容与x的元素进行交换,则max即为要删除的结点。由于树是有序的,因此找到的max结点只可能是一个叶子结点或者一个没有右孩子的结点。

    例如现在有一棵平衡二叉树。现在要删除结点20,结点20的平衡因子是1,则在其左子树中找到最大结点15,将两个结点的数值互换。
    这里写图片描述

    然后删除结点20。
    在删除结点20之后,平衡二叉树失去了平衡,结点10的平衡因子为2,则需要对此最小不平衡子树进行调整,此次调整类似于插入,先进性一次左旋转再进行一次右旋转即可,调整后的结果如图:
    这里写图片描述
    (2)如果要删除的结点其平衡因子为-1,则找到其右结点中具有最小值的结点min,将min与x的数据值进行互换,则min即为新的要删除的结点,将结点删除后,如果树失去了平衡,则需要重新调整。由于平衡二叉树是有序的,因此这样的结点只可能是一个叶子结点,或者是一个没有左子树的结点。

    展开全文
  • 本篇文章为博主对实现平衡二叉树的各种算法的补充,以下代码为平衡二叉树的删除算法的实现。 参考文章:https://blog.csdn.net/sysu_arui/article/details/7897017 具体代码实现 bool DeleteAVL(BiTree &T,int e...

    说明

    本篇文章为博主对实现平衡二叉树的各种算法的补充,以下代码为平衡二叉树的删除算法的实现。
    参考文章:https://blog.csdn.net/sysu_arui/article/details/7897017

    具体代码实现

    bool DeleteAVL(BiTree &T,int e,bool &flag)//删除结点并调整
    {
    	if(T==NULL)//根结点不存在
    	{
    		return false;//删除失败
    	}
    	else if(e==T->data)//找到需要删除的结点
    	{
    		BiTNode *q=NULL;
    		if(T->lchild==NULL)//左子树为空
    		{
    			q=T;
    			T=T->rchild;
    			delete q;
    			flag=true;
    		}
    		else if(T->rchild==NULL)//右子树为空
    		{
    			q=T;
    			T=T->lchild;
    			delete q;
    			flag=true;
    		}
    		else//左右子树均存在
    		{
    			q=T->lchild;
    			while(q->rchild)
    			{
    				q=q->rchild;
    			}
    			T->data=q->data;
    			DeleteAVL(T->lchild,q->data,flag);//在左子树中递归删除前驱结点
    		}
    	}
    	else if(e<T->data)//左子树中继续查找
    	{
    		if(!DeleteAVL(T->lchild,e,flag))
    		{
    			return false;
    		}
    		if(flag)
    		{
    			switch(T->bf)
    			{
    				case LH:
    					T->bf=EH;
    					flag=true;
    					break;
    				case EH:
    					T->bf=RH;
    					flag=false;
    					break;
    				case RH:
    					RightBalance(T);//右平衡处理
    					if(T->rchild->bf==EH)
    						flag=false;
    					else
    						flag=true;
    					break;
    			}
    		}
    	}
    	else//右子树中继续查找
    	{
    		if(!DeleteAVL(T->rchild,e,flag))
    		{
    			return false;
    		}
    		if(flag)
    		{
    			switch(T->bf)
    			{
    				case LH:
    					LeftBalance(T);//左平衡处理
    					if(T->lchild->bf==EH)
    						flag=false;
    					else
    						flag=true;
    					break;
    				case EH:
    					T->bf=LH;
    					flag=false;
    					break;
    				case RH:
    					T->bf=EH;
    					flag=true;
    					break;
    			}
    		}
    	}
    	return true;
    }
    

    本篇文章仅是本人在学习平衡二叉树删除结点过程中的算法总结,如果有什么错漏的地方,敬请谅解。

    展开全文
  • 平衡二叉树的删除也涉及到删除后的连接问题。其删除一般分为4种情况: (1)删除叶子结点 (2)删除的结点只有左子树,没有右子树 (3)删除的结点只有右子树,没有左子树 (4)删除的结点既有左子树,又有右子树 ...
    本文只讲平衡二叉树(AVL)的删除原理,具体代码实现请看后序文章
    

    平衡二叉树的删除也涉及到删除后的连接问题。其删除一般分为4种情况:
    (1)删除叶子结点
    (2)删除的结点只有左子树,没有右子树
    (3)删除的结点只有右子树,没有左子树
    (4)删除的结点既有左子树,又有右子树

    (1)删除叶子结点
    这个很简单,直接删除。然后判断父结点的平衡因子,然后进行旋转,维持AVL的平衡。
    (2)删除的结点只有左子树,没有右子树
    删除后,只需要将其父结点与其左子树连接即可。
    在这里插入图片描述
    删除后依旧可能导致二叉树的不平衡,判断该删除节点上的平衡因子,然后进行旋转,维持AVL的平衡。
    (3)删除的结点只有右子树,没有左子树
    情况类似于(2),删除后,只需要将其父结点与其右子树连接即可。
    在这里插入图片描述
    删除后依旧可能导致二叉树的不平衡,判断该删除节点上的平衡因子,然后进行旋转,维持AVL的平衡。
    (4)删除的结点既有左子树,又有右子树
    分两种情况:
    1)要删除的结点的平衡因子是0或1
    找到其左子树中具有最大值的结点max,将max的内容与x的元素进行交换,则max即为要删除的结点。由于树是有序的,因此找到的max结点只可能是一个叶子结点或者一个没有右孩子的结点。
    在这里插入图片描述
    在这里插入图片描述
    要删除20,先与左子树最大值交换,再删除,之后旋转维持二叉树的平衡。

    2)要删除的结点的平衡因子是-1;
    则找到其右结点中具有最小值的结点min,将min与x的数据值进行互换,则min即为新的要删除的结点,将结点删除后,如果树失去了平衡,则需要重新调整。由于平衡二叉树是有序的,因此这样的结点只可能是一个叶子结点,或者是一个没有左子树的结点。

    展开全文
  • 由于删除要考虑树的平衡状态,所以得用递归进行删除 比如删除30数据, 1、查找30节点, 2、找到之后,判断左树与右树高度谁高,如果是左树高话那就去左树寻找最右边节点,反之就去找右树最左边节点 3、...

    插入思路如图:
    在这里插入图片描述插入就四种情况
    1、右旋
    2、先左旋再右旋
    3、左旋
    4、先右旋再左旋


    删除的思路:
    由于删除要考虑树的平衡状态,所以得用递归进行删除
    比如删除30的数据,
    1、查找30的节点,
    2、找到之后,判断左树与右树的高度谁高,如果是左树高的话那就去左树寻找最右边的节点,反之就去找右树最左边的节点
    3、找到该节点之后,比如他的数据是40,那就把40覆盖掉30,覆盖之后,继续删除,但是现在不是删除30了,删除的是40,继续递归往下找,找到40这个节点就可以收敛了,清除其内存就行

    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <math.h>
    
    typedef struct SHU{
    	int num;
    	int heght;
    	struct SHU *left;
    	struct SHU *right;
    } ss;
    
    int MABS(int a,int b);
    int CheckHight(ss *head);
    ss * Inselt(ss *head,int num) ;
    void look(ss *head,int mode);
    ss * Finemin(ss *head,ss*head2);
    void myfree(ss *head);
    ss *Xuanzhuan(ss *head,int mode);
    ss * delete_avl(ss *head,int num);
    int Findright(ss *temp);
    int Findleft(ss *temp);
    
    
    int MABS(int a,int b)
    {
    	if(a>b) return a-b;
    
    	 return b-a;
    
    
    }
    int CheckHight(ss *head)
    {
    	if(head ==0) return -1;   //是空的话就层数表示-1
    		
    	return head->heght;
    
    
    }
    
    int GeiHight(ss *head1,ss *head2)
    {
    	int hight_lest=0,hight_right=0,temp=0;
    	
    	hight_lest=CheckHight(head1); // 获取当前左树高度
    	hight_right=CheckHight(head2);// 获取当前右树高度
    	if(hight_lest>hight_right){
    		temp=hight_lest+1;
    	}else{
    		temp=hight_right+1;
    	}	
    	return temp;
    }
    
    
    //mode 0:左旋,1 先右后左,2 右旋3 先左后右
    
    ss *Xuanzhuan(ss *head,int mode)
    {
    	ss *temp=0;
    	ss *temp1=0;
    	switch(mode){
    		case 0:
    				temp=head->left;//取出头部的左树
    				
    				head->left=temp->right;//将左树的右边赋值为头部的左边
    					
    				temp->right=head;  //左树的右边指向头部
    				
    				//更新的高度顺序不能乱,因为此时HEAD已经变成 temp的右节点了
    				head->heght=GeiHight(head->left,head->right);
    
    				temp->heght=GeiHight(temp->left,temp->right);
    				
    				return temp;  
    				//刚开始我比较郁闷该怎么拼接,直接然会就行了,
    				//我忽略了指针传参数的意义
    			break;
    		case 1:
    				temp=head->left;//取出头部的左树
    				temp1=temp->right;//
    				//交换这两个数据测顺序
    				head->left=temp1;
    				temp->right=temp1->left; //保存temp1的左树到temp的右树
    				temp1->left =temp;
    				
    				temp->heght=GeiHight(temp->left,temp->right);
    
    				temp1->heght=GeiHight(temp1->left,temp1->right);
    
    				//重复第一步的操作
    
    				temp=head->left;//取出头部的左树
    				
    				head->left=temp->right;//将左树的右边赋值为头部的左边
    					
    				temp->right=head;  //左树的右边指向头部
    				
    				//更新的高度顺序不能乱,因为此时HEAD已经变成 temp的右节点了
    				head->heght=GeiHight(head->left,head->right);
    
    				temp->heght=GeiHight(temp->left,temp->right);
    				
    				return temp;  					
    					
    
    					
    			break;
    		case 2:
    				temp=head->right;//取出头部的左树
    				
    				head->right=temp->left;//将左树的右边赋值为头部的左边
    					
    				temp->left=head;  //左树的右边指向头部
    				
    				//更新的高度顺序不能乱,因为此时HEAD已经变成 temp的右节点了
    				head->heght=GeiHight(head->left,head->right);
    
    				temp->heght=GeiHight(temp->left,temp->right);
    				
    				return temp; 
    
    			break;
    		case 3:
    				temp=head->right;//取出头部的左树
    				temp1=temp->left;//
    				//交换这两个数据测顺序
    				head->right=temp1;
    				temp->left=temp1->right; //保存temp1的左树到temp的右树
    				temp1->right =temp;
    				temp->heght=GeiHight(temp->left,temp->right);
    				temp1->heght=GeiHight(temp1->left,temp1->right);
                                //按第一步进行操作
    
    				temp=head->right;//取出头部的左树
    				
    				head->right=temp->left;//将左树的右边赋值为头部的左边
    					
    				temp->left=head;  //左树的右边指向头部
    				
    				//更新的高度顺序不能乱,因为此时HEAD已经变成 temp的右节点了
    				head->heght=GeiHight(head->left,head->right);
    
    				temp->heght=GeiHight(temp->left,temp->right);
    				
    				return temp; 
                                
    			break;
    		default:
    
    			return head;
    			break;
    	}
    
    
    }
    
    
    ss * Inselt(ss *head,int num)  //数的插入数据函数
    {
    	int hight_lest=0,hight_right=0;
    	if(head==0){//空指针,先申请一波内存
    		head=(ss *)malloc(sizeof(struct SHU));
    		head->num=num;
    		head->heght=0;
    		head->left=0;
    		head->right=0;
    	}else{
    		if(head->num<num){//如果当前的数据比当前的数据大那就往右边进行插入
    			head->right=Inselt(head->right,num);
    			hight_lest=CheckHight(head->left);
    			hight_right=CheckHight(head->right);
    			if(MABS(hight_lest,hight_right)>=2){
    				//最好在这里进行判断,这样会很麻烦
    				if(num>(head->right)->num){ //也就是说该新的数插到了最左边
    					head=Xuanzhuan(head,2);
    				}else{
    					head=Xuanzhuan(head,3);
    				}
    			}
    		}else{//如果当前的数据比当前的数据小那就往右边进行插入
    			head->left=Inselt(head->left,num);
    			hight_lest=CheckHight(head->left);
    			hight_right=CheckHight(head->right);
    			if(MABS(hight_lest,hight_right)>=2){
    				//最好在这里进行判断,这样会很麻烦
    				//这个=很需要,如果相等的数直接按小处理
    				if(num<=(head->left)->num){ //也就是说该新的数插到了最左边
    					head=Xuanzhuan(head,0);
    				}else{
    					head=Xuanzhuan(head,1);
    				}
    			}	
    		}
    		//从新进行对高度的
    		head->heght=GeiHight(head->left,head->right);
    		
    	}
    	return head;
    }
    
    //树的遍历 0 前序 1 中序 2后序
    
    //前序 |根节点 |左边节点|右边节点
    
    //中序 |左边节点 |根节点 |右边节点
    
    //后序 |左边节点|右边节点 |根节点 
    
    //所有的节点都已根节点为基准
    
    void look(ss *head,int mode)
    {
    	switch(mode){
    		case 0:
    			if(head!=0){
    				printf(" %d ",head->num);
    				if(head->left!=0){
    					look(head->left,mode);
    				}
    				if(head->right!=0){
    					look(head->right,mode);
    				}
    			}
    			break;
    		case 1:
    			if(head!=0){
    				if(head->left!=0){
    					look(head->left,mode);
    				}
    				printf(" %d ",head->num);
    
    				if(head->right!=0){
    					look(head->right,mode);
    				}
    			}
    			break;
    		default:
    			if(head!=0){
    
    				if(head->left!=0){
    					look(head->left,mode);
    				}
    				if(head->right!=0){
    					look(head->right,mode);
    				}
    				printf(" %d ",head->num);
    			}			
    			break;
    	}
    
    }
    
    //删除的策略
    //就是吧当前节点的指针替换成其右数最小的值即可
    ss * Finemin(ss *head,ss*head2)
    {
    	ss *temp=head;
    	if(temp==0){
    		return 0;
    	}else{
    		while(temp->left!=0){
    			temp=temp->left;
    		}
    	}
    	return temp;
    }
    
    
    
    int Findright(ss *temp)
    {
    	ss *temp1=temp;	
    
    	if(temp1!=0){  //当前有右节点的话,
    		while(temp1->left!=0){ //找最左边的节点
    			temp1=temp1->left; //继续往下搜索左树
    		}
    		
    	}
    	return temp1->num;
    }
    
    int Findleft(ss *temp)
    {
    	ss *temp1=temp;	
    
    
    	if(temp1!=0){  //当前有右节点的话,
    		while(temp1->right!=0){ //找最左边的节点
    			temp1=temp1->right; //继续往下搜索左树
    		}
    		
    	}
    	return temp1->num;
    }
    
    
    
    //删除的策略第一步:就是先找出被删除的节点
    //a判断左边的节点高还是右边的节点高
    //b是左边的话找出其最大的叶子,
    //c是右边的话找其最小的叶子
    //d将上面找到的节点赋值给删除的节点,也就是覆盖掉他
    //重新去删除BC两部找到的节点,一直找到最末尾的位置为止
    
    
    ss * delete_avl(ss *head,int num) 
    {
    	int hight_lest=0,hight_right=0;
    	int temonums=0;
    	ss *temp=0;
    	ss *temp1=0;
    	ss *headtemp=head;
    	if(head!=0){
    		if(head->num==num){//找到删除的位置
    			if((head->left==0)&&(head->right==0)){ //开始收敛了
    				free(head);
    				return 0;
    			}else{
    				hight_lest=CheckHight(head->left);
    				hight_right=CheckHight(head->right);
    				if(hight_lest>hight_right){//找左树最大的点
    					temonums=Findleft(head->left);
    				}else{
    					temonums=Findright(head->right);
    				}
    				head->num=	temonums; //将值赋值给要删除的指针
    				if(hight_lest>hight_right){
    					head->left=delete_avl(head->left,temonums);
    					hight_lest=CheckHight(head->left);
    					hight_right=CheckHight(head->right);
    					if(MABS(hight_lest,hight_right)>=2){
    						if(hight_lest>hight_right){ 
    							head=Xuanzhuan(head,0);
    						}else{
    							head=Xuanzhuan(head,2);
    						}
    					}
    					head->heght=GeiHight(head->left,head->right);
    					headtemp=head;
    				}else{
    					head->right=delete_avl(head->right,temonums);
    					hight_lest=CheckHight(head->left);
    					hight_right=CheckHight(head->right);
    					if(MABS(hight_lest,hight_right)>=2){
    						if(hight_lest>hight_right){ 
    							head=Xuanzhuan(head,0);
    						}else{
    							head=Xuanzhuan(head,2);
    						}
    					}
    					head->heght=GeiHight(head->left,head->right);
    					headtemp=head;
    				}
                       
    			}
    		}else if(head->num!=num) {
    
    			if(head->num<num){
    				head->right=delete_avl(head->right,num);
    				hight_lest=CheckHight(head->left);
    				hight_right=CheckHight(head->right);
    				// 由于左边去掉的都是最大的,右边去掉的都是最小的
    				//那么如果发生不平衡的事件就不会是双旋转
    				if(MABS(hight_lest,hight_right)>=2){
    					if(hight_lest>hight_right){ 
    						head=Xuanzhuan(head,0);
    					}else{
    						head=Xuanzhuan(head,2);
    					}
    				}
    				head->heght=GeiHight(head->left,head->right);
    				headtemp=head;
    			}else{
    				head->left=delete_avl(head->left,num);
    				hight_lest=CheckHight(head->left);
    				hight_right=CheckHight(head->right);
    				if(MABS(hight_lest,hight_right)>=2){
    					if(hight_lest>hight_right){ 
    						head=Xuanzhuan(head,0);
    					}else{
    						head=Xuanzhuan(head,2);
    					}
    				}
    				head->heght=GeiHight(head->left,head->right);
    				headtemp=head;
    			}
    		}
    			
    	}
    
    	return headtemp;
    }
    
    
    void myfree(ss *head){
    	if(head!=0){
    		if(head->left!=0){
    			myfree(head->left);
    		}
    		if(head->right!=0){
    			myfree(head->right);
    		}
    		free(head);
    	}
    }
    
    
    void main(void)
    {
    	ss *k=0,*temp=0;
    
    	k=Inselt(k,60);
    	k=Inselt(k,50);
    	k=Inselt(k,40);
    	k=Inselt(k,30);
    	k=Inselt(k,20);
    	k=Inselt(k,10);
    	k=Inselt(k,10);
    	k = Inselt(k, 70);
    	
    	
    	k=delete_avl(k,50);
    	k=delete_avl(k,60);
    	k=delete_avl(k,40);
    	
    	temp=k;
    	printf("\n----------------------\n");
    	look(temp,0);
    	printf("\n----------------------\n");
    	myfree(k);
    	
    
    }
    
    
    展开全文
  • 关于平衡二叉树,我查阅了一下资料,在删除部分实现,目前还不是很完善。于是我自己动手写了一个递归删除,每一部分都做了注释,可以把代码直接拷贝到环境中进行测试。测试代码:public class TestAVLTree { ...
  • 偷懒方法 public void delete(Key key) { insert(key, null); } 这样方法就是将key相应值覆盖成null。...这是一种偷懒办法,可是在严肃实际应用中肯定不能这样,一方面会造成内存浪费,...
  • 删除节点存在左孩子,则使用p左孩子最右孩子替换p,然后重平衡树 // 2.待删除节点不存在左孩子,则使用p右孩子替换p,然后重平衡树 // 调用路径:clean_up->unlink_from_pool 1.1 static void unlink_from...
  • 平衡二叉树的实现我们在遍历二叉树时,先一直往左遍历,于是我们发现,当一棵树的每个节点都只有一个子节点时,他就变成了一个链表,然后链表就说啊:❝ 年轻人你不要过度消费我,这好吗?这不好。 ❞所以我们针对这...
  • 平衡二叉树AVL(也是排序二叉树)失衡,分为左左(指在一个节点左孩子左孩子上插入节点(无论插得是左还是右节点)使二叉树失衡,就叫左左)、右右、左右、右左 调整平衡二叉树,可以通过“旋转”,但是首先必须...
  • 平衡二叉树的节点删除比较有意思,删除后,涉及剩余结点的连接和平衡问题。总结一下从平衡二叉树中删除结点可以分为以下三步:找到要删除的结点完成节点的删除找到因为删除而导致不满足平衡二叉树要求的子树并对其...
  • 平衡二叉树AVL删除

    2019-09-22 14:32:20
    平衡二叉树的插入过程:http://www.cnblogs.com/hujunzheng/p/4665451.html 对于二叉平衡树的删除采用的是二叉排序树删除的思路:  假设被删结点是*p,其双亲是*f,不失一般性,设*p是*f的左孩子,下面分三种情况...
  • 平衡二叉树

    2018-01-17 15:18:43
    用了两种方法实现对平衡二叉树的删除与增加,方法很巧妙。
  • 在按照二叉查找树(二叉查找树(BST:Binary Search Tree) )方式插入元素构建一个平衡二叉树(平衡二叉树 )时,可能会出现不平衡现象。可以根据新插入节点与最低不平衡节点之间位置关系进行相应调整。我们先把...
  • 平衡二叉树的实现我们在遍历二叉树时,先一直往左遍历,于是我们发现,当一棵树的每个节点都只有一个子节点时,他就变成了一个链表,然后链表就说啊:❝年轻人你不要过度消费我,这好吗?这不好。❞所以我们针对这个...
  • 一、平衡二叉树的定义为避免树的高度增长过快,降低二叉树的排序性能,规定在插入和删除二叉树结点时,保证任意结点的左右子树高度差的绝对值不大于1。这样的二叉树被称为平衡二叉树(Balanced Binary Tree)。二、...
  • 二分查找树》中提到了:平衡二叉树的目的就是使得平均查找长度最短。那么这里就引出两个问题:什么是平衡二叉树?为什么平衡二叉树的平均查找长度最短?如何将非平衡二叉树调整成平衡二叉树?1. 平衡二叉树是什么鬼...
  • 一、前言概述 在之前的博文《算法导论 之 平衡二叉树 - 插入》和...之所以现在才来写平衡二叉树的删除操作,主要是其过程相对比较复杂,且测试和实现过程中出现了各种各样的问题。 二、处理思路 虽然...
  • 自己整了一天写的平衡二叉树的插入和删除,暂时还没发现bug...
  • 具体功能 初始平衡二叉树为空树操作界面给出创建查找插入删除合并分裂六种操作供选择每种操作均提示输入关键字每次插入或删除一个结点后更新平衡二叉树的显示 平衡二叉树的显示采用凹入表现形式 合并两棵平衡二叉树 ...
  • 适合哪些人阅读:如果您已经对平衡二叉树的概念有一定了解,并且对插入时逻辑有一定了解,这篇文章提供不完整的代码实现。 阅读时间: 10分钟 平衡因子 定义:某节点的左子树与右子树的高度(深度)差即为该节点的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,710
精华内容 1,084
关键字:

平衡二叉树的删除