我写的一个btree实现的代码

Serenaiad

一直没有找到实现的代码，前段时间写了一个，数据库里的索引就是用的整个东西实现的

1. 
   
2.      1  /* btree implementation example ,any bug send mail to serenaiad@126.com
   
3.      2  
   
4.      3  You can modify,destribute this code , please reserve this note when destribute this code.
   
5.      4  */
   
6.      5  #include <stdio.h>
   
7.      6  #include <stdlib.h>
   
8.      7
   
9.      8
   
10.      9  #define NODESIZE       3                   //number of values  each node
    
11.     10  #define TOTALNODES     100                 //number of nodes
    
12.     11
    
13.     12
    
14.     13  typedef enum {
    
15.     14  inner,leaf
    
16.     15  } nodetype;
    
17.     16
    
18.     17  typedef struct{
    
19.     18  int nodeindex;
    
20.     19  int valueindex;
    
21.     20  int pointer;
    
22.     21  } valuelocation;
    
23.     22
    
24.     23  typedef struct{
    
25.     24  nodetype type;
    
26.     25  int valuecount;
    
27.     26  int values[NODESIZE];
    
28.     27  int pointers[NODESIZE+1];
    
29.     28  } node;
    
30.     29
    
31.     30  int freenode;               //the first free node
    
32.     31  int rootnode;               //root node
    
33.     32  node nodes[TOTALNODES];     //nodes array
    
34.     33
    
35.     34
    
36.     35  int CreateBtree();
    
37.     36  int LoadBtree();
    
38.     37  int WriteBtree();
    
39.     38  int InsertValue(int value,int pointer);
    
40.     39  int DeleteValue(int value);
    
41.     40  char *GetSysTime();
    
42.     41
    
43.     42
    
44.     43  /* find the node index for new value to insert  ,return  -1 if the btree is empty(no value in it) */
    
45.     44  int FindNewValueNode(int value,int path[]);
    
46.     45
    
47.     46  /* 一个中间节点中，要搜索指定的值，需要查找向那个指针所指向的节点去搜索，
    
48.     47  这里返回下一级节点指针在指针数组中的index                       */
    
49.     48  int FindValuePtIndex(int value,node* n);
    
50.     49
    
51.     50  /* 把一个节点，指针对插入到一个中间节点去
    
52.     51  index: 这个节点的index, value: 值， pointer 指针
    
53.     52  path: 从根节点到叶节点的全路径
    
54.     53  */
    
55.     54  void InsertPtToInnerNode(int index,int value,int pointer, int path[]);
    
56.     55
    
57.     56  void DeletePtInnerNode(int index,int minvalue,int pointer,int path[]);
    
58.     57  void PrintBtree();
    
59.     58  void PrintNode(int index);
    
60.     59
    
61.     60  /* 从空余节点中取一个全新的节点 */
    
62.     61  int GetFreeNode();
    
63.     62  int ReleaseNode(int index);
    
64.     63
    
65.     64  /* 查找某值，如果值存在，返回这个值所在节点的index , 如果不存在，返回 -1 */
    
66.     65  valuelocation FindValue(int value);
    
67.     66
    
68.     67  /* 当某个根节点的最小值改变了以后，他的某个父节点的值需要调整
    
69.     68  path - access path ; indexstart - 从哪一级开始 ; val - 老值 ; newval - 新值 */
    
70.     69  void UpdateAncestorNodeMinValue(int path[],int posstart,int val,int newval);
    
71.     70  /* 经过一个节点可以访问到的最小值 */
    
72.     71  int MinValueThroughNode(int index);
    
73.     72  void Usage();
    
74.     73  void test();
    
75.     74  int FindNodeValueIndex(int value, node* n);
    
76.     75  void DeleteValueInLeafNode(node* n,int value);
    
77.     76  int GetPosInAccessPath(int index , int path[]);
    
78.     77  void DeletePointerInInnerNode(node* n,int index, int path[], int pointer,int minvalue);
    
79.     78  //验证一个节点的的值和指针是否正确
    
80.     79  int VerifyNode(int index);
    
81.     80  int VerifyBtree();
    
82.     81
    
83.     82  int main(int argc, char* argv[])
    
84.     83  {
    
85.     84  valuelocation l;
    
86.     85          if(argc==1)
    
87.     86          {
    
88.     87                  Usage();
    
89.     88                  return 0;
    
90.     89          }
    
91.     90          if(strcmp(argv[1],"-create")==0)
    
92.     91                  CreateBtree();
    
93.     92          if(strcmp(argv[1],"-i")==0)
    
94.     93          {
    
95.     94                  LoadBtree();
    
96.     95                  if(InsertValue(atoi(argv[2]),atoi(argv[3]))!=0)
    
97.     96                          printf("Insert Value Failed.\n");
    
98.     97                  WriteBtree();
    
99.     98          }
    
100.     99          if(strcmp(argv[1],"-p")==0)
     
101.    100                  PrintBtree();
     
102.    101          if(strcmp(argv[1],"-pn")==0)
     
103.    102          {
     
104.    103                  LoadBtree();
     
105.    104                  PrintNode(atoi(argv[2]));
     
106.    105          }
     
107.    106          if(strcmp(argv[1],"-test")==0)
     
108.    107                  test();
     
109.    108          if(strcmp(argv[1],"-f")==0)
     
110.    109          {
     
111.    110                  LoadBtree();
     
112.    111                  l=FindValue(atoi(argv[2]));
     
113.    112                  if(l.nodeindex==-1 )
     
114.    113                          printf("Value %d not found.\n",atoi(argv[2]));
     
115.    114                  else
     
116.    115                          printf("Value %d found , pointer:%d\n",atoi(argv[2]),l.pointer);
     
117.    116          }
     
118.    117          if(strcmp(argv[1],"-d")==0)
     
119.    118          {
     
120.    119                  LoadBtree();
     
121.    120                  if(DeleteValue(atoi(argv[2]))!=0)
     
122.    121                          printf("delete value failed.\n");
     
123.    122                  WriteBtree();
     
124.    123          }
     
125.    124          if(strcmp(argv[1],"-verify")==0)
     
126.    125          {
     
127.    126                  LoadBtree();
     
128.    127                  VerifyBtree();
     
129.    128          }
     
130.    129          return 0;
     
131.    130  }
     
132.    131
     
133.    132  int CreateBtree()
     
134.    133  {
     
135.    134  FILE* f;
     
136.    135  node n;
     
137.    136  int itmp;
     
138.    137  int i;
     
139.    138          if((f=fopen("btree.dat","w"))==NULL)
     
140.    139          {
     
141.    140                  printf("Can't open file!\n");
     
142.    141                  return 1;
     
143.    142          }
     
144.    143          freenode=0;
     
145.    144          rootnode=-1;
     
146.    145          fwrite(&freenode,1,sizeof(int),f);
     
147.    146          fwrite(&rootnode,1,sizeof(int),f);
     
148.    147          for (i=0;i<TOTALNODES;i++)
     
149.    148          {
     
150.    149                  n.pointers[NODESIZE]=i+1;
     
151.    150                  if(i==(TOTALNODES-1))
     
152.    151                          n.pointers[NODESIZE]=-1;
     
153.    152                  fwrite(&n,1,sizeof(n),f);
     
154.    153          }
     
155.    154          fclose(f);
     
156.    155  }
     
