B-树插入删除代码数据结构算法经典

#include "BTNode.h" /*搜索树函数 Search B-Tree for Target 前提：root所指B-Tree已经被创建 结果：若target在B-Tree中，则返回值所在节点，并且targetpos保存着 target在这个节点中的位置 用到的函数有：SearchTree被递归调用,SearchNode被调用*/ Treenode* SearchTree(KeyType target,Treenode* root,int* targetpos) { if (!root) { return NULL; } else if (SearchNode(target,root,targetpos)) { return root; } else { return SearchTree(target,root->branch[*targetpos],targetpos); } } /*搜索节点函数 前提：target是个关键字并且current指向B-tree的一个节点 结果：返回真且target在节点中的位置保存于pos 或者返回假pos 保存了应该去哪棵子树去找*/ bool SearchNode(KeyType target,Treenode* current,int *pos) { if (target<current->entry[1].key) { *pos=0; return false; } else { for (*pos=current->count;target<current->entry[*pos].key&&*pos>1;(*pos)--); return target==current->entry[*pos].key; } } /*插入函数 前提：root所指的B-Tree已经被创建，本函数不应插入重复的记录 结果：newentry插入B-tree中，返回root 所用到了的函数：PushDown */ Treenode* InsertTree(Treentry newentry,Treenode* root) { Treentry medentry;//新根结点要插入的记录 Treenode* medright;//medentry的右子树 Treenode* newroot;//新根结点是用于树的高度增加了 if (PushDown(newentry,root,&medentry,&medright)) {//树增高了 newroot=(Treenode*)malloc(sizeof(Treenode)); newroot->count=1; newroot->entry[1]=medentry; newroot->branch[0]=root; newroot->branch[1]=medright; return newroot; } return root; } /*子树中的递归插入 前提：newentry应该插入到current的子树中 结果：newentry插入到current的子树中， 若返回true，则表明子树的高度增加，则medentry需要插入到树的高层,且将子树的medright放到 它的右边 用到了的函数：PushDown递归调用，SearchNode，Split，PushIn */ bool PushDown(Treentry newentry,Treenode*current,Treentry*medentry,Treenode**medright) { int pos;//存储在哪个分支继续搜寻 if(current==NULL)//不能在空树上插入 { *medentry=newentry; *medright=NULL; return true; } else { if (SearchNode(newentry.key,current,&pos)) { //Warning("掺入了重复的值"); } else { if (PushDown(newentry,current->branch[pos],medentry,medright)) { if (current->count<MAX)//可以直接插入 { PushIn(*medentry,*medright,current,pos); return false; } else//造成分裂 { Split(*medentry,*medright,current,pos,medentry,medright); return true; } } } return false; } } /*将键插入到节点 前提：medentry属于current节点的pos位置上， 结果：将medentry，medright都插入到了current节点的pos位置上 */ void PushIn(Treentry medentry,Treenode*medright,Treenode*current,int pos) { int i; for (i=current->count;i>pos;i--) { current->entry[i+1]=current->entry[i]; current->branch[i+1]=current->entry[i]; } current->entry[pos+1]=medentry; current->branch[pos+1]=medright; current->count++; } /*划分一个满节点 前提：medentry属于满节点current的pos位置上 结果：将current 节点和在pos上medentry,medright分裂成current和newright（包含newmedian） */ void Split(Treentry medentry,Treenode*medright,Treenode*current,int pos,Treentry*newmedian,Treenode**newright) { int i; int median; if (pos<=MIN) { median=MIN; } else { median=MIN+1; } //产生一个分裂后的右边节点 *newright=(Treenode*)malloc(sizeof(Treenode)); //将右边的记录插入到右节点中 for (i=median+1;i<=MAX;i++) { (*newright)->entry[i-median]=current->entry[i]; (*newright)->branch[i-median]=current->branch[i]; } (*newright)->count=MAX-median; current->count=median; if (pos<=MIN) { PushIn(medentry,medright,current,pos); } else { PushIn(medentry,medright,*newright,pos-median); } *newmedian=current->entry[current->count]; (*newright)->branch[0]=current->branch[current->count]; current->count--; }