(h 从叶子结点中删除一个关键字的情况是 除 除 (I)若结点N中的关键字个数fm21:在结点中直 接删除关键字K,如图(b)∽©所示。 (2)若结点N中的关键字个数「m21:若结点N的 a 左（右）兄弟结点中的关键字个数fm2L1,则将结点 N的左（或右）兄弟结点中的最大（或最小）关键字上移 除 除 到其父结点中，而父结点中大于（或小于）且紧靠上移 m m b 关键字的关键字下移到结点N,如图(a)。 (3)若结点N和其兄弟结点中的关键字数-21： P e P (d) 删除结点N中的关键字，再将结点N中的关键字、指 回 针与其兄弟结点以及分割二者的父结点中的某个关 在B树中进行侧除的过程 键字K,合并为一个结点，若因此使父结点中的关 键字个数「m21则依世类推.如图(d 算法实现 if(b->keynum>(m-1)/2) 严左邻兄弟有多余关键字) 在B树上删除一个关键字的操作，针对上述的(2) 和(3的情况，相应的算法如下： for (k=p->keynum;k>=0;K--) {p->keyk+1片p->key[k int BTNode MoveKey(BTNode*p) p->ptr[k+1]=p->ptr[k]: P将命的左（或右）兄弟结点中的最大（成最小）关键字上移 】严将印中关键字和指针后移 广到其父结点中，父结点中的关键字下移到中/ p->key[1]=f->key[j]: {BTNode*b,*f=p->parent;产f指向p的父结点7 f->key[j]=b->key[keynum]; int k.j; 严f仲关键字下移到卵，b中最大关键字上移到y for0片0：f>pt=p:j+)产在仲找p的位置7 p->ptr[0]=b->ptr[keynum]; f>0)IP若D有左邻兄第结点7 p->keynum++: 22 {b=f->ptf-11:Pb指向p的左邻兄弟7 b->keynum-; return(1) b->key[k]=b->key[k+1]: b->ptr[k]=b->ptr[k+1]; fG<f->keynum严若p有右邻兄弟结点y 】产将6中关键字和指针前移 {b=f->pt+1]:Pb指向p的右邻兄弟v p->keynum++; if (b->keynum>(m-1)/2) b->keynum--; 严右邻兄弟有多余关键字1 return(1); p->key[p->keynum]=f->key[j+1]; f->key1]片b-keyM1]: p->ptr[p->keynum]=b->ptr[0]: return(0); P仲关键字下移到P,b中最小关键字上移到fV 】左右兄弟中无多余关键字移动失败习 for (k=0;k<b->keynum;k++) 44 19 在B_树中进行删除的过程 删除q b d e g l m q h f p b d e g l p h f m 删除h (a) 删除e b d e l p g f m b e l p g f m 删除d l p g m b f (b) (c) (d) 20 从叶子结点中删除一个关键字的情况是： ⑴ 若结点N中的关键字个数>⎡m/2⎤-1：在结点中直 接删除关键字K，如图 (b)∽©所示。 ⑵ 若结点N中的关键字个数=⎡m/2⎤-1：若结点N的 左(右)兄弟结点中的关键字个数>⎡m/2⎤-1，则将结点 N的左(或右)兄弟结点中的最大(或最小)关键字上移 到其父结点中，而父结点中大于(或小于)且紧靠上移 关键字的关键字下移到结点N，如图 (a)。 ⑶ 若结点N和其兄弟结点中的关键字数=⎡m/2⎤-1： 删除结点N中的关键字，再将结点N中的关键字、指 针与其兄弟结点以及分割二者的父结点中的某个关 键字Ki ，合并为一个结点，若因此使父结点中的关 键字个数<⎡m/2⎤-1 ，则依此类推，如图 (d)。 21 算法实现 在B_树上删除一个关键字的操作，针对上述的⑵ 和⑶的情况，相应的算法如下： int BTNode MoveKey(BTNode *p) /* 将p的左(或右)兄弟结点中的最大(或最小)关键字上移 */ /* 到其父结点中,父结点中的关键字下移到p中 */ { BTNode *b , *f=p->parent ; /* f指向p的父结点 */ int k, j ; for (j=0; f->ptr[j]!=p; j++) /* 在f中找p的位置 */ if (j>0) /* 若p有左邻兄弟结点 */ { b=f->ptr[j-1] ; /* b指向p的左邻兄弟 */ 22 if (b->keynum>(m-1)/2) /* 左邻兄弟有多余关键字 */ { for (k=p->keynum; k>=0; k--) { p->key[k+1]=p->key[k]; p->ptr[k+1]=p->ptr[k]; } /* 将p中关键字和指针后移 */ p->key[1]=f->key[j]; f->key[j]=b->key[keynum] ; /* f中关键字下移到p, b中最大关键字上移到f */ p->ptr[0]= b->ptr[keynum] ; p->keynum++ ; b->keynum-- ; 23 return(1) ; } if (j<f->keynum) /* 若p有右邻兄弟结点 */ { b=f->ptr[j+1] ; /* b指向p的右邻兄弟 */ if (b->keynum>(m-1)/2) /* 右邻兄弟有多余关键字 */ { p->key[p->keynum]=f->key[j+1] ; f->key[j+1]=b->key[1]; p->ptr[p->keynum]=b->ptr[0]; /* f中关键字下移到p, b中最小关键字上移到f */ for (k=0; k<b->keynum; k++) 24 { b->key[k]=b->key[k+1]; b->ptr[k]=b->ptr[k+1]; } /* 将b中关键字和指针前移 */ p->keynum++ ; b->keynum-- ; return(1) ; } } return(0); } /* 左右兄弟中无多余关键字,移动失败 */ }