157.    156
     
158.    157  void Usage()
     
159.    158  {
     
160.    159          printf("Usage: btree -create | -i value | -d value | -e value\n");
     
161.    160          printf("-create : create new btree file.\n");
     
162.    161          printf("-p : print btree.\n");
     
163.    162          printf("-pn nodeindex : print node nodeindex\n");
     
164.    163          printf("-i value : insert new value.\n");
     
165.    164          printf("-d value : delete a value.\n");
     
166.    165          printf("-f value : find if value exists.\n");
     
167.    166          printf("-verify : verify if the btree is correct.\n");
     
168.    167  }
     
169.    168
     
170.    169  int LoadBtree()
     
171.    170  {
     
172.    171  FILE* f;
     
173.    172          if((f=fopen("btree.dat","r"))==NULL)
     
174.    173          {
     
175.    174                  printf("Can't open file.\n");
     
176.    175                  return 1;
     
177.    176          }
     
178.    177          fread(&freenode,1,sizeof(int),f);
     
179.    178          fread(&rootnode,1,sizeof(int),f);
     
180.    179          fread(nodes,1,sizeof(node)*TOTALNODES,f);
     
181.    180          fclose(f);
     
182.    181          return 0;
     
183.    182  }
     
184.    183  int WriteBtree()
     
185.    184  {
     
186.    185  FILE* f;
     
187.    186          if((f=fopen("btree.dat","w"))==NULL)
     
188.    187          {
     
189.    188                  printf("Can't open file.\n");
     
190.    189                  return 1;
     
191.    190          }
     
192.    191          fwrite(&freenode,1,sizeof(int),f);
     
193.    192          fwrite(&rootnode,1,sizeof(int),f);
     
194.    193          fwrite(nodes,1,sizeof(node)*TOTALNODES,f);
     
195.    194          fclose(f);
     
196.    195          return 0;
     
197.    196  }
     
198.    197
     
199.    198  int InsertValue(int value,int pointer)
     
200.    199  {
     
201.    200  node* n;
     
202.    201  node* newNode;
     
203.    202  node* pn;
     
204.    203  int i,inode,insertPos,ni,pi;
     
205.    204  int tmpvalues[NODESIZE+1];
     
206.    205  int tmppointers[NODESIZE+1];
     
207.    206  int halfsize=(NODESIZE+1)/2;
     
208.    207  int path[101];
     
209.    208  int pathindex;
     
210.    209  int minval,newval;
     
211.    210  int pos;
     
212.    211
     
213.    212          insertPos=-1;
     
214.    213          inode=FindNewValueNode(value,path); //先找出需要往那个节点里插入值
     
215.    214
     
216.    215          if( inode==-1) // 如果这是btree中的第一个值
     
217.    216          {
     
218.    217                  ni=GetFreeNode();
     
219.    218                  n=nodes+ni;
     
220.    219                  rootnode=ni;
     
221.    220                  n->type=leaf;
     
222.    221                  n->valuecount=1;
     
223.    222                  n->values[0]=value;
     
224.    223                  n->pointers[0]=pointer;
     
225.    224                  n->pointers[NODESIZE]=-1;
     
226.    225          }
     
227.    226          else
     
228.    227          {
     
229.    228                  n=nodes+inode;
     
230.    229                  for(i=0;i<n->valuecount;i++)
     
231.    230                  {
     
232.    231                          if(value==n->values[i])
     
233.    232                                  return 1;
     
234.    233                  }
     
235.    234                  for(i=1;i<=path[0];i++)
     
236.    235                  {
     
237.    236                          if(inode==path[i])
     
238.    237                                  pathindex=i;
     
239.    238                  }
     
240.    239                  if (n->valuecount==NODESIZE) // the leaf node needs to split
     
241.    240                  {
     
242.    241                          ni=GetFreeNode();
     
243.    242                          newNode=nodes+ni;
     
244.    243                          newNode->type=leaf;
     
245.    244                          newNode->valuecount=NODESIZE+1-halfsize;
     
246.    245                          for(i=0;i<NODESIZE;i++)
     
247.    246                          {
     
248.    247                                  if(value< n->values[i])
     
249.    248                                  {
     
250.    249                                          insertPos=i;
     
251.    250                                          break;
     
252.    251                                  }
     
253.    252                          }
     
254.    253                          if(insertPos==-1)
     
255.    254                                  insertPos=NODESIZE;
     
256.    255                          if (insertPos==0)
     
257.    256                          {
     
258.    257                                  minval=n->values[0];
     
259.    258                                  newval=value;
     
260.    259                                  UpdateAncestorNodeMinValue(path,pathindex-1,minval,newval);
     
261.    260                          }
     
262.    261                          for(i=0;i<insertPos;i++)
     
263.    262                          {
     
264.    263                                  tmpvalues[i]=n->values[i];
     
265.    264                                  tmppointers[i]=n->pointers[i];
     
266.    265                          }
     
267.    266                          tmpvalues[insertPos]=value;
     
268.    267                          tmppointers[insertPos]=pointer;
     
269.    268                          for(i=NODESIZE-1;i>=insertPos;i--)
     
270.    269                          {
     
271.    270                                  tmpvalues[i+1]=n->values[i];
     
272.    271                                  tmppointers[i+1]=n->pointers[i];
     
273.    272                          }
     
274.    273                          for(i=0;i<halfsize;i++)
     
275.    274                          {
     
276.    275                                  n->values[i]=tmpvalues[i];
     
277.    276                                  n->pointers[i]=tmppointers[i];
     
278.    277                          }
     
279.    278                          n->valuecount=halfsize;
     
280.    279                          for(i=halfsize;i<NODESIZE+1;i++)
     
281.    280                          {
     
282.    281                                  newNode->values[i-halfsize]=tmpvalues[i];
     
283.    282                                  newNode->pointers[i-halfsize]=tmppointers[i];
     
284.    283                          }
     
285.    284                          newNode->pointers[NODESIZE]=n->pointers[NODESIZE];
     
286.    285                          n->pointers[NODESIZE]=ni;
     
287.    286                          if(inode==path[1]) // if the node is root node
     
288.    287                          {
     
289.    288                                  pi=GetFreeNode();
     
290.    289                                  rootnode=pi;  // change new root node
     
291.    290                                  pn=nodes+pi;
     
292.    291                                  pn->type=inner;
     
293.    292                                  pn->valuecount=1;
     
294.    293                                  pn->values[0]=newNode->values[0];
     
295.    294                                  pn->pointers[0]=inode;
     
296.    295                                  pn->pointers[1]=ni;
     
297.    296                          }
     
298.    297                          else // 如果这个叶节点不是根节点，那么需要向它的父节点插入值和指针
     
299.    298                          {
     
300.    299                                  InsertPtToInnerNode(path[pathindex-1],newNode->values[0],ni,path);
     
301.    300                          }
     
302.    301
     
303.    302                  }
     
304.    303                  else  // the leaf node has enough space
     
305.    304                  {
     
306.    305                          for(i=0;i < n->valuecount;i++)
     
307.    306                          {
     
308.    307                                  if(value < n->values[i])
     
309.    308                                  {
     
310.    309                                          insertPos=i;
     
311.    310                                          break;
     
312.    311                                  }
     
313.    312                          }
     
314.    313                          if(insertPos==-1)
     
315.    314                          {
     
316.    315                                  insertPos=n->valuecount;
     
317.    316                          }
     
318.    317                          if(insertPos==0)
     
319.    318                          {
     
320.    319                                  minval=n->values[0];
     
321.    320                                  newval=value;
     
322.    321                          }
     
323.    322                          for(i=n->valuecount;i>insertPos;i--)
     
324.    323                          {
     
325.    324                                  n->values[i]=n->values[i-1];
     
326.    325                                  n->pointers[i]=n->pointers[i-1];
     
327.    326                          }
     
328.    327                          n->values[insertPos]=value;
     
329.    328                          n->pointers[insertPos]=pointer;
     
330.    329                          n->valuecount=n->valuecount+1;
     
331.    330                          if(insertPos==0)
     
332.    331                          {
     
333.    332                                  UpdateAncestorNodeMinValue(path,pathindex-1,minval,newval);
     
334.    333                          }
     
335.    334                  }
     
336.    335          }
     
337.    336          return 0;
     
338.    337  }
     
