deletes.h

一个B-树实现与编辑

void DeleteBTree(BTree &T,int x,Record* r,BTree q,int i)
{
	
	
	BTree p;
	p=q;
	if(q==T&&q->ptr[i]==NULL)//当树只有根时,且删除根的元素
	{
		for(int j=i;j<q->keynum;j++)
		{
			q->key[j]=q->key[j+1];
			q->recptr[j]=q->recptr[j+1];
		}
		q->key[q->keynum]=0;
		q->recptr[q->keynum]=NULL;
		q->keynum-=1;
	}
	else

	if(q->ptr[i]!=NULL)//非根非叶子结点
	{
		p=p->ptr[i];
		while(p->ptr[0]!=NULL)
			p=p->ptr[0];
		q->recptr[i]=p->recptr[1];
		q->key[i]=p->key[1];
		if(p->keynum>=s)
		{
			for(int j=1;j<p->keynum;j++)
			{
				p->key[j]=p->key[j+1];
				p->recptr[j]=p->recptr[j+1];
			}
			p->key[p->keynum]=0;
			p->recptr[p->keynum]=NULL;
			p->keynum-=1;
		}
		else

		     change(p,p->parent,1,1);
	}
	else
		if(q->ptr[i]==NULL)//非终端叶子结点
		{
			if(q->keynum>=s)
		{
			for(int j=i;j<q->keynum;j++)
			{
				q->key[j]=q->key[j+1];
				q->recptr[j]=q->recptr[j+1];
			}
			q->key[q->keynum]=0;
			q->recptr[q->keynum]=NULL;
			q->keynum-=1;
		}
			else
				change(q,q->parent,i,i);
		}
}