B-树结点的分裂不是很理解求指点

QQ3469571352011-08-15 20:56

程序代码：

#define m 3 //B_树的阶，现设为3
int s=(m+1)/2; //s为分裂结点的中值
void split(BTree q,BTree &ap)
{    //将结点*q分裂成两个结点，前一半保留在*q，后一半移入新生结点*ap
    int i;
    ap=(BTree)malloc(sizeof(BTNode)); // 生成新结点*ap
    ap->ptr[0]=q->ptr[s]; // 结点*q的后一半移入结点*ap
    if(ap->ptr[0]) // ap->ptr[0]不为空
        ap->ptr[0]->parent=ap; // 给ap->ptr[0]的双亲域赋值ap
    for(i=s+1;i<=m;i++) // 对于*q中后一半数据
    {
        ap->key[i-s]=q->key[i]; // 3个成员均移结点*ap
        ap->recptr[i-s]=q->recptr[i];
        ap->ptr[i-s]=q->ptr[i];
        if(ap->ptr[i-s]) // ap->ptr[i-s]不为空
        ap->ptr[i-s]->parent=ap; // 给ap->ptr[i-s]的双亲域赋值ap
    }
    ap->keynum=m-s; // 新结点*ap的关键字个数
    q->keynum=s-1; // *q的前一半保留，修改*q的关键字个数
}
void NewRoot(BTree &T,Record* r,BTree ap)
{    //生成含信息(T,r,ap)的新的根结点*T，原根结点T和ap为其子树指针
    BTree p=(BTree)malloc(sizeof(BTNode)); // 动态生成新根结点
    p->parent=NULL; // 新根结点的双亲为空
    p->keynum=1; // 新根结点有1个关键字
    p->key[1]=r->key; // 这个关键字是记录r的关键字
    p->recptr[1]=r; // 指向记录r
    p->ptr[0]=T; // 原根结点T为新根结点的第1棵子树
    if(T) // 原根结点T不空
        T->parent=p; // 新根结点是原根结点T的双亲
    p->ptr[1]=ap; // 结点*ap为新根结点的第2棵子树
    if(ap) // ap不空
        ap->parent=p; // 新根结点是ap的双亲
    T=p; // T指向新根结点
}

[ 本帖最后由 QQ346957135 于 2011-8-15 20:59 编辑 ]

B-树结点的分裂 不是很理解 求指点