339.    338
     
340. 
     

复制代码

Serenaiad

1. 
   
2.    339
   
3.    340  int FindNewValueNode(int value,int path[])
   
4.    341  {
   
5.    342  node* n;
   
6.    343  node* root;
   
7.    344  int i,ni;
   
8.    345          if (rootnode== -1 )
   
9.    346                  return -1;
   
10.    347          else
    
11.    348          {
    
12.    349                  path[0]=1;
    
13.    350                  path[1]=rootnode;
    
14.    351                  root=nodes+rootnode;
    
15.    352                  n=root;
    
16.    353                  ni=rootnode;
    
17.    354                  while(n->type==inner)
    
18.    355                  {
    
19.    356                          ni=n->pointers[FindValuePtIndex(value,n)];
    
20.    357                          n=nodes+ni;
    
21.    358                          path[0]=path[0]+1;
    
22.    359                          path[path[0]]=ni;
    
23.    360                  }
    
24.    361                  return ni;
    
25.    362          }
    
26.    363  }
    
27.    364
    
28.    365  int FindValuePtIndex(int value,node* n)
    
29.    366  {
    
30.    367  int count;
    
31.    368  int i;
    
32.    369          count=n->valuecount;
    
33.    370
    
34.    371          for(i=0;i<count;i++)
    
35.    372          {
    
36.    373                  if(value < n->values[i])
    
37.    374                          return i;
    
38.    375          }
    
39.    376          return count;
    
40.    377  }
    
41.    378
    
42.    379
    
43.    380  int GetFreeNode()
    
44.    381  {
    
45.    382  node* n;
    
46.    383  int i;
    
47.    384          n=nodes+freenode;
    
48.    385          i=freenode;
    
49.    386          freenode=n->pointers[NODESIZE];
    
50.    387          return i;
    
51.    388  }
    
52.    389
    
53.    390  void InsertPtToInnerNode(int index,int value,int pointer, int path[])
    
54.    391  {
    
55.    392  node* n;
    
56.    393  node* newnode;
    
57.    394  node* parentnode;
    
58.    395  int tmpvalues[NODESIZE+1];
    
59.    396  int tmppointers[NODESIZE+1+1];
    
60.    397  int halfsize;
    
61.    398  int i,j,insertpos,ni,pi; // ni-new node index, pi-parent node index
    
62.    399  int pathindex;
    
63.    400  int valueinsert; //the value insert to parent node
    
64.    401
    
65.    402          n=nodes+index;
    
66.    403          insertpos=-1;
    
67.    404          halfsize=(NODESIZE+1)/2;
    
68.    405          if(n->valuecount==NODESIZE) // the node is full, need to split
    
69.    406          {
    
70.    407                  ni=GetFreeNode();
    
71.    408                  newnode=nodes+ni;
    
72.    409                  newnode->type=inner;
    
73.    410                  for(i=0;i<NODESIZE;i++)
    
74.    411                  {
    
75.    412                          if(value<n->values[i])
    
76.    413                          {
    
77.    414                                  insertpos=i;
    
78.    415                                  break;
    
79.    416                          }
    
80.    417                  }
    
81.    418                  if(insertpos==-1)
    
82.    419                          insertpos=NODESIZE;
    
83.    420
    
84.    421                  tmppointers[0]=n->pointers[0];
    
85.    422                  for(i=0;i<insertpos;i++)
    
86.    423                  {
    
87.    424                          tmpvalues[i]=n->values[i];
    
88.    425                          tmppointers[i+1]=n->pointers[i+1];
    
89.    426                  }
    
90.    427                  tmpvalues[insertpos]=value;
    
91.    428                  tmppointers[insertpos+1]=pointer;
    
92.    429                  for(i=insertpos;i<NODESIZE;i++)
    
93.    430                  {
    
94.    431                          tmpvalues[i+1]=n->values[i];
    
95.    432                          tmppointers[i+1+1]=n->pointers[i+1];
    
96.    433                  }
    
97.    434
    
98.    435                  n->valuecount=halfsize;
    
99.    436                  for(i=0;i<halfsize;i++)
    
100.    437                  {
     
101.    438                          n->values[i]=tmpvalues[i];
     
102.    439                          n->pointers[i+1]=tmppointers[i+1];
     
103.    440                  }
     
104.    441
     
105.    442                  for(i=halfsize;i<NODESIZE+1;i++)
     
106.    443                  {
     
107.    444                          newnode->values[i-halfsize]=tmpvalues[i];
     
108.    445                          newnode->pointers[i-halfsize]=tmppointers[i+1];
     
109.    446                  }
     
110.    447                  newnode->valuecount=NODESIZE+1-halfsize; //中间的那个值插入到上级节点
     
111.    448                  valueinsert=newnode->values[0];
     
112.    449                  for(i=1;i<newnode->valuecount;i++)
     
113.    450                  {
     
114.    451                          newnode->values[i-1]=newnode->values[i];
     
115.    452                  }
     
116.    453                  newnode->valuecount=newnode->valuecount-1;
     
117.    454
     
118.    455                  for(i=1 ;i<=path[0];i++)
     
119.    456                  {
     
120.    457                          if(index==path[i])
     
121.    458                                  pathindex=i;
     
122.    459                  }
     
123.    460                  if(pathindex==1) // if this inner node is root node
     
124.    461                  {
     
125.    462                          pi=GetFreeNode();
     
126.    463                          rootnode=pi;
     
127.    464                          parentnode=nodes+pi;
     
128.    465                          parentnode->type=inner;
     
129.    466                          parentnode->valuecount=1;
     
130.    467                          parentnode->values[0]=valueinsert;
     
131.    468                          parentnode->pointers[0]=index;
     
132.    469                          parentnode->pointers[1]=ni;
     
133.    470                  }
     
134.    471                  else
     
135.    472                          InsertPtToInnerNode(path[pathindex-1],valueinsert,ni,path);
     
136.    473          }
     
137.    474          else // if the node doesn't need to split
     
138.    475          {
     
139.    476                  for(i=0;i< n->valuecount;i++)
     
140.    477                  {
     
141.    478                          if (value < n->values[i])
     
142.    479                          {
     
143.    480                                  insertpos=i;
     
144.    481                                  break;
     
145.    482                          }
     
146.    483                  }
     
147.    484                  if(insertpos==-1)
     
148.    485                          insertpos=n->valuecount;
     
149.    486
     
150.    487                  for(i=n->valuecount;i > insertpos;i--)
     
151.    488                  {
     
152.    489                          n->values[i]=n->values[i-1];
     
153.    490                          n->pointers[i+1]=n->pointers[i];
     
154.    491                  }
     
155.    492                  n->values[insertpos]=value;
     
156.    493                  n->pointers[insertpos+1]=pointer;
     
157.    494                  n->valuecount=n->valuecount+1;
     
158.    495          }
     
159.    496  }
     
