devbox
正经夜光杯
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

B-树的插入、查找、删除 及 可执行的C语言代码_写出b-树的构建,查找,插入和删除代码,并设计一个主函数来呈现该操作。用c语言

作者：正经夜光杯 | 2024-06-28 14:33:07

赞

踩

写出b-树的构建,查找,插入和删除代码,并设计一个主函数来呈现该操作。用c语言

 前面讨论的查找都是内查询算法，被查询的数据都在内存。当查询的数据放在外存，用平衡二叉树作磁盘文件的索引组织时，若以结点为内外存交换的单位，则找到需要的关键字之前，平均要进行lgn次磁盘读操作，而磁盘、光盘的读写时间要比随机存取的内存代价大得多。其二，外存的存取是以“页”为单位的，一页的大小通常是1024字节或2048字节。

 针对上述特点，1972年R.Bayer和E.M.Cright提出了一种B-树的多路平衡查找树，以适合磁盘等直接存取设备上组织动态查找表。B-树上算法的执行时间主要由读、写磁盘的次数来决定，故一次I/O操作应读写尽可能多的信息。因此B-树的结点规模一般以一个磁盘页为单位。一个结点包含的关键字及其孩子个数取决于磁盘页的大小。

一、基本概念

B-树又称为多路平衡查找树。

         一棵度为m的B-树称为m阶B_树。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求m≥3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：

（1）根结点或者为叶子，或者至少有两棵子树，至多有m棵子树。

（2）除根结点外，所有非终端结点至少有ceil(m/2)棵子树，至多有m棵子树。

（3）所有叶子结点都在树的同一层上。

（4）每个结点的结构为：

       （n，A0，K1，A1，K2，A2，…  ，Kn，An）

其中，Ki(1≤i≤n)为关键字，且Ki<Ki+1(1≤i≤n-1)。

        Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。An所指子树中所有结点的关键字均大于Kn。

n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。

        比如，一棵3阶B-树，m=3。它满足： 

（1）每个结点的孩子个数小于等于3。 

（2）除根结点外，其他结点至少有=2个孩子。 

（3）根结点有两个孩子结点。 

（4）除根结点外的所有结点的n大于等于=1，小于等于2。 

（5）所有叶结点都在同一层上。
   29、B-树及其查找 - 墨涵 - 墨涵天地

二、B-树查找的算法思想

1、B-树的查找

B-树的查找过程：根据给定值查找结点和在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程：

       若比结点的第一个关键字小，则查找在该结点第一个指针指向的结点进行；若等于结点中某个关键字，则查找成功；若在两个关键字之间，则查找在它们之间的指针指向的结点进行；若比该结点所有关键字大，则查找在该结点最后一个指针指向的结点进行；若查找已经到达某个叶结点，则说明给定值对应的数据记录不存在，查找失败。

2.  B-树的插入

插入的过程分两步完成：

   （1）利用前述的B-树的查找算法查找关键字的插入位置。若找到，则说明该关键字已经存在，直接返回。否则查找操作必失败于某个最低层的非终端结点上。

   （2）判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n<=m-1。若满足，则说明该结点还有空位置，直接把关键字k插入到该结点的合适位置上。若不满足，说明该结点己没有空位置，需要把结点分裂成两个。

分裂的方法是：生成一新结点。把原结点上的关键字和k按升序排序后，从中间位置把关键字（不包括中间位置的关键字）分成两部分。左部分所含关键字放在旧结点中，右部分所含关键字放在新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过（m-1），则要再分裂，再往上插。直至这个过程传到根结点为止。

29、B-树及其查找 - 墨涵 - 墨涵天地
29、B-树的插入、查找、删除 - EdwardLewis - 墨涵天地

29、B-树及其查找 - 墨涵 - 墨涵天地

29、B-树及其查找 - 墨涵 - 墨涵天地

3、B-树的删除

在B-树上删除关键字k的过程分两步完成：

   （1）利用前述的B-树的查找算法找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。

   （2）若该结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从指针son[i]所指的子树中找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。

因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。

在B-树叶结点上删除一个关键字的方法是

首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况：

（1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)，说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。

（2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。

调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。

（3）如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均等于ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki一起，合并到Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲结点中关键字个数小于ceil(m/2)-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。

总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。

29、B-树及其查找 - 墨涵 - 墨涵天地

如图示：

a、被删关键字Ki所在结点的关键字数目不小于ceil(m/2)，则只需从结点中删除Ki和相应指针Ai，树的其它部分不变。

29、B-树及其查找 - 墨涵 - 墨涵天地

b、被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。调整过程如上面所述。

29、B-树及其查找 - 墨涵 - 墨涵天地

c、被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，假设该结点有右兄弟，且其右兄弟结点地址由其双亲结点指针Ai所指。则在删除关键字之后，它所在结点的剩余关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟结点中（若无右兄弟，则合并到左兄弟结点中）。如果因此使双亲结点中的关键字数目少于ceil(m/2)-1，则依次类推。

29、B-树及其查找 - 墨涵 - 墨涵天地

29、B-树及其查找 - 墨涵 - 墨涵天地

三、B-树的C语言描述

1、存储结构

29、B-树及其查找 - 墨涵 - 墨涵天地

29、B-树及其查找 - 墨涵 - 墨涵天地

2、插入

29、B-树及其查找 - 墨涵 - 墨涵天地

3、查找

29、B-树及其查找 - 墨涵 - 墨涵天地

