delete.h

一个B-树实现与编辑

Status DeleteBTree(BTree &T,int k,BTree q,int i)
{
	BTree p,f,pl,pr;//f为q的双亲，pl,pr分别为q的左右兄弟。
	int l;
	p=q;
	if(q->ptr[i]!=NULL)
	{
		p=q->ptr[i];
		while(p->ptr[0]!=NULL)
			p=p->ptr[0];
		q->key[i]=p->key[1];
		q->recptr[i]=p->recptr[1];
		if(p->keynum>=s)
		{
			for(int j=1;j<p->keynum-1;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;
			return OK;
		}
		else
		{
			f=p->parent;
			pr=f->ptr[1];
			if(p->keynum>=s)
				change1(p,f,pr,1);//p:要删除的关键字所以的结点,pr:q的右兄弟,f:q与p的双亲,i:x在p中的位置
			else
				change(q,f,1);
		}
	}
	else     //q是非终端叶子结点
	{
		if(q->keynum>=s||q==T)
		{
			for(int j=i;j<q->keynum-1;j++)
			{
				q->key[j]=q->key[j+1];
				q->recptr[j]=q->recptr[j+1];
			}
			q->key[p->keynum]=0;
			q->recptr[p->keynum]=NULL;
			q->keynum-=1;
			return OK;
		}
		else
		{
			f=q->parent;
			l=Search(f,q->key[0]);
			pl=f->ptr[l-1];
			pr=f->ptr[l+1];
			if(pr!=NULL&&pr->keynum>=s)
				change1(q,f,pr,i);
			else
			if(pl!=NULL&&pl->keynum>=s)
				change2(q,f,pl,i);
			else
				change(q,f,i);
		}
	}
	return OK;
}