160.    497
     
161.    498  void PrintBtree()
     
162.    499  {
     
163.    500          LoadBtree();
     
164.    501          printf("BTree: Root:%d \n\n",rootnode);
     
165.    502          if(rootnode!=-1)
     
166.    503                  PrintNode(rootnode);
     
167.    504  }
     
168.    505
     
169. 
     

复制代码

Serenaiad

1. 
   
2.    506  void PrintNode(int index)
   
3.    507  {
   
4.    508  node* n;
   
5.    509  int i;
   
6.    510          n=nodes+index;
   
7.    511          if(n->type==inner)
   
8.    512                  printf("NodeIndex:%d ValueCount:%d, type:InnerNode\n",index,n->valuecount);
   
9.    513          else
   
10.    514                  printf("NodeIndex:%d ValueCount:%d, type:LeafNode\n",index,n->valuecount);
    
11.    515          if (n->type==leaf)
    
12.    516                  printf("Values:   ");
    
13.    517          else
    
14.    518                  printf("Values:      ");
    
15.    519          for(i=0;i< n->valuecount;i++)
    
16.    520                  printf("  %4d  ",n->values[i]);
    
17.    521          printf("\n");
    
18.    522          printf("Pointers: ");
    
19.    523          if(n->type==inner)
    
20.    524          {
    
21.    525                  for(i=0;i< n->valuecount+1;i++)
    
22.    526                          printf("  %4d  ",n->pointers[i]);
    
23.    527          }
    
24.    528          else
    
25.    529          {
    
26.    530                  for(i=0;i< n->valuecount;i++)
    
27.    531                          printf("  %4d  ",n->pointers[i]);
    
28.    532                  printf("next:%d",n->pointers[NODESIZE]);
    
29.    533          }
    
30.    534
    
31.    535          printf("\n\n");
    
32.    536          if( n->type == inner)
    
33.    537          {
    
34.    538                  for(i=0;i< n->valuecount+1 ;i++)
    
35.    539                          PrintNode(n->pointers[i]);
    
36.    540          }
    
37.    541  }
    
38.    542
    
39.    543  void test()
    
40.    544  {
    
41.    545  int i,j;
    
42.    546  int ni;
    
43.    547  int minval;
    
44.    548  node* n;
    
45.    549  int values[100];
    
46.    550  valuelocation v;
    
47.    551  int valuecount;
    
48.    552  int index;
    
49.    553  int val;
    
50.    554          printf("RAND_MAX:%d\n",RAND_MAX);
    
51.    555
    
52.    556          LoadBtree();
    
53.    557          srand(atoi(GetSysTime()));
    
54.    558          //random();
    
55.    559          for(i=0;i<100;i++)
    
56.    560          {
    
57.    561
    
58.    562                  while(1)
    
59.    563                  {
    
60.    564
    
61.    565                          val=rand();
    
62.    566                          v=FindValue(val);
    
63.    567                          if(v.nodeindex==-1)
    
64.    568                          {
    
65.    569                                  InsertValue(val,val);
    
66.    570                                  break;
    
67.    571                          }
    
68.    572                  }
    
69.    573          }
    
70.    574          if(VerifyBtree()!=0)
    
71.    575                  return ;
    
72.    576          WriteBtree();
    
73.    577
    
74.    578
    
75.    579          minval=MinValueThroughNode(rootnode);
    
76.    580          v=FindValue(minval);
    
77.    581          ni=v.nodeindex;
    
78.    582          n=nodes+ni;
    
79.    583          i=0;
    
80.    584          printf("values: \n");
    
81.    585          while(n!=NULL)
    
82.    586          {
    
83.    587                  for(j=0;j<n->valuecount;j++)
    
84.    588                  {
    
85.    589                          values[i]=n->values[j];
    
86.    590                          printf("value %d is %d\n",i,values[i]);
    
87.    591                          i++;
    
88.    592                  }
    
89.    593
    
90.    594                  if(n->pointers[NODESIZE]==-1)
    
91.    595                          n=NULL;
    
92.    596                  else
    
93.    597                          n=nodes+n->pointers[NODESIZE];
    
94.    598          }
    
95.    599          printf("\n");
    
96.    600          //begin to delete
    
97.    601          valuecount=100;
    
98.    602          while(valuecount>10)
    
99.    603          {
    
100.    604                  i=random();
     
101.    605                  i=rand();
     
102.    606                  index=i/(RAND_MAX/valuecount);
     
103.    607                  if(index>valuecount-1)
     
104.    608                          continue;
     
105.    609                  v=FindValue(values[index]);
     
106.    610                  if(v.nodeindex==-1)
     
107.    611                  {
     
108.    612                          printf("value %d not in btree.\n",values[index]);
     
109.    613                          return ;
     
110.    614                  }
     
111.    615                  printf("Delete %d value:%d\n",index,values[index]);
     
112.    616                  if(DeleteValue(values[index])!=0)
     
113.    617                  {
     
114.    618                          printf("delete value failed\n");
     
115.    619                          return ;
     
116.    620                  }/*
     
117.    621                  v=FindValue(32085);
     
118.    622                  if(v.nodeindex==-1)
     
119.    623                  {
     
120.    624                          printf("value %d not in btree.\n",32085);
     
121.    625                          return ;
     
122.    626                  }*/
     
123.    627
     
124.    628                  for(i=index;i<valuecount-1;i++)
     
125.    629                          values[i]=values[i+1];
     
126.    630                  if(VerifyBtree()!=0)
     
127.    631                          return;
     
128.    632                  WriteBtree();
     
129.    633                  valuecount--;
     
130.    634
     
131.    635          }
     
132.    636          WriteBtree();
     
133.    637  }
     
134.    638
     
135.    639  valuelocation FindValue(int value)
     