四、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 //字符串最大长度＋1
typedef int KeyType;
struct Others  //记录的其它部分
{
char info[MAX];
};
struct Record
{
KeyType key; //关键字
Others others; //其它部分
};
typedef struct BTNode
{
int keynum; //结点中关键字个数
BTNode *parent;//指向双亲节点
   struct Node  //结点向量类型
   {
   KeyType key; //关键字向量
   BTNode *ptr;//子树指针向量
   Record *recptr; //记录向量指针
   }node[m+1]; //key,recptr的0号单元未用
}BTNode,*BTree;
struct Result //B树的查找结果类型
{
BTNode *pt; //指向找到的结点
int i; //在节点中关键字序号，1...m
int tag; //1表示查找成功，0表示查找失败。
};

int InitDSTable(BTree &DT)
{
DT=NULL;
return OK;
}//InitDSTable

void DestroyDSTable(BTree &DT)
{
int i;
if(DT) //非空树
    {
     for(i=0;i<=DT->keynum;i++)
         DestroyDSTable(DT->node[i].ptr);
     free(DT);
     DT=NULL;
    }//if
}//DestroyDSTable

int Search(BTree p,KeyType K)
{//在p->node[1...keytype].key中查找i,使得p->node[i].key<=K<
    //p->node[i+1].key
    int i=0,j;
    for(j=1;j<=p->keynum;j++)
        if(p->node[j].key<=K)
            i=j;
    return i;
}//Search

void Insert(BTree &q,int i,Record *r,BTree ap)
{//将r->key、r和ap分别插入到q->key[i+1]、
    //q->recptr[              i+1]和q->ptr[i+1]中
    int j;
    for(j=q->keynum;j>i;j--) //空出q->node[i+1]
     q->node[j+1]=q->node[j];
    q->node[i+1].key=r->key;
    q->node[i+1].ptr=ap; //前加入的结点，还没有儿子结点
    q->node[i+1].recptr=r;
    q->keynum++;
}//Insert

void NewRoot(BTree &T,Record *r,BTree ap)
{// 生成含信息(T,r,ap)的新的根结点*T，原T和ap为子树指针
BTree p;
p=(BTree)malloc(sizeof(BTNode));
p->node[0].ptr=T;
T=p;
if(T->node[0].ptr)
    T->node[0].ptr->parent=T;
T->parent=NULL;
T->keynum=1;
T->node[1].key=r->key;
T->node[1].recptr=r;
T->node[1].ptr=ap;
if(T->node[1].ptr)
    T->node[1].ptr->parent=T;
}//NewRoot

void split(BTree &q,BTree &ap)
{// 将结点q分裂成两个结点，前一半保留，后一半移入新生结点ap
int i,s=(m+1)/2;
ap=(BTree)malloc(sizeof(BTNode));//生成新结点ap
ap->node[0].ptr=q->node[s].ptr;//原来结点中间位置关键字相应指针指向的子树放到
                               //新生成结点的0棵子树中去
for(i=s+1;i<=m;i++) //后一半移入ap
   {
   ap->node[i-s]=q->node[i];
   if(ap->node[i-s].ptr)
       ap->node[i-s].ptr->parent=ap;
   }//for
   ap->keynum=m-s;
   ap->parent=q->parent;
   q->keynum=s-1; // q的前一半保留，修改keynum
}//split

void InsertBTree(BTree &T,Record *r,BTree q,int i)
{//在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K的指针r。若引起
   // 结点过大,则沿双亲链进行必要的结点分裂调整,使T仍是m阶B树。
BTree ap=NULL;
int finished=false;
int s;
Record *rx;
rx=r;
while(q&&!finished)
   {
    Insert(q,i,rx,ap);//将r->key、r和ap分别插入到q->key[i+1]、
                      //q->recptr[i+1]和q->ptr[i+1]中
    if(q->keynum<m)
        finished=true;
    else
      {//分裂结点*q
      s=(m+1)/2;
      rx=q->node[s].recptr;
      split(q,ap);//将q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]
                  //移入新结点*ap
      q=q->parent;
      if(q)
          i=Search(q,rx->key);//在双亲结点*q中查找rx->key的插入位置
      }//else
   }//while
if(!finished) //T是空树(参数q初值为NULL)或根结点已分裂为
              //结点*q和*ap
NewRoot(T,rx,ap);    
}//InsertBTree

Result SearchBTree(BTree T,KeyType K)
{// 在m阶B树T上查找关键字K，返回结果(pt,i,tag)。若查找成功，则特征值
// tag=1，指针pt所指结点中第i个关键字等于K；否则特征值tag=0，等于K的
// 关键字应插入在指针Pt所指结点中第i和第i+1个关键字之间。
BTree p=T,q=NULL; //初始化，p指向待查结点，q指向p的双亲
int found=false;
int i=0;
Result r;
while(p&&!found)
   {
   i=Search(p,K);//p->node[i].key≤K<p->node[i+1].key
   if(i>0&&p->node[i].key==K)
       found=true;
   else
     {
     q=p;
     p=p->node[i].ptr;//在子树中继续查找
     }//else
    }//while
   r.i=i;
   if(found)
     {
      r.pt=p;
      r.tag=1;
     }//if
   else
      {
       r.pt=q;
       r.tag=0;
      }//else
    return r;
}//SearchBTree

void print(BTNode c,int i) // TraverseDSTable()调用的函数
 {
   printf("(%d,%s)",c.node[i].key,c.node[i].recptr->others.info);
 }//print
