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且右兄弟不存在
					
						
				}
	
}