136.    640  {
     
137.    641  int i,vi;
     
138.    642  node* n;
     
139.    643  int path[101];
     
140.    644  valuelocation v;
     
141.    645          v.nodeindex=-1;
     
142.    646          vi=FindNewValueNode(value,path);
     
143.    647          if(vi==-1)
     
144.    648          {
     
145.    649                  return v;
     
146.    650          }
     
147.    651          else
     
148.    652          {
     
149.    653                  n=nodes+vi;
     
150.    654                  for(i=0;i<n->valuecount;i++)
     
151.    655                  {
     
152.    656                          if(n->values[i]==value)
     
153.    657                          {
     
154.    658                                  v.nodeindex=vi;
     
155.    659                                  v.valueindex=i;
     
156.    660                                  v.pointer=n->pointers[i];
     
157.    661                                  return v;
     
158.    662                          }
     
159.    663                  }
     
160.    664                  return v;
     
161.    665          }
     
162.    666  }
     
163.    667
     
164.    668  int DeleteValue(int value)
     
165.    669  {
     
166.    670  int i,j,ni,pi,bi; //ni - node index;  pi - parent node index ; bi - borther node index
     
167.    671  int vi ; // vi - value index int he pointers array
     
168.    672  int halfsize=(NODESIZE+1)/2;
     
169.    673  int minval,pminval,nminval;
     
170.    674  int newval;
     
171.    675  int valuepos;
     
172.    676
     
173.    677  node* n;
     
174.    678  node* pn; // parent node
     
175.    679  node* prenode=NULL; // previous brother node
     
176.    680  node* nextnode=NULL; //next brother node
     
177.    681
     
178.    682  // 本节点和前一个兄弟节点还是和后一个兄弟节点发生关系（借值或合并) P ,N
     
179.    683  char  NodeProc; // P - previous node N- next node
     
180.    684  char  MethodProc; // M-merge B-borrow
     
181.    685  int path[101];
     
182.    686  valuelocation v;
     
183.    687
     
184.    688          ni=FindNewValueNode(value,path);
     
185.    689          if( ni==-1)
     
186.    690          {
     
187.    691                  return 1;
     
188.    692          }
     
189.    693          else
     
190.    694          {
     
191.    695                  n=nodes+ni;
     
192.    696                  valuepos=-1;
     
193.    697                  for(i=0;i<n->valuecount;i++)
     
194.    698                  {
     
195.    699                          if(value==n->values[i])
     
196.    700                          {
     
197.    701                                  valuepos=i;
     
198.    702                                  break;
     
199.    703                          }
     
200.    704                  }
     
201.    705                  if(valuepos==-1)
     
202.    706                          return 1;
     
203.    707                  if(n->valuecount > halfsize) // the node have enough value
     
204.    708                  {
     
205.    709                          if(value==n->values[0]) // 如果删掉的这个值是这个节点的最小值,那么需要update 他的某个父节点的值
     
206.    710                          {
     
207.    711                                  minval=n->values[0];
     
208.    712                                  newval=n->values[1];
     
209.    713                                  if(path[0]!=1) // if this node is not root node
     
210.    714                                          UpdateAncestorNodeMinValue(path,path[0]-1,minval,newval);
     
211.    715                          }
     
212.    716                          DeleteValueInLeafNode(n,value);
     
213.    717                          return 0;
     
214.    718                  }
     
215.    719                  else// if the node doesn't have enough values;
     
216.    720                  {
     
217.    721                          vi=FindNodeValueIndex(value,n);
     
218.    722                          if(path[0]==1) // this leaf node is root node
     
219.    723                          {
     
220.    724                                  DeleteValueInLeafNode(n,value);
     
221.    725                                  if(n->valuecount==0)
     
222.    726                                  {
     
223.    727                                          ReleaseNode(ni);
     
224.    728                                          rootnode=-1;
     
225.    729                                  }
     
226.    730                                  return 0;
     
227.    731                          }
     
228.    732                          else  // if the node is not root node
     
229.    733                          {
     
230.    734
     
231.    735                                  pi=path[path[0]-1];
     
232.    736                                  pn=nodes+pi; // get parent node
     
233.    737                                  for(i=0 ;i<NODESIZE+1;i++)
     
234.    738                                  {
     
235.    739                                          if(pn->pointers[i]==ni)
     
236.    740                                          {
     
237.    741                                                  if(i!=0)
     
238.    742                                                  {
     
239.    743                                                          bi=pn->pointers[i-1];
     
240.    744                                                          prenode=nodes+pn->pointers[i-1];
     
241.    745                                                  }
     
242.    746                                                  if(i!=NODESIZE)
     
243.    747                                                  {
     
244.    748                                                          bi=pn->pointers[i+1];
     
245.    749                                                          nextnode=nodes+pn->pointers[i+1];
     
246.    750                                                  }
     
247.    751                                                  break;
     
248.    752                                          }
     
249.    753                                  }
     
250.    754                                  if(prenode!=NULL)
     
251.    755                                  {
     
252.    756                                          NodeProc='P';
     
253.    757                                          if(prenode->valuecount > halfsize)
     
254.    758                                                  MethodProc='B';
     
255.    759                                          else
     
256.    760                                                  MethodProc='M';
     
257.    761                                  }
     
258.    762                                  else
     
259.    763                                  {
     
260.    764                                          NodeProc='N';
     
261.    765                                          if(nextnode->valuecount > halfsize)
     
262.    766                                                  MethodProc='B';
     
263.    767                                          else
     
264.    768                                                  MethodProc='M';
     
265.    769                                  }
     
266.    770                                  //printf("NodeProc: %c ,MethodProc:%c\n",NodeProc,MethodProc);
     
267.    771                                  if(MethodProc=='B') //如果需要借值
     
268.    772                                  {
     
269.    773                                          if(NodeProc=='P') //如果从前一个节点借
     
270.    774                                          {
     
271.    775                                                  if(value==n->values[0])
     
272.    776                                                  {
     
273.    777                                                          minval=value;
     
274.    778                                                          newval=n->values[1];
     
275.    779                                                          UpdateAncestorNodeMinValue(path,path[0]-1,minval,newval);
     
276.    780                                                  }
     
277.    781                                                  DeleteValueInLeafNode(n,value);
     
278.    782
     
279.    783                                                  for(i=n->valuecount ; i>=1 ;i--)
     
280.    784                                                  {
     
281.    785                                                          n->values[i]=n->values[i-1];
     
282.    786                                                          n->pointers[i]=n->pointers[i-1];
     
283.    787                                                  }
     
284.    788                                                  minval=n->values[0];
     
285.    789                                                  newval=prenode->values[prenode->valuecount-1];
     
286.    790                                                  n->values[0]=prenode->values[prenode->valuecount-1];
     
287.    791                                                  n->pointers[0]=prenode->pointers[prenode->valuecount-1];
     
288.    792                                                  n->valuecount=n->valuecount+1;
     
289.    793                                                  UpdateAncestorNodeMinValue(path,path[0]-1,minval,newval);
     
290.    794                                                  prenode->valuecount=prenode->valuecount-1;
     
291.    795                                          }
     
292.    796                                          else  //如果需要从后一个节点借
     
293.    797                                          {
     
294.    798                                                  if(value==n->values[0]) //如果这个删除的最小值
     
295.    799                                                  {
     
296.    800                                                          newval=n->values[1];
     
297.    801                                                          UpdateAncestorNodeMinValue(path,path[0]-1,value,newval);
     
298.    802                                                  }
     
299.    803                                                  DeleteValueInLeafNode(n,value);
     
300.    804
     
301.    805                                                  //处理下一个节点
     
302.    806                                                  minval=nextnode->values[0];
     
303.    807                                                  newval=nextnode->values[1];
     
304.    808                                                  n->values[n->valuecount]=nextnode->values[0];
     
305.    809                                                  n->pointers[n->valuecount]=nextnode->pointers[0];
     
306.    810                                                  n->valuecount=n->valuecount+1;
     
307.    811                                                  DeleteValueInLeafNode(nextnode,minval);
     
308.    812                                                  UpdateAncestorNodeMinValue(path,path[0]-1,minval,newval);// 下一个节点的最小值也改变了，所以需要也update 父节点
     
309.    813                                          }
     
310.    814                                          return 0;
     
311.    815                                  }
     
312.    816                                  else //如果合并节点
     
313.    817                                  {
     
314.    818                                          if(NodeProc=='P') // 如果和前一个节点合并
     
315.    819                                          {
     
316.    820                                                  if(value==n->values[0])
     
317.    821                                                  {
     
318.    822                                                          newval=n->values[1];
     
319.    823                                                          UpdateAncestorNodeMinValue(path,path[0]-1,value,newval);
     
320.    824                                                  }
     
321.    825                                                  DeleteValueInLeafNode(n,value);
     
322.    826                                                  minval=n->values[0];
     
323.    827                                                  for(i=0;i<n->valuecount;i++)
     
324.    828                                                  {
     
325.    829                                                          prenode->values[halfsize+i]=n->values[i];
     
326.    830                                                          prenode->pointers[halfsize+i]=n->pointers[i];
     
327.    831                                                  }
     
328.    832                                                  prenode->pointers[NODESIZE]=n->pointers[NODESIZE];
     
329.    833                                                  prenode->valuecount=halfsize*2-1;
     
330.    834                                                  DeletePtInnerNode(pi,minval,ni,path);
     
331.    835                                                  ReleaseNode(ni);
     
332.    836                                          }
     
333.    837                                          else //如果和后一个节点合并
     
334.    838                                          {
     
335.    839                                                  if(value==n->values[0])
     
336.    840                                                  {
     
337.    841                                                          minval=n->values[1];
     
338.    842                                                          UpdateAncestorNodeMinValue(path,path[0]-1,value,minval);
     
339.    843                                                  }
     
340.    844                                                  DeleteValueInLeafNode(n,value);
     
341.    845                                                  n->pointers[NODESIZE]=nextnode->pointers[NODESIZE];
     
342.    846                                                  n->valuecount=halfsize*2 -1;
     
343.    847
     
344.    848                                                  minval=nextnode->values[0];
     
345.    849                                                  for(i=0;i<halfsize;i++)
     
346.    850                                                  {
     
347.    851                                                          n->values[halfsize-1+i]=nextnode->values[i];
     
348.    852                                                          n->pointers[halfsize-1+i]=nextnode->pointers[i];
     
349.    853                                                  }
     
350.    854                                                  DeletePtInnerNode(pi,minval,bi,path);
     
351.    855                                                  ReleaseNode(bi);
     
352.    856                                          }
     
353.    857                                  }
     
354.    858                                  return 0;
     
355.    859                          }
     
356.    860                  }
     
357.    861          }
     
358.    862  }
     
