《B_树的插入、删除、查找的算法(C语言描述)》由会员分享，可在线阅读，更多相关《B_树的插入、删除、查找的算法(C语言描述)（12页珍藏版）》请在金锄头文库上搜索。
1、 B-树的插入、查找、删除算法（C语言描述）前面讨论的查找都是内查询算法，被查询的数据都在内存。当查询的数据放在外存，用平衡二叉树作磁盘文件的索引组织时，若以结点为内外存交换的单位，则找到需要的关键字之前，平均要进行lgn次磁盘读操作，而磁盘、光盘的读写时间要比随机存取的内存代价大得多。其二，外存的存取是以“页”为单位的，一页的大小通常是1024字节或2048字节。针对上述特点，1972年R.Bayer和E.M.Cright提出了一种B-树的多路平衡查找树，以适合磁盘等直接存取设备上组织动态查找表。B-树上算法的执行时间主要由读、写磁盘的次数来决定，故一次I/O操作应读写尽可能多的信息。因此B
2、-树的结点规模一般以一个磁盘页为单位。一个结点包含的关键字及其孩子个数取决于磁盘页的大小。一、基本概念B-树又称为多路平衡查找树。一棵度为m的B-树称为m阶B_树。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求m3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：（1）根结点或者为叶子，或者至少有两棵子树，至多有m棵子树。（2）除根结点外，所有非终端结点至少有ceil(m/2)棵子树，至多有m棵子树。（3）所有叶子结点都在树的同一层上。（4）每个结点的结构为：（n，
3、A0，K1，A1，K2，A2，Kn，An）其中，Ki(1in)为关键字，且KiKi+1(1in-1)。Ai(0in)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。An所指子树中所有结点的关键字均大于Kn。n为结点中关键字的个数，满足ceil(m/2)-1nm-1。比如，一棵3阶B-树，m=3。它满足：（1）每个结点的孩子个数小于等于3。（2）除根结点外，其他结点至少有=2个孩子。（3）根结点有两个孩子结点。（4）除根结点外的所有结点的n大于等于=1，小于等于2。（5）所有叶结点都在同一层上。二、B-树查找的算法思想1、B-树的查找B-树的查找过程：根据给定值查找结点和
4、在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程： 若比结点的第一个关键字小，则查找在该结点第一个指针指向的结点进行；若等于结点中某个关键字，则查找成功；若在两个关键字之间，则查找在它们之间的指针指向的结点进行；若比该结点所有关键字大，则查找在该结点最后一个指针指向的结点进行；若查找已经到达某个叶结点，则说明给定值对应的数据记录不存在，查找失败。2. B-树的插入插入的过程分两步完成：（1）利用前述的B-树的查找算法查找关键字的插入位置。若找到，则说明该关键字已经存在，直接返回。否则查找操作必失败于某个最低层的非终端结点上。（2）判断该结点是否还有空位置。即判断该结点的关键字总数
5、是否满足n=ceil(m/2)，说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。（2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。（3）如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目
6、均等于ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki一起，合并到Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲结点中关键字个数小于ceil(m/2)-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的
7、删除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-树的
8、C语言描述1、存储结构2、 插入3、 查找四、B-树的C语言实现#include stdio.h#include stdlib.h#include math.h#define OK 1#define ERROR -1#define m 3 /3阶树#define N 16 /数据元素个数#define MAX 5 /字符串最大长度1typedef int KeyType;struct Others /记录的其它部分char infoMAX;struct RecordKeyType key; /关键字Others others; /其它部分;typedef struct BTNodeint ke
9、ynum; /结点中关键字个数BTNode *parent;/指向双亲节点struct Node /结点向量类型KeyType key; /关键字向量BTNode *ptr;/子树指针向量Record *recptr; /记录向量指针nodem+1; /key,recptr的0号单元未用BTNode,*BTree;struct Result /B树的查找结果类型BTNode *pt; /指向找到的结点int i; /在节点中关键字序号，1.mint tag; /1表示查找成功，0表示查找失败。;int InitDSTable(BTree &DT)DT=NULL;return OK;/InitD
10、STablevoid DestroyDSTable(BTree &DT)int i;if(DT) /非空树for(i=0;ikeynum;i+)DestroyDSTable(DT-nodei.ptr);free(DT);DT=NULL;/if/DestroyDSTableint Search(BTree p,KeyType K)/在p-node1.keytype.key中查找i,使得p-nodei.key=Knodei+1.keyint i=0,j;for(j=1;jkeynum;j+)if(p-nodej.keykey、r和ap分别插入到q-keyi+1、/q-recptr i+1和q-pt
11、ri+1中int j;for(j=q-keynum;ji;j-) /空出q-nodei+1q-nodej+1=q-nodej;q-nodei+1.key=r-key;q-nodei+1.ptr=ap; /前加入的结点，还没有儿子结点q-nodei+1.recptr=r;q-keynum+;/Insertvoid NewRoot(BTree &T,Record *r,BTree ap)/ 生成含信息(T,r,ap)的新的根结点*T，原T和ap为子树指针BTree p;p=(BTree)malloc(sizeof(BTNode);p-node0.ptr=T;T=p;if(T-node0.ptr)T
12、-node0.ptr-parent=T;T-parent=NULL;T-keynum=1;T-node1.key=r-key;T-node1.recptr=r;T-node1.ptr=ap;if(T-node1.ptr)T-node1.ptr-parent=T;/NewRootvoid split(BTree &q,BTree &ap)/ 将结点q分裂成两个结点，前一半保留，后一半移入新生结点apint i,s=(m+1)/2;ap=(BTree)malloc(sizeof(BTNode);/生成新结点apap-node0.ptr=q-nodes.ptr;/原来结点中间位置关键字相应指针指向的子树放到/新生成结点的0棵子树中去for(i=s+1;inodei-s=q-nodei;if(ap-nodei-s.ptr)ap-nodei-s.ptr-parent=ap;/forap-keynum=m-s;ap-parent=q-parent;q-keynum=s-1; / q的前一半保留，修改keynum/splitvoid InsertBTree(BTree &T,Record *r,BTree q,int i)/在m阶B树T上结点*q的ke