void TraverseDSTable(BTree DT,void(*Visit)(BTNode,int))
{// 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数
// 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次
int i;
if(DT) //非空树
    {
      if(DT->node[0].ptr) // 有第0棵子树
         TraverseDSTable(DT->node[0].ptr,Visit);
      for(i=1;i<=DT->keynum;i++)
        {
         Visit(*DT,i);
         if(DT->node[i].ptr) // 有第i棵子树
         TraverseDSTable(DT->node[i].ptr,Visit);
        }//for
    }//if
}//TraverseDSTable

void InputBR(BTree &t,Record r[])
{
Result s;    
for(int i=0;i<N;i++)
   {
     s=SearchBTree(t,r[i].key);
     if(!s.tag)
       InsertBTree(t,&r[i],s.pt,s.i);
   }
}//InputBR
void UserSearch(BTree t)
{
int i;
Result s;
printf("\n请输入待查找记录的关键字: ");
scanf("%d",&i);
s=SearchBTree(t,i);
if(s.tag)
print(*(s.pt),s.i);
else
printf("没找到");
printf("\n");
}//UserSearch
void DeleteIt(BTree t,BTNode *dnode,int id)
{
if(dnode->keynum>=ceil(m/2))
   {
    dnode->keynum--;
    dnode->node[id].ptr=NULL;
   }//if被删关键字Ki所在结点的关键字数目不小于ceil(m/2)，则只需从结点中删除Ki和相应指针Ai，树的其它部分不变。
else if((dnode->keynum==(ceil(m/2)-1))&&((id+1)<(m-1))&&dnode->parent->node[id+1].ptr->keynum>(ceil(m/2)-1))
   {
    for(int i=1;i<m&&dnode->parent->node[i].key < dnode->parent->node[id+1].ptr->node[1].key;i++)
        dnode->node[i].key=dnode->parent->node[i].key;
    dnode->parent->node[1].key=dnode->parent->node[id+1].ptr->node[1].key;
    (dnode->parent->node[id+1].ptr->keynum)--;
   }//else if 被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。本次为与右兄弟调整
else if((dnode->keynum==(ceil(m/2)-1))&&((id-1)>0    )&&dnode->parent->node[id-1].ptr->keynum>(ceil(m/2)-1))
   {
    for(int i=1;i<m&&dnode->parent->node[i].key > dnode->parent->node[id-1].ptr->node[dnode->parent->node[id-1].ptr->keynum].key;i++)
        dnode->node[i].key=dnode->parent->node[i].key;
    dnode->parent->node[1].key=dnode->parent->node[id-1].ptr->node[dnode->parent->node[id-1].ptr->keynum].key;
    (dnode->parent->node[id-1].ptr->keynum)--;
   }//2-else if被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。本次为与左兄弟调整
else if((dnode->keynum==(ceil(m/2)-1))&&((id+1)<(m-1))&&dnode->parent->node[id+1].ptr->keynum==(ceil(m/2)-1))
   {
    do
      {
        BTree tmp;
        tmp=dnode;
       dnode->parent->node[id+1].ptr->node[2]=dnode->parent->node[id+1].ptr->node[1];
       dnode->parent->node[id+1].ptr->node[1]=dnode->parent->node[1];
       dnode->parent->node[id+1].ptr->keynum++;
       dnode->parent->node[id+1].ptr->node[0].ptr=dnode->node[1].ptr;
       dnode->parent->keynum--;
       dnode->parent->node[id].ptr=NULL;
       tmp=dnode;
       if(dnode->parent->keynum>=(ceil(m/2)-1))
           dnode->parent->node[1]=dnode->parent->node[2];
       dnode=dnode->parent;
       free(tmp);
      }while(dnode->keynum<(ceil(m/2)-1));    //双亲中keynum<
   }//3-else if被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，本次假设右兄弟存在
else if((dnode->keynum==(ceil(m/2)-1))&&(id-1)>0      &&dnode->parent->node[id-1].ptr->keynum==(ceil(m/2)-1))
   {
    do
      {
        BTree tmp;
        tmp=dnode;
       dnode->parent->node[id-1].ptr->node[2]=dnode->parent->node[id-1].ptr->node[1];
       dnode->parent->node[id-1].ptr->node[1]=dnode->parent->node[1];
       dnode->parent->node[id-1].ptr->keynum++;
       dnode->parent->node[id-1].ptr->node[0].ptr=dnode->node[1].ptr;
       dnode->parent->keynum--;
       dnode->parent->node[id].ptr=NULL;
       tmp=dnode;
       if(dnode->parent->keynum>=(ceil(m/2)-1))
           dnode->parent->node[1]=dnode->parent->node[2];
       dnode=dnode->parent;
       free(tmp);
      }while(dnode->keynum<(ceil(m/2)-1)); //双亲中keynum<
   }//4-else if被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，本次假设左兄弟存在
    else printf("Error!"); //出现异常
}//DeleteIt
void UserDelete(BTree t)
{
KeyType date;
Result s;
printf("Please input the date you want to delete:\n");
scanf("%d",&date);
s=SearchBTree(t,date);
if(!s.tag)  printf("Search failed,no such date\n");
else DeleteIt(t,s.pt,s.i);
}//UserDelete

int main()
{
Record r[N]={{24,"1"},{45,"2"},{53,"3"},{12,"4"},{37,"5"},
        {50,"6"},{61,"7"},{90,"8"},{100,"9"},{70,"10"},
        {3,"11"},{30,"12"},{26,"13"},{85,"14"},{3,"15"},
        {7,"16"}};    
BTree t;
InitDSTable(t);
InputBR(t,r);
printf("按关键字的顺序遍历B_树:\n");
TraverseDSTable(t,print);
UserSearch(t);
UserDelete(t);
TraverseDSTable(t,print);
DestroyDSTable(t);
return 1;
}