359. 
     

复制代码

Serenaiad

1. 
   
2.    863
   
3.    864  /* 从一个中间节点中删除指针 */
   
4.    865  void DeletePtInnerNode(int index,int minvalue,int pointer,int path[])
   
5.    866  {
   
6.    867  int i,pi;
   
7.    868  int preindex,nextindex,parentindex;
   
8.    869  node* pn;
   
9.    870  node* prenode=NULL;
   
10.    871  node* nextnode=NULL;
    
11.    872  char NodeProc,MethodProc;
    
12.    873  int ptpos;
    
13.    874  int newval;
    
14.    875  node* n;
    
15.    876  int minval;
    
16.    877  int halfsize=(NODESIZE+1)/2;
    
17.    878  int val;
    
18.    879
    
19.    880          parentindex=-1;
    
20.    881          nextindex=-1;
    
21.    882          preindex=-1;
    
22.    883          n=nodes+index;
    
23.    884          if(index==path[1]) //如果这个中间节点是根节点
    
24.    885          {
    
25.    886                  if(n->valuecount==1)
    
26.    887                  {
    
27.    888                          ReleaseNode(index);
    
28.    889                          if(pointer==n->pointers[1])
    
29.    890                                  rootnode=n->pointers[0];
    
30.    891                          else
    
31.    892                                  rootnode=n->pointers[1];
    
32.    893                  }
    
33.    894                  else
    
34.    895                  {
    
35.    896                          DeletePointerInInnerNode(n,-1,path,pointer,minvalue);
    
36.    897                  }
    
37.    898          }
    
38.    899          else //如果是中间节点
    
39.    900          {
    
40.    901                  parentindex=path[GetPosInAccessPath(index,path)-1];
    
41.    902                  if(n->valuecount+1>halfsize) //如果这个节点有足够的指针
    
42.    903                  {
    
43.    904                          DeletePointerInInnerNode(n,parentindex,path,pointer,minvalue);
    
44.    905                  }
    
45.    906                  else //如果这个节点的指针不够,需要 借 或 合并
    
46.    907                  {
    
47.    908
    
48.    909                          pn=nodes+parentindex;
    
49.    910                          for(i=0;i<pn->valuecount+1;i++)
    
50.    911                          {
    
51.    912                                  if(pn->pointers[i]==index)
    
52.    913                                  {
    
53.    914                                          ptpos=i;
    
54.    915                                          break;
    
55.    916                                  }
    
56.    917                          }
    
57.    918                          if(ptpos==0)
    
58.    919                          {
    
59.    920                                  NodeProc='N';
    
60.    921                                  nextindex=pn->pointers[1];
    
61.    922                                  nextnode=nodes+nextindex;
    
62.    923                          }
    
63.    924                          else
    
64.    925                          {
    
65.    926                                  NodeProc='P';
    
66.    927                                  preindex=pn->pointers[ptpos-1];
    
67.    928                                  prenode=nodes+preindex;
    
68.    929                          }
    
69.    930                          if(NodeProc=='P')  // previous brother node
    
70.    931                          {
    
71.    932                                  if(prenode->valuecount > (halfsize-1)) // 借指针
    
72.    933                                  {
    
73.    934                                          DeletePointerInInnerNode(n,parentindex,path,pointer,minvalue);
    
74.    935                                          minval=MinValueThroughNode(n->pointers[0]);
    
75.    936                                          for(i=n->valuecount-1;i>=0 ;i--)
    
76.    937                                          {
    
77.    938                                                  n->values[i+1]=n->values[i];
    
78.    939                                                  n->pointers[i+1+1]=n->pointers[i+1];
    
79.    940                                          }
    
80.    941                                          n->pointers[1]=n->pointers[0];
    
81.    942
    
82.    943                                          n->values[0]=minval;
    
83.    944                                          newval=prenode->values[prenode->valuecount-1];
    
84.    945                                          n->pointers[0]=prenode->pointers[prenode->valuecount];
    
85.    946                                          prenode->valuecount=prenode->valuecount-1;
    
86.    947                                          n->valuecount=n->valuecount+1;
    
87.    948                                          UpdateAncestorNodeMinValue(path,GetPosInAccessPath(index,path)-1,minval,newval);
    
88.    949                                  }
    
89.    950                                  else// 合并
    
90.    951                                  {
    
91.    952                                          DeletePointerInInnerNode(n,parentindex,path,pointer,minvalue);
    
92.    953                                          minval=MinValueThroughNode(n->pointers[0]);
    
93.    954                                          DeletePtInnerNode(parentindex,minval,index,path);
    
94.    955                                          for(i=0;i<=n->valuecount;i++)
    
95.    956                                          {
    
96.    957                                                  if(i==0)
    
97.    958                                                          val=minval;
    
98.    959                                                  else
    
99.    960                                                          val=n->values[i-1];
    
100.    961
     
101.    962                                                  prenode->values[prenode->valuecount + i]=val;
     
102.    963                                                  prenode->pointers[prenode->valuecount+i+1]=n->pointers[i];
     
103.    964                                          }
     
104.    965                                          prenode->valuecount=prenode->valuecount+n->valuecount+1;
     
105.    966                                          ReleaseNode(index);
     
106.    967                                  }
     
107.    968                          }
     
108.    969                          else // next brother node
     
109.    970                          {
     
110.    971                                  if(nextnode->valuecount > (halfsize-1)) // 借节点
     
111.    972                                  {
     
112.    973                                          DeletePointerInInnerNode(n,parentindex,path,pointer,minvalue);
     
113.    974                                          minval=MinValueThroughNode(nextnode->pointers[0]);
     
114.    975                                          n->values[n->valuecount]=minval;
     
115.    976                                          n->pointers[n->valuecount+1]=nextnode->pointers[0];
     
116.    977                                          n->valuecount=n->valuecount+1;
     
117.    978                                          DeletePointerInInnerNode(nextnode,parentindex,path,nextnode->pointers[0],minval);
     
118.    979                                  }
     
119.    980                                  else // 合并节点
     
120.    981                                  {
     
121.    982                                          DeletePointerInInnerNode(n,parentindex,path,pointer,minvalue);
     
122.    983                                          minval=MinValueThroughNode(nextnode->pointers[0]);
     
123.    984                                          for(i=0;i<=nextnode->valuecount;i++)
     
124.    985                                          {
     
125.    986                                                  if(i==0)
     
126.    987                                                          val=minval;
     
127.    988                                                  else
     
128.    989                                                          val=nextnode->values[i-1];
     
129.    990                                                  n->values[n->valuecount+i]=val;
     
130.    991                                                  n->pointers[n->valuecount+i+1]=nextnode->pointers[i];
     
131.    992                                          }
     
132.    993                                          n->valuecount=n->valuecount+nextnode->valuecount+1;
     
133.    994                                          DeletePtInnerNode(parentindex,minval,nextindex,path);
     
134.    995                                          ReleaseNode(nextindex);
     
135.    996                                  }
     
136.    997                          }
     
137.    998                  }
     
138.    999          }
     
139.   1000  }
     
