changes.h

一个B-树实现与编辑

void change(BTree &q,BTree &f,int i,int t);    
    //函数原型声明，删除关键字，并改变其它关键字相应位置


void change1(BTree &q,BTree &f,BTree &pr,int i,int t)

{      //非终端叶子结点中，被删结点q关键字数目小于Ｓ，
	    //其右兄弟pr关键字数目不小于Ｓ的删除算法,
	//将pr结点中的最小关键字上移至双亲f结点中，而将f中小于
	//且紧靠该上移关键字的关键字下移至被删关键字所有的结点中．
	int x,j;
	Record *r;
	x=pr->key[1];
	r=pr->recptr[1];
	j=Search(f,x);
	for(int l=i;l<q->keynum;l++)    //调整q的关键字及其记录
	
	{
		q->key[l]=q->key[l+1];
		q->recptr[l]=q->recptr[l+1];
	}
	for(int l=t;l<q->keynum;l++)    //调整q的子树
	{
		q->ptr[l]=q->ptr[l+1];
		
	}
	q->key[q->keynum]=f->key[j];         //插入
	q->recptr[q->keynum]=f->recptr[j];
	q->ptr[q->keynum]=pr->ptr[0];
	if(pr->ptr[0]!=NULL)
	pr->ptr[0]->parent=q;
	f->key[j]=x;
	f->recptr[j]=r;

	for(int l=1;l<pr->keynum;l++)               //调整右兄弟结点
	{
		pr->key[l]=pr->key[l+1];
		pr->recptr[l]=pr->recptr[l+1];
	}
	for(int l=0;l<pr->keynum;l++)
	{
		pr->ptr[l]=pr->ptr[l+1];
	    
	}
	pr->ptr[pr->keynum]=NULL;
	pr->key[pr->keynum]=0;
	pr->recptr[pr->keynum]=NULL;
	pr->keynum-=1;

}


void change2(BTree q,BTree f,BTree pl,int i,int t)
{ //非终端叶子结点中，被删结点q关键字数目小于Ｓ，
	    //其左兄弟pl关键字数目不小于Ｓ的删除算法,
	//将pl结点中的最大关键字上移至双亲f结点中，而将f中大于
	//且紧靠该上移关键字的关键字下移至被删关键字所有的结点中．
	int x,  j;
	Record *r;
	x=pl->key[pl->keynum];
	r=pl->recptr[pl->keynum];
	j=Search(f,x);
	for(int l=i;l>1;l--)       //调整q关键字及其记录
	{
		q->key[l]=q->key[l-1];
		q->recptr[l]=q->recptr[l-1];
	}
	for(int l=t;t>0;t--)             //调整q的子树
		q->ptr[l]=q->ptr[l-1];
	q->key[1]=f->key[j+1];            //插入
	q->recptr[1]=f->recptr[j+1];
	q->ptr[0]=pl->ptr[pl->keynum];
	if(pl->ptr[pl->keynum]!=NULL)
		pl->ptr[pl->keynum]->parent=q;
	f->key[j+1]=x;
	f->recptr[j+1]=r;
	pl->key[pl->keynum]=0;               //调整左兄弟结点
	pl->recptr[pl->keynum]=NULL;
	pl->ptr[pl->keynum]=NULL;
	
	pl->keynum-=1;
}