五、复杂度分析

B-树查找包含两种基本动作：

     ●在B-树上查找结点

     ●在结点中找关键字

前一操作在磁盘上进行，后一操作在内存进行。因此查找效率主要由前一操作决定。在磁盘上查找的次数取决于关键字结点在B-树上的层次数。

定理：若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B-树，其树高度h至多为logt((n+1)/2)+1，t= ceil(m/2)。也就是说根结点到关键字所在结点的路径上涉及的结点数不超过logt((n+1)/2)+1。推理如下：

29、B-树的插入、查找、删除 - 墨涵 - 墨涵天地

29、B-树的插入、查找、删除 - 墨涵 - 墨涵天地

29、B-树的插入、查找、删除 - 墨涵 - 墨涵天地

 

 

另一套代码，可执行，附带时间测试函数。

  1. /* btrees.h */ 
  2. /* 
  3. * 平衡多路树的一种重要方案。 
  4. * 在 1970 年由 R. Bayer 和 E. McCreight 发明。 
  5. */ 
  6.  
  7. #include <stdlib.h> 
  8. #include <stdio.h> 
  9. #include <time.h>
  10. #include <assert.h>
  11. #include <windows.h>
  12.  
  13. #define M 1
  14. /* B 树的阶，即非根节点中键的最小数目。 
  15. * 有些人把阶定义为非根节点中子树的最大数目。 
  16. */ 
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24. typedef int typekey; 
  25. typedef struct btnode {    /* B-Tree 节点 */ 
  26. 	int d;    /* 节点中键的数目 */ 
  27. 	typekey k[M+2];    /* 键 */ 
  28. 	char *v[M+2];    /* 值 */ 
  29. 	struct btnode *p[M+2+1];    /* 指向子树的指针 */ 
  30. } node, *btree; 
  31. /* 
  32. * 每个键的左子树中的所有的键都小于这个键， 
  33. * 每个键的右子树中的所有的键都大于等于这个键。 
  34. * 叶子节点中的每个键都没有子树。 
  35. */ 
  36.  
  37. /* 当 M 等于 1 时也称为 2-3 树 
  38. *    +----+----+ 
  39. *    | k0 | k1 |                     
  40. *  +-+----+----+--- 
  41. *  | p0 | p1 | p2 | 
  42. *  +----+----+----+ 
  43. */ 
  44. //extern int btree_disp; /* 查找时找到的键在节点中的位置 */ 
  45. //extern char * InsValue; /* 与要插的键相对应的值 */ 
  46.  
  47.  
  48. int btree_disp; /* 查找时找到的键在节点中的位置 */ 
  49. char * InsValue; /* 与要插的键相对应的值 */ 
  50. int flag; /* 节点增减标志 */ 
  51. int btree_level; /* 多路树的高度 */ 
  52. int btree_count; /* 多路树的键总数 */ 
  53. int node_sum;  /* 多路树的节点总数 */ 
  54. int level; /* 当前访问的节点所处的高度 */ 
  55. btree NewTree; /* 在节点分割的时候指向新建的节点 */ 
  56. typekey InsKey; /* 要插入的键 */ 
  57.  
  58.  
  59.  
  60.  
  61. btree search(typekey, btree); 
  62. btree insert(typekey,btree); 
  63. btree delete(typekey,btree); 
  64. int height(btree); 
  65. int count(btree); 
  66. double payload(btree); 
  67. btree deltree(btree); 
  68.  
  69. static void InternalInsert(typekey, btree); 
  70. static void InsInNode(btree, int); 
  71. static void SplitNode(btree, int); 
  72. static btree NewRoot(btree); 
  73.  
  74. static void InternalDelete(typekey, btree); 
  75. static void JoinNode(btree, int); 
  76. static void MoveLeftNode(btree t, int); 
  77. static void MoveRightNode(btree t, int); 
  78. static void DelFromNode(btree t, int); 
  79. static btree FreeRoot(btree); 
  80.  
  81. static btree delall(btree); 
  82. static void Error(int,typekey); 
  83.  
  84.  
  85.  
  86.  
  87. void out_txt(int * pt,int n);
  88.  
  89.  
  90. int *read_txt(int n);
  91.  
  92. /* end of btrees.h */


 

  1. /* btrees.c */ 
  2.  
  3. #include "btrees.h"
  4. btree search(typekey key, btree t) 
  5. { 
  6. 	int i,j,m; 
  7. 	level=btree_level-1; 
  8. 	while (level >= 0){ 
  9. 		for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m)); 
  10. 		if (key == t->k [ i ]){ 
  11. 			btree_disp = i; 
  12. 			return t; 
  13. 		} 
  14. 		if (key > t->k [ i ]) /* i == t->d-1 时有可能出现 */ 
  15. 			i++; 
  16. 		t = t->p[ i ]; 
  17. 		level--; 
  18. 	} 
  19. 	return NULL; 
  20. } 
  21.  
  22. btree insert(typekey key, btree t) 
  23. { 
  24. 	level=btree_level; 
  25. 	InternalInsert(key, t); 
  26. 	if (flag == 1)  /* 根节点满之后，它被分割成两个半满节点 */ 
  27. 		t=NewRoot(t);    /* 树的高度增加 */ 
  28. 	return t; 
  29. } 
  30.  
  31. void InternalInsert(typekey key, btree t) 
  32. { 
  33. 	int i,j,m; 
  34.  
  35. 	level--; 
  36. 	if (level < 0){ /* 到达了树的底部: 指出要做的插入 */ 
  37. 		NewTree = NULL; /* 这个键没有对应的子树 */ 
  38. 		InsKey = key; /* 导致底层的叶子节点增加键值+空子树对 */ 
  39. 		btree_count++; 
  40. 		flag = 1; /* 指示上层节点把返回的键插入其中 */ 
  41. 		return; 
  42. 	} 
  43. 	for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m)); 
  44. 	if (key == t->k[ i ]) { 
  45. 		Error(1,key); /* 键已经在树中 */ 
  46. 		flag = 0; 
  47. 		return; 
  48. 	} 
  49. 	if (key > t->k[ i ]) /* i == t->d-1 时有可能出现 */ 
  50. 		i++; 
  51. 	InternalInsert(key, t->p[ i ]); 
  52.  
  53. 	if (flag == 0) 
  54. 		return; 
  55. 	/* 有新键要插入到当前节点中 */ 
  56. 	if (t->d < 2*M) {/* 当前节点未满 */ 
  57. 		InsInNode(t, i); /* 把键值+子树对插入当前节点中 */ 
  58. 		flag = 0; /* 指示上层节点没有需要插入的键值+子树，插入过程结束 */ 
  59. 	} 
  60. 	else /* 当前节点已满，则分割这个页面并把键值+子树对插入当前节点中 */ 
  61. 		SplitNode(t, i); /* 继续指示上层节点把返回的键值+子树插入其中 */ 
  62. } 
  63.  
  64. /* 
  65. * 把一个键和对应的右子树插入一个节点中 
  66. */ 
  67. void InsInNode(btree t, int d) 
  68. { 
  69. 	int i; 
  70. 	/* 把所有大于要插入的键值的键和对应的右子树右移 */ 
  71. 	for(i = t->d; i > d; i--){ 
  72. 		t->k[ i ] = t->k[i-1]; 
  73. 		t->v[ i ] = t->v[i-1]; 
  74. 		t->p[i+1] = t->p[ i ]; 
  75. 	} 
  76. 	/* 插入键和右子树 */ 
  77. 	t->k[ i ] = InsKey; 
  78. 	t->p[i+1] = NewTree; 
  79. 	t->v[ i ] = InsValue; 
  80. 	t->d++; 
  81. } 
  82. /* 
  83. * 前件是要插入一个键和对应的右子树，并且本节点已经满 
  84. * 导致分割这个节点，插入键和对应的右子树， 
  85. * 并向上层返回一个要插入键和对应的右子树 
  86. */ 
  87. void SplitNode(btree t, int d) 
  88. {     
  89. 	int i,j; 
  90. 	btree temp; 
  91. 	typekey temp_k; 
  92. 	char *temp_v; 
  93. 	/* 建立新节点 */ 
  94. 	temp = (btree)malloc(sizeof(node)); 
  95. 	/* 
  96. 	*   +---+--------+-----+-----+--------+-----+ 
  97. 	*   | 0 | ...... |  M  | M+1 | ...... |2*M-1| 
  98. 	*   +---+--------+-----+-----+--------+-----+ 
  99. 	*   |<-      M+1     ->|<-        M-1     ->|   
  100. 	*/ 
  101. 	if (d > M) { /* 要插入当前节点的右半部分 */ 
  102. 		/* 把从 2*M-1 到 M+1 的 M-1 个键值+子树对转移到新节点中, 
  103. 		* 并且为要插入的键值+子树空出位置 */ 
  104. 		for(i=2*M-1,j=M-1; i>=d; i--,j--) { 
  105. 			temp->k[j] = t->k[ i ]; 
  106. 			temp->v[j] = t->v[ i ]; 
  107. 			temp->p[j+1] = t->p[i+1]; 
  108. 		} 
  109. 		for(i=d-1,j=d-M-2; j>=0; i--,j--) { 
  110. 			temp->k[j] = t->k[ i ]; 
  111. 			temp->v[j] = t->v[ i ]; 
  112. 			temp->p[j+1] = t->p[i+1]; 
  113. 		} 
  114. 		/* 把节点的最右子树转移成新节点的最左子树 */ 
  115. 		temp->p[0] = t->p[M+1]; 
  116. 		/* 在新节点中插入键和右子树 */ 
  117. 		temp->k[d-M-1] = InsKey; 
  118. 		temp->p[d-M] = NewTree; 
  119. 		temp->v[d-M-1] = InsValue; 
  120. 		/* 设置要插入上层节点的键和值 */ 
  121. 		InsKey = t->k[M]; 
  122. 		InsValue = t->v[M]; 
  123.  
  124. 	} 
  125. 	else { /* d <= M */ 
  126. 		/* 把从 2*M-1 到 M 的 M 个键值+子树对转移到新节点中 */ 
  127. 		for(i=2*M-1,j=M-1; j>=0; i--,j--) { 
  128. 			temp->k[j] = t->k[ i ]; 
  129. 			temp->v[j] = t->v[ i ]; 
  130. 			temp->p[j+1] = t->p[i+1]; 
  131. 		} 
  132. 		if (d == M) /* 要插入当前节点的正中间 */ 
  133. 			/* 把要插入的子树作为新节点的最左子树 */ 
  134. 			temp->p[0] = NewTree; 
  135. 		/* 直接把要插入的键和值返回给上层节点 */ 
  136. 		else { /* (d<M) 要插入当前节点的左半部分 */ 
  137. 			/* 把节点当前的最右子树转移成新节点的最左子树 */ 
  138. 			temp->p[0] = t->p[M]; 
  139. 			/* 保存要插入上层节点的键和值 */ 
  140. 			temp_k = t->k[M-1]; 
  141. 			temp_v = t->v[M-1]; 
  142. 			/* 把所有大于要插入的键值的键和对应的右子树右移 */ 
  143. 			for(i=M-1; i>d; i--) { 
  144. 				t->k[ i ] = t->k[i-1]; 
  145. 				t->v[ i ] = t->v[i-1]; 
  146. 				t->p[i+1] = t->p[ i ]; 
  147. 			} 
  148. 			/* 在节点中插入键和右子树 */ 
  149. 			t->k[d] = InsKey; 
  150. 			t->p[d+1] = NewTree; 
  151. 			t->v[d] = InsValue; 
  152. 			/* 设置要插入上层节点的键和值 */ 
  153. 			InsKey = temp_k; 
  154. 			InsValue = temp_v; 
  155. 		} 
  156. 	} 
  157. 	t->d =M; 
  158. 	temp->d = M; 
  159. 	NewTree = temp; 
  160. 	node_sum++; 
  161. } 
  162.  
  163. btree delete(typekey key, btree t) 
  164. { 
  165. 	level=btree_level; 
  166. 	InternalDelete(key, t); 
  167. 	if (t->d == 0) 
  168. 		/* 根节点的子节点合并导致根节点键的数目随之减少， 
  169. 		* 当根节点中没有键的时候，只有它的最左子树可能非空 */ 
  170. 		t=FreeRoot(t); 
  171. 	return t; 
  172. } 
  173.  
  174. void InternalDelete(typekey key, btree t) 
  175. { 
  176. 	int i,j,m; 
  177. 	btree l,r; 
  178. 	int lvl; 
  179.  
  180. 	level--; 
  181. 	if (level < 0) { 
  182. 		Error(0,key); /* 在整个树中未找到要删除的键 */ 
  183. 		flag = 0; 
  184. 		return; 
  185. 	} 
  186. 	for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m)); 
  187. 	if (key == t->k[ i ]) { /* 找到要删除的键 */ 
  188. 		if (t->v[ i ] != NULL) 
  189. 			free(t->v[ i ]); /* 释放这个节点包含的值 */ 
  190. 		if (level == 0) { /* 有子树为空则这个键位于叶子节点 */ 
  191. 			DelFromNode(t,i); 
  192. 			btree_count--; 
  193. 			flag = 1; 
  194. 			/* 指示上层节点本子树的键数量减少 */ 
  195. 			return; 
  196. 		} else { /* 这个键位于非叶节点 */ 
  197. 			lvl = level-1; 
  198. 			/* 找到前驱节点 */ 
  199. 			r = t->p[ i ]; 
  200. 			while (lvl > 0)  { 
  201. 				r = r->p[r->d]; 
  202. 				lvl--; 
  203. 			} 
  204. 			t->k[ i ]=r->k[r->d-1]; 
  205. 			t->v[ i ]=r->v[r->d-1]; 
  206. 			r->v[r->d-1]=NULL; 
  207. 			key = r->k[r->d-1]; 
  208. 		} 
  209. 	} 
  210. 	else if (key > t->k[ i ]) /* i == t->d-1 时有可能出现 */ 
  211. 		i++;          
  212. 	InternalDelete(key,t->p[ i ]); 
  213. 	/* 调整平衡 */ 
  214. 	if (flag == 0) 
  215. 		return; 
  216. 	if (t->p[ i ]->d < M) { 
  217. 		if (i == t->d) /* 在最右子树中发生了删除 */ 
  218. 			i--; /* 调整最右键的左右子树平衡 */ 
  219. 		l = t->p [ i ]; 
  220. 		r = t->p[i+1]; 
  221. 		if (r->d > M) 
  222. 			MoveLeftNode(t,i); 
  223. 		else if(l->d > M) 
  224. 			MoveRightNode(t,i); 
  225. 		else { 
  226. 			JoinNode(t,i); 
  227. 			/* 继续指示上层节点本子树的键数量减少 */ 
  228. 			return; 
  229. 		} 
  230. 		flag = 0; 
  231. 		/* 指示上层节点本子树的键数量没有减少，删除过程结束 */ 
  232. 	} 
  233. } 
  234.  
  235. /* 
  236. * 合并一个节点的某个键对应的两个子树 
  237. */ 
  238. void JoinNode(btree t, int d) 
  239. { 
  240. 	btree l,r; 
  241. 	int i,j; 
  242. 	l = t->p[d]; 
  243. 	r = t->p[d+1]; 
  244.  
  245. 	/* 把这个键下移到它的左子树 */ 
  246. 	l->k[l->d] = t->k[d]; 
  247. 	l->v[l->d] = t->v[d]; 
  248. 	/* 把右子树中的所有键值和子树转移到左子树 */ 
  249. 	for (j=r->d-1,i=l->d+r->d; j >= 0 ; j--,i--) { 
  250. 		l->k[ i ] = r->k[j]; 
  251. 		l->v[ i ] = r->v[j]; 
  252. 		l->p[ i ] = r->p[j]; 
  253. 	} 
  254. 	l->p[l->d+r->d+1] = r->p[r->d]; 
  255. 	l->d += r->d+1; 
  256. 	/* 释放右子树的节点 */ 
  257. 	free(r); 
  258. 	/* 把这个键右边的键和对应的右子树左移 */ 
  259. 	for (i=d; i < t->d-1; i++) { 
  260. 		t->k[ i ] = t->k[i+1]; 
  261. 		t->v[ i ] = t->v[i+1]; 
  262. 		t->p[i+1] = t->p[i+2]; 
  263. 	} 
  264. 	t->d--; 
  265. 	node_sum--; 
  266. } 
  267. /* 
  268. * 从一个键的右子树向左子树转移一些键，使两个子树平衡 
  269. */ 
  270. void MoveLeftNode(btree t, int d) 
  271. { 
  272. 	btree l,r; 
  273. 	int m; /* 应转移的键的数目 */ 
  274. 	int i,j; 
  275. 	l = t->p[d]; 
  276. 	r = t->p[d+1]; 
  277. 	m = (r->d - l->d)/2; 
  278.  
  279. 	/* 把这个键下移到它的左子树 */ 
  280. 	l->k[l->d] = t->k[d]; 
  281. 	l->v[l->d] = t->v[d]; 
  282. 	/* 把右子树的最左子树转移成左子树的最右子树 
  283. 	* 从右子树向左子树移动 m-1 个键+子树对 */ 
  284. 	for (j=m-2,i=l->d+m-1; j >= 0; j--,i--) { 
  285. 		l->k[ i ] = r->k[j]; 
  286. 		l->v[ i ] = r->v[j]; 
  287. 		l->p[ i ] = r->p[j]; 
  288. 	} 
  289. 	l->p[l->d+m] = r->p[m-1]; 
  290. 	/* 把右子树的最左键提升到这个键的位置上 */ 
  291. 	t->k[d] = r->k[m-1]; 
  292. 	t->v[d] = r->v[m-1]; 
  293. 	/* 把右子树中的所有键值和子树左移 m 个位置 */ 
  294. 	r->p[0] = r->p[m]; 
  295. 	for (i=0; i<r->d-m; i++) { 
  296. 		r->k[ i ] = r->k[i+m]; 
  297. 		r->v[ i ] = r->v[i+m]; 
  298. 		r->p[ i ] = r->p[i+m]; 
  299. 	} 
  300. 	r->p[r->d-m] = r->p[r->d]; 
  301. 	l->d+=m; 
  302. 	r->d-=m; 
  303. } 
  304. /* 
  305. * 从一个键的左子树向右子树转移一些键，使两个子树平衡 
  306. */ 
  307. void MoveRightNode(btree t, int d) 
  308. { 
  309. 	btree l,r; 
  310. 	int m; /* 应转移的键的数目 */ 
  311. 	int i,j; 
  312. 	l = t->p[d]; 
  313. 	r = t->p[d+1]; 
  314.  
  315. 	m = (l->d - r->d)/2; 
  316. 	/* 把右子树中的所有键值和子树右移 m 个位置 */ 
  317. 	r->p[r->d+m]=r->p[r->d]; 
  318. 	for (i=r->d-1; i>=0; i--) { 
  319. 		r->k[i+m] = r->k[ i ]; 
  320. 		r->v[i+m] = r->v[ i ]; 
  321. 		r->p[i+m] = r->p[ i ]; 
  322. 	} 
  323. 	/* 把这个键下移到它的右子树 */ 
  324. 	r->k[m-1] = t->k[d]; 
  325. 	r->v[m-1] = t->v[d]; 
  326. 	/* 把左子树的最右子树转移成右子树的最左子树 */ 
  327. 	r->p[m-1] = l->p[l->d]; 
  328. 	/* 从左子树向右子树移动 m-1 个键+子树对 */ 
  329. 	for (i=l->d-1,j=m-2; j>=0; j--,i--) { 
  330. 		r->k[j] = l->k[ i ]; 
  331. 		r->v[j] = l->v[ i ]; 
  332. 		r->p[j] = l->p[ i ]; 
  333. 	} 
  334. 	/* 把左子树的最右键提升到这个键的位置上 */ 
  335. 	t->k[d] = l->k[ i ]; 
  336. 	t->v[d] = l->v[ i ]; 
  337. 	l->d-=m; 
  338. 	r->d+=m; 
  339. } 
  340. /* 
  341. * 把一个键和对应的右子树从一个节点中删除 
  342. */ 
  343. void DelFromNode(btree t, int d) 
  344. { 
  345. 	int i; 
  346. 	/* 把所有大于要删除的键值的键左移 */ 
  347. 	for(i=d; i < t->d-1; i++) { 
  348. 		t->k[ i ] = t->k[i+1]; 
  349. 		t->v[ i ] = t->v[i+1]; 
  350. 	} 
  351. 	t->d--; 
  352. } 
  353. /* 
  354. * 建立有两个子树和一个键的根节点 
  355. */ 
  356. btree NewRoot(btree t) 
  357. { 
  358. 	btree temp; 
  359. 	temp = (btree)malloc(sizeof(node)); 
  360. 	temp->d = 1; 
  361. 	temp->p[0] = t; 
  362. 	temp->p[1] = NewTree; 
  363. 	temp->k[0] = InsKey; 
  364. 	temp->v[0] = InsValue; 
  365. 	btree_level++; 
  366. 	node_sum++; 
  367. 	return(temp); 
  368. } 
  369. /* 
  370. * 释放根节点，并返回它的最左子树 
  371. */ 
  372. btree FreeRoot(btree t) 
  373. { 
  374. 	btree temp; 
  375. 	temp = t->p[0]; 
  376. 	free(t); 
  377. 	btree_level--; 
  378. 	node_sum--; 
  379. 	return temp; 
  380. } 
  381.  
  382. void Error(int f,typekey key) 
  383. { 
  384. 	if (f) 
  385. 		printf("Btrees error: Insert %d!\n",key); 
  386. 	else 
  387. 		printf("Btrees error: delete %d!\n",key); 
  388. } 
  389.  
  390. int height(btree t) 
  391. { 
  392. 	return btree_level; 
  393. } 
  394.  
  395. int count(btree t) 
  396. { 
  397. 	return btree_count; 
  398. } 
  399. double payload(btree t) 
  400. { 
  401. 	if (node_sum==0) 
  402. 		return 1; 
  403. 	return (double)btree_count/(node_sum*(2*M)); 
  404. } 
  405. btree deltree (btree t) 
  406. {     
  407. 	level=btree_level; 
  408. 	btree_level = 0; 
  409. 	return delall(t); 
  410.  
  411. } 
  412. btree delall(btree t) 
  413. { 
  414. 	int i; 
  415. 	level--; 
  416. 	if (level >= 0) { 
  417. 		for (i=0; i < t->d; i++) 
  418. 			if (t->v[ i ] != NULL) 
  419. 				free(t->v[ i ]); 
  420. 		if (level > 0) 
  421. 			for (i=0; i<= t->d ; i++) 
  422. 				t->p[ i ]=delall(t->p[ i ]); 
  423. 		free(t); 
  424. 	} 
  425. 	return NULL; 
  426. } 
  427.  
  428. /* end of btrees.c */ 
  429.  
  430.  
  431. void out_txt(int * pt,int n)
  432. {
  433. 	FILE *fp_b;
  434.  
  435. 	int i;
  436.  
  437.  
  438. 	if((fp_b=fopen("btree2.txt","a"))==NULL)
  439. 	{
  440. 		printf("cannot open this file\n");
  441. 		exit(0);
  442. 	}
  443.  
  444. 	//fprintf(fp_b,"%d\t",bucket_volumes);
  445. 	for (i=0;i<n;i++)
  446. 	{
  447. 		fprintf(fp_b,"%d\t",pt[i]);
  448. 	}
  449. 	fprintf(fp_b,"\r");
  450.  
  451. }
  452.  
  453.  
  454. int *read_txt(int n)
  455. {
  456.  
  457. 	FILE *fp;
  458. 	int i;
  459. 	int *a=(int *)malloc(n*sizeof(int));
  460. 	if ((fp = fopen("F:\\text_data.txt","rt")) == NULL)
  461. 	{
  462. 		printf("open file failed!\n");
  463. 		exit(1);
  464. 	}
  465. 	for (i=0; i<n; i++)
  466. 	{
  467. 		fscanf(fp,"%d", &a[i]);
  468. 		//              fprintf(fp,"%d ",a[i]);
  469. 	}
  470. 	fclose(fp);
  471. 	return a;
  472. }


 

  1. #include "btrees.h"
  2. #define key_num 1000
  3. void main()
  4. {
  5.  
  6.  
  7.  
  8.  
  9. 	int * key_array;
  10. 	int i;
  11. int pt[5];
  12. 	btree root,temp;
  13. long long sf1,sf2,sf3;
  14. LARGE_INTEGER f1,f2,f3,f5,f4,f6;
  15.  
  16. InsValue = NULL; /* 与要插的键相对应的值 */ 
  17.  /* 节点增减标志 */ 
  18. btree_level = 0; /* 多路树的高度 */ 
  19. btree_count = 0; /* 多路树的键总数 */ 
  20. node_sum = 0;  /* 多路树的节点总数 */ 
  21.  
  22. key_array=read_txt(key_num);
  23. 	temp = (btree)malloc(sizeof(node)); 
  24. 	temp->d = 0; 
  25. 	temp->p[0] = NewTree; 
  26. 	temp->p[1] = NewTree; 
  27. 	temp->k[0] = InsKey; 
  28. 	temp->v[0] = InsValue; 
  29.  
  30. 	root=temp;
  31.  
  32.  
  33.  
  34.  
  35. QueryPerformanceCounter(&f1);
  36. 	for (i=0;i<key_num;i++)
  37. 	{
  38. 		root=insert(key_array[i],root);
  39.  
  40. 	}
  41.  
  42. QueryPerformanceCounter(&f2);
  43. QueryPerformanceCounter(&f3);
  44.  
  45. 		for (i=0;i<key_num;i++)
  46. 		{
  47.  
  48. 		search(key_array[i],root);
  49.  
  50.  
  51. 			
  52.  
  53. 		}
  54.  
  55. QueryPerformanceCounter(&f4);
  56. QueryPerformanceCounter(&f5);
  57. 		for (i=0;i<key_num;i++)
  58. 		{
  59.  
  60. 			root=delete(key_array[i],root);
  61. 			
  62. 		}
  63.  
  64. QueryPerformanceCounter(&f6);
  65.  
  66.  
  67. sf1=f2.QuadPart-f1.QuadPart-750;
  68. sf2=f4.QuadPart-f3.QuadPart-750;
  69. sf3=f6.QuadPart-f5.QuadPart-750;
  70.  
  71. pt[0]=M+2;
  72. pt[1]=key_num;
  73. pt[2]=(sf1/1000)-7;
  74. pt[3]=(sf2/1000)-7;
  75. pt[4]=(sf3/1000)-7;
  76.  
  77. out_txt(pt,5);
  78.  
  79. Sleep(1000);
  80.  
  81. }


 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/766287
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号