140.   1001
     
141.   1002  int FindNodeValueIndex(int value, node* n)
     
142.   1003  {
     
143.   1004  int i;
     
144.   1005          for(i=0;i<n->valuecount;i++)
     
145.   1006          {
     
146.   1007                  if(n->values[i]==value)
     
147.   1008                          return i;
     
148.   1009          }
     
149.   1010          return -1;
     
150.   1011  }
     
151.   1012
     
152.   1013  int ReleaseNode(int index)
     
153.   1014  {
     
154.   1015  node* n;
     
155.   1016          n=nodes+index;
     
156.   1017          n->pointers[NODESIZE]=freenode;
     
157.   1018          freenode=index;
     
158.   1019  }
     
159.   1020
     
160.   1021  void DeleteValueInLeafNode(node* n,int value)
     
161.   1022  {
     
162.   1023  int i;
     
163.   1024  int vi;
     
164.   1025
     
165.   1026          for(i=0 ;i< n->valuecount;i++)
     
166.   1027          {
     
167.   1028                  if(n->values[i]==value)
     
168.   1029                  {
     
169.   1030                          vi=i;
     
170.   1031                          break;
     
171.   1032                  }
     
172.   1033          }
     
173.   1034          for(i=vi;i<n->valuecount-1;i++)
     
174.   1035          {
     
175.   1036                  n->values[i]=n->values[i+1];
     
176.   1037                  n->pointers[i]=n->pointers[i+1];
     
177.   1038          }
     
178.   1039          n->valuecount=n->valuecount-1;
     
179.   1040  }
     
180.   1041
     
181.   1042
     
182.   1043  void UpdateAncestorNodeMinValue(int path[],int posstart,int val,int newval)
     
183.   1044  {
     
184.   1045  int i,j;
     
185.   1046  node* n;
     
186.   1047          for(i=posstart;i>=1;i--)
     
187.   1048          {
     
188.   1049                  n=nodes+path[i];
     
189.   1050                  for(j=0;j<n->valuecount;j++)
     
190.   1051                  {
     
191.   1052                          if(n->values[j]==val)
     
192.   1053                          {
     
193.   1054                                  n->values[j]=newval;
     
194.   1055                                  return;
     
195.   1056                          }
     
196.   1057                  }
     
197.   1058          }
     
198.   1059  }
     
199.   1060
     
200.   1061  int MinValueThroughNode(int index)
     
201.   1062  {
     
202.   1063  node* n;
     
203.   1064  int mi;
     
204.   1065          n=nodes+index;
     
205.   1066          if(n->type==inner)
     
206.   1067                  mi=MinValueThroughNode(n->pointers[0]);
     
207.   1068          else
     
208.   1069                  mi=n->values[0];
     
209.   1070          return mi;
     
210.   1071  }
     
211.   1072
     
212.   1073  int GetPosInAccessPath(int index , int path[])
     
213.   1074  {
     
214.   1075  int i;
     
215.   1076          for(i=1 ;i<=path[0];i++)
     
216.   1077          {
     
217.   1078                  if(index==path[i])
     
218.   1079                          return i;
     
219.   1080          }
     
220.   1081          return -1;
     
221.   1082
     
222.   1083  }
     
223.   1084
     
224.   1085  void DeletePointerInInnerNode(node* n,int parentindex, int path[], int pointer,int minvalue)
     
