void insert BTree(BTNode *T, Keytype K) /在B_树T中插入关键字K,* BTNode*q, S1=NULL, * S2=NULL f( bT search(T,K,p)/树中不存在关键字K* i While (p=NULL) {p->key0=K;/设置哨兵* for(n=p->keynum; ksp->keyn]; n-) i p->keyn+ 1=p->keyIn p->ptr[n+1=p->ptrn }/后移关键字和指针” p->keyIn=K; p->ptr[n-1=S
16 void insert_BTree(BTNode *T, KeyType K) /* 在B_树T中插入关键字K， */ { BTNode *q, *s1=NULL, *s2=NULL ; int n ; if (!BT_search(T, K, p)) /* 树中不存在关键字K */ { while (p!=NULL) { p->key[0]=K ; /* 设置哨兵 */ for (n=p->keynum ; K<p->key[n] ; n--) { p->key[n+1]=p->key[n] ; p->ptr[n+1]=p->ptr[n] ; } /* 后移关键字和指针 */ p->key[n]=K ; p->ptr[n-1]=s1 ;
p-> porn+1]=s2;/置关键字K的左右指针 if(++(p->keynum )<m) break else{s2=spl(p);s1=p;/分裂结点p K=p->keylp->keynum+ 1] p=p-> parent;/*取出父结点* f(p==NULL)/*需要产生新的根结点 i p=(BTNode*)malloc(sizeof( BTNode)) p->keynum=1; p->keyl1=K p->ptr[O]=s1; p->ptr[1]=s2 }}
17 p->ptr[n+1]=s2 ; /* 置关键字K的左右指针 */ if (++(p->keynum )<m) break ; else { s2=split(p) ; s1=p ; /* 分裂结点p */ K=p->key[p->keynum+1] ; p=p->parent ; /* 取出父结点*/ } } if (p==NULL) /* 需要产生新的根结点 */ { p=(BTNode*)malloc(sizeof( BTNode)) ; p->keynum=1 ; p->key[1]=K ; p->ptr[0]=s1 ; p->ptr[1] =s2 ; } } }
利用m阶B_树的插入操作,可从空树起,将一组 关键字依次插入到m阶B树中,从而生成一个m阶B树。 4B树的删除 在B_树上删除一个关键字K,首先找到关键字所在 的结点N,然后在N中进行关键字K的删除操作。 若N不是叶子结点,设K是N中的第个关键字,则 将指针A1所指子树中的最大关键字(或最小关键字)K放 在(K)的位置,然后删除K,而K一定在叶子结点上。如 图,删除关键字h,用关键字g代替h的位置,然后再从 叶子结点中删除关键字g
18 4 B_树的删除 在B_树上删除一个关键字K ，首先找到关键字所在 的结点N，然后在N中进行关键字K的删除操作。 若N不是叶子结点，设K是N中的第i个关键字，则 将指针Ai-1所指子树中的最大关键字(或最小关键字)K’放 在(K)的位置，然后删除K’，而K’一定在叶子结点上。如 图，删除关键字h，用关键字g代替h的位置，然后再从 叶子结点中删除关键字g。 利用m阶B_树的插入操作，可从空树起，将一组 关键字依次插入到m阶B_树中，从而生成一个m阶B_树