西文图书管理与野人过河

数据结构课程设计报告

结点最后一个指针指向的结点进行；若查找已经到达某个叶结点，则说明给定值对应的数据记录不存在，查找失败。

用C语言描述并返回结果如下： //在B-Tree中查找关键字

Result searchBTree(BTree t, KeyType *k) {

BTree p=t,q=NULL; int found=0; int i=0;

Result result; while(p&&!found) {

i=searchNode(p,k);

if( i>0 && p->key[i].booknum==k->booknum) found=1; else {

q=p;

p=p->ptr[i]; } }

if(found) {

result.pt=p; result.i=i; result.tag=1; } else {

result.pt=q; result.i=i; result.tag=0; }

return result; }

2. B-树的插入

插入的过程分两步完成：

- 4 -

数据结构课程设计报告

(1)利用前述的B-树的查找算法查找关键字的插入位置。若找到，则说明该关键字已经存在，直接返回。否则查找操作必失败于某个最低层的非终端结点上。

(2)判断该结点是否还有空位置。即判断该结点的关键字总数是否满足

n<=m-1。若满足，则说明该结点还有空位置，直接把关键字k插入到该结点的合适位置上。若不满足，说明该结点己没有空位置，需要把结点分裂成两个。

分裂的方法是：生成一新结点。把原结点上的关键字和k按升序排序后，从中间位置把关键字（不包括中间位置的关键字）分成两部分。左部分所含关键字放在旧结点中，右部分所含关键字放在新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过（m-1），则要再分裂，再往上插。直至这个过程传到根结点为止。

插入及分裂用C语言描述如下:

void InsertBTree(BTNode *&t, KeyType k, BTNode *&q, int i) //在m阶t树t上结点*q的key[i]与key[i+1]之间插入关键字k。若引起//结点过大,则沿双亲链进行必要的结点分裂调整,使t仍是m阶t树。 {

BTNode *ap;

int finished,needNewRoot,s; KeyType x;

if(q==NULL) //t是空树(参数q初值为NULL)

NewRoot(t,NULL,k,NULL); //生成仅含关键字k的根结点*t else {

x=k; ap=NULL;

finished=needNewRoot=0;

while (needNewRoot==0 && finished==0) {

Insert(q,i,x,ap); //将x和ap分别插入到//q->key[i+1]和q->ptr[i+1]

if(q->keynum<=m) finished=1; /*插入完成*/ else

{ //分裂结点*q,将q->key[s+1..m],q->ptr[s..m]和//q->recptr[s+1..m]移入新结点*ap s=(m+1)/2; Split(q,ap); x=q->key[s];

- 5 -

数据结构课程设计报告

if(q->parent) //在双亲结点*q中查找x的插入位//置

{

q=q->parent;

//i=Search(q, x); }

else needNewRoot=1; } }

if(needNewRoot==1) //根结点已分裂为结点*q和*ap

NewRoot(t,q,x,ap); //生成新根结点*t,q和ap为子树指针 } }

3.B-树的删除

在B-树上删除关键字k的过程分两步完成：

（1）利用前述的B-树的查找算法找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。 （2）若该结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从指针son[i]所指的子树中找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。 因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。

在B-树叶结点上删除一个关键字的方法是

首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况：

（1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)，说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。

（2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。

调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。 （3）如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均等于ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加

- 6 -

数据结构课程设计报告

上双亲结点中的关键字Ki一起，合并到Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲结点中关键字个数小于ceil(m/2)-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。

总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除

a、被删关键字Ki所在结点的关键字数目不小于ceil(m/2)，则只需从结点中删除Ki和相应指针Ai，树的其它部分不变。

b、被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。调整过程如上面所述。

c、被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，假设该结点有右兄弟，且其右兄弟结点地址由其双亲结点指针Ai所指。则在删除关键字之后，它所在结点的剩余关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟结点中（若无右兄弟，则合并到左兄弟结点中）。如果因此使双亲结点中的关键字数目少于ceil(m/2)-1，则依次类推。

B_树中删除操作用C语言描述为：

int RecDelete(KeyType k,BTNode *p)//查找并删除关键字k {

int i; int found;

if(p==NULL) return 0; else {

if((found=SearchNode(k,p,i))==1) //查找关键字k {

if(p->ptr[i-1]!=NULL) //若为非叶子结点 {

Successor(p,i); //由其后继代替它

RecDelete(p->key[i],p->ptr[i]); //p->key[i]在叶子结点中

} else

Remove(p,i); //从*p结点中位置i处删除关键字 } else

- 7 -