void change3(BTree &q,BTree &f,BTree &pr,int i,int t,int l)
{
	//被删关键字所在结点p和其相邻的兄弟结点中的关键字数目均等于s-1且p有右兄弟pr的删除．
	//先调整q,再将f->key[l+1]合并q到中，再将q合并到pr中
	int j;
	BTree p;
					
	if(q->ptr[q->keynum]!=NULL)  //调整q的子树
	{
		for( j=t;j<q->keynum;j++)
			q->ptr[j]=q->ptr[j+1];
		q->ptr[q->keynum]=NULL;
	}
	for(j=i;j<q->keynum;j++)     //调整q的关键字及记录
	{
		q->key[j]=q->key[j+1];
		q->recptr[j]=q->recptr[j+1];
	}
	q->key[q->keynum]=f->key[l+1];        //将f->key[l+1]合并q到中
	q->recptr[q->keynum]=f->recptr[l+1];
	
	for(j=pr->keynum;j>=1;j--)     //调整pr
	
	{
		pr->key[q->keynum+j]=pr->key[j];
		pr->recptr[q->keynum+j]=pr->recptr[j];
	}


		
	for(j=pr->keynum;j>=0;j--)
		pr->ptr[q->keynum+j]=pr->ptr[j];
	
	
		
	for(j=q->keynum;j>=1;j--)      //将q合并到pr中
	{
		pr->key[j]=q->key[j];
		pr->recptr[j]=q->recptr[j];
		pr->ptr[j-1]=q->ptr[j-1];
		if(q->ptr[j-1]!=NULL)q->ptr[j-1]->parent=pr;
	}
	
	

	
	pr->keynum+=q->keynum;      //改变pr关键字数目
	//f->ptr[l]=NULL;free(q);
	i=l+1;
	if(f->keynum==s-1)      //判断下一步操作    
	{
		if(f->parent!=NULL)

		change(f,f->parent,i,i-1);
	else
		
	{
		p=T;T=pr;T->parent=NULL;free(p);
	}
	}
	else
	{
		for(j=i;j<f->keynum;j++)
		{
			f->key[j]=f->key[j+1];
			f->recptr[j]=f->recptr[j+1];
		}
		f->key[f->keynum]=0;
		f->recptr[f->keynum]=NULL;
		
		for(j=i-1;j<f->keynum;j++)
			f->ptr[j]=f->ptr[j+1];
		f->ptr[f->keynum]=NULL;
		f->keynum-=1;
	}free(q);
		

}





void change4(BTree q,BTree &f,BTree pl,int i,int t,int l)
{//被删关键字所在结点p和其相邻的兄弟结点中的关键字数目均等于s-1且p有右兄弟pl的删除．
	//先调整q,再将k(l)合并q到中，再将q合并到pl中
	int j;
	BTree p;
	if(q->ptr[0]!=NULL)          //调整q的子树
	{
		for(j=t;j>0;j--)
			q->ptr[j]=q->ptr[j-1];
		q->ptr[0]=NULL;
	}
	for(j=i;j>1;j--)             //调整q的关键字及记录
	{
		q->key[j]=q->key[j-1];
		
		q->recptr[j]=q->recptr[j-1];
	}
	q->key[1]=f->key[l];          //将f->k[l]合并q到中
	q->recptr[1]=f->recptr[l];
	for(j=1;j<=q->keynum;j++)        //将q合并到pl中
	{
		pl->key[pl->keynum+j]=q->key[j];
		pl->recptr[pl->keynum+j]=q->recptr[j];
		pl->ptr[pl->keynum+j]=q->ptr[j];
		if(q->ptr[j]!=NULL)q->ptr[j]->parent=pl;
	}
	    
	pl->keynum+=q->keynum;       //改变pl关键字数目
	
	//f->ptr[l]=NULL;free(q);
	i=l;

	if(f->keynum==s-1)           //判断下一步操作  
	{
		if(f->parent!=NULL)
			change(f,f->parent,i,i);
		else
		{p=T;T=pl;T->parent=NULL;free(p);}
	}
	else
		if(f->keynum>=s)
	{
		for(j=i;j<f->keynum;j++)
		{
			f->key[j]=f->key[j+1];
			f->recptr[j]=f->recptr[j+1];
			f->ptr[j]=f->ptr[j+1];
		}
		f->key[f->keynum]=0;
		f->recptr[f->keynum]=NULL;
		f->ptr[f->keynum]=NULL;
		f->keynum-=1;
		
	}free(q);
	//f->ptr[l]=NULL;free(q);
	     

	
}


void change(BTree &q,BTree &f,int i,int t)
{//删除关键字，并改变其它关键字相应位置
	int l;
	BTree pl=NULL,pr=NULL;
	
	l=Search(f,q->key[1]);      //找出左右兄弟
		if(l>0)
		pl=f->ptr[l-1];
		if(l<f->keynum)
		pr=f->ptr[l+1];
		if(pr!=NULL&&pr->keynum>=s)    
		{
			
			change1(q,f,pr,i,t);//右兄弟存在，且其关键字数目不小于s
		}

			else
				if(pl!=NULL&&pl->keynum>=s) 
				{                                
					
				    change2(q,f,pl,i,t);//左兄弟存在，且其关键字数目不小于s,
				}//右兄弟不存在或其关键字数目小于s
			else
				if(pr!=NULL)
				{
					

					change3(q,f,pr,i,t,l);//左右兄弟关键字数目均小于s且右兄弟存在
					
						
				}
				else
				{
					change4(q,f,pl,i,t,l);//左右兄弟关键字数目均小于s且右兄弟不存在
					
						
				}
	
}