225.   1086  {
     
226.   1087  int i;
     
227.   1088  int pos;
     
228.   1089  int newval;
     
229.   1090          pos=-1;
     
230.   1091          for(i=0;i< n->valuecount+1;i++)
     
231.   1092          {
     
232.   1093                  if(n->pointers[i]==pointer)
     
233.   1094                  {
     
234.   1095                          pos=i;
     
235.   1096                          break;
     
236.   1097                  }
     
237.   1098          }
     
238.   1099          if(pos==-1)
     
239.   1100                  return;
     
240.   1101
     
241.   1102          if(pos==0)
     
242.   1103          {
     
243.   1104                  newval=n->values[0];
     
244.   1105                  if(parentindex!=-1) // 如果不是根节点
     
245.   1106                  {
     
246.   1107                          //printf("update ancestor,index:%d parent level: %d  minval:%d newval:%d\n",index,GetPosInAccessPath(index,path)-1,minvalue,newval);
     
247.   1108                          UpdateAncestorNodeMinValue(path,GetPosInAccessPath(parentindex,path),minvalue,newval);
     
248.   1109                  }
     
249.   1110                  for(i=0;i<n->valuecount-1;i++)
     
250.   1111                  {
     
251.   1112                          n->values[i]=n->values[i+1];
     
252.   1113                          n->pointers[i]=n->pointers[i+1];
     
253.   1114                  }
     
254.   1115                  n->pointers[n->valuecount-1]=n->pointers[n->valuecount];
     
255.   1116                  n->valuecount=n->valuecount-1;
     
256.   1117          }
     
257.   1118          else
     
258.   1119          {
     
259.   1120                  for(i=pos-1;i<n->valuecount-1;i++)
     
260.   1121                  {
     
261.   1122                          n->values[i]=n->values[i+1];
     
262.   1123                          n->pointers[i+1]=n->pointers[i+1+1];
     
263.   1124                  }
     
264.   1125                  n->valuecount=n->valuecount-1;
     
265.   1126          }
     
266.   1127  }
     
267.   1128
     
268.   1129  int VerifyNode(int index)
     
269.   1130  {
     
270.   1131  int i;
     
271.   1132  node* n;
     
272.   1133  int minval;
     
273.   1134          n=nodes+index;
     
274.   1135          if(n->type==leaf)
     
275.   1136          {
     
276.   1137                  for(i=0;i<n->valuecount-1;i++)
     
277.   1138                  {
     
278.   1139                          if(n->values[i]>= n->values[i+1])
     
279.   1140                          {
     
280.   1141                                  printf("Leaf node %d verify failed.\n",index);
     
281.   1142                                  return 1;
     
282.   1143                          }
     
283.   1144                  }
     
284.   1145                  return 0;
     
285.   1146          }
     
286.   1147          for(i=0;i<n->valuecount;i++)
     
287.   1148          {
     
288.   1149                  minval=n->values[i];
     
289.   1150                  if(minval!=MinValueThroughNode(n->pointers[i+1]))
     
290.   1151                  {
     
291.   1152                          printf("node %d ,pointer %d verify failed.\n",index,n->pointers[i+1]);
     
292.   1153                          return 1;
     
293.   1154                  }
     
294.   1155          }
     
295.   1156          for(i=0;i<=n->valuecount;i++)
     
296.   1157          {
     
297.   1158                  if(VerifyNode(n->pointers[i])!=0)
     
298.   1159                          return 1;
     
299.   1160          }
     
300.   1161          return 0;
     
301.   1162  }
     
302.   1163
     
303.   1164  int VerifyBtree()
     
304.   1165  {
     
305.   1166  int i,ni,minval;
     
306.   1167  node* n;
     
307.   1168  int path[101];
     
308.   1169  int lastvalue;
     
309.   1170  int firstvaluefetched;
     
310.   1171
     
311.   1172          if(rootnode==-1)
     
312.   1173          {
     
313.   1174                  printf("no value in this btree.\n");
     
314.   1175                  return 0;
     
315.   1176          }
     
316.   1177          if(VerifyNode(rootnode)!=0)
     
317.   1178          {
     
318.   1179                  printf("Verify Btree failed.\n");
     
319.   1180                  return 1;
     
320.   1181          }
     
321.   1182
     
322.   1183          minval=MinValueThroughNode(rootnode);
     
323.   1184          ni=FindNewValueNode(minval,path);
     
324.   1185          n=nodes+ni;
     
325.   1186          firstvaluefetched=0;
     
326.   1187          while(n!=NULL)
     
327.   1188          {
     
328.   1189                  //printf("Verify Leaf Node %d in leaf node chain.\n",ni);
     
329.   1190                  for(i=0;i<n->valuecount-1;i++)
     
330.   1191                  {
     
331.   1192                          if(firstvaluefetched)
     
332.   1193                          {
     
333.   1194                                  if(n->values[i]<= lastvalue)
     
334.   1195                                  {
     
335.   1196                                          printf("Verify btree failed. value should keep growing. node %d\n",ni);
     
336.   1197                                          return 1;
     
337.   1198                                  }
     
338.   1199                                  else
     
339.   1200                                          lastvalue=n->values[i];
     
340.   1201                          }
     
341.   1202                          else
     
342.   1203                          {
     
343.   1204                                  lastvalue=n->values[i];
     
344.   1205                                  firstvaluefetched=1;
     
345.   1206                          }
     
346.   1207
     
347.   1208                          if(n->values[i]>= n->values[i+1])
     
348.   1209                          {
     
349.   1210                                  printf("Leaf node %d verify failed.\n",ni);
     
350.   1211                                  return 1;
     
351.   1212                          }
     
352.   1213                  }
     
353.   1214                  ni=n->pointers[NODESIZE];
     
354.   1215                  if(ni==-1)
     
355.   1216                          n=NULL;
     
356.   1217                  else
     
357.   1218                          n=nodes+ni;
     
358.   1219          }
     
359.   1220          printf("Verify Btree success!\n");
     
360.   1221          return 0;
     
361.   1222  }
     
362.   1223
     
363.   1224  char *GetSysTime()
     
364.   1225  {
     
365.   1226      time_t tm;
     
366.   1227      static char systime[7];
     
367.   1228      
     
368.   1229      tm = time(NULL);
     
369.   1230      strftime(systime, 7, "%H%M%S", localtime(&tm));
     
370.   1231      
     
371.   1232      return systime;
     
372.   1233  }
     
373. 
     

复制代码

cjaizss

顶一把，但是提醒一下，UNIX-like OS下最好不要像CreateBtree这样命名

rushrush

好奇怪的接口，这个可以实用吗？

langue

原帖由 cjaizss 于 2006-12-23 02:14 发表
顶一把，但是提醒一下，UNIX-like OS下最好不要像CreateBtree这样命名

的确，风格不同。

原帖由 Serenaiad 于 2006-12-23 01:58 发表
一直没有找到实现的代码，前段时间写了一个，数据库里的索引就是用的整个东西实现的

如果不嫌弃的话，看看 BSD 里的实现。

[ 本帖最后由 langue 于 2006-12-23 09:42 编辑 ]

hardboy_du

我一只用snort中附带的 二叉树 和 伸展二叉树
现在正努力把他扩充到 AVL树和 红黑树