B树删除和创建(C)

不得不说,这个我写了两天。第一天晚上想移植一篇博客的,后来经过四个小时发现是错了谁懂啊!今天早上又找了一篇,大错误我都改了,有一个潜在的小bug是自己调试跳出来的,谁懂啊!得找阅读量高的才行!

先把刚刚的小错误放一下

 也不知道博主怎么想的,同时i和keynum++,害,害我好找!!!

改后就好了

由于老师要求的数据规模太大,我小小的vs承受不起,我只能想法设法减少我开辟的空间,连数组都不要了(哭)

结构(这是我采取的数据结构)

 1 //关键字索引  0(不记录)  1    2    3    4(不记录具体数值)
 2 //孩子的索引         0        1    2    3    4
 3 
 4 //树结点信息
 5 typedef struct Treenode
 6 {
 7     int level;//树的阶数
 8     int keyNum;//关键字的个数
 9     int childNum;//孩子的个数
10     int* keys;//关键字数组
11     struct Treenode** children;//孩子数组
12     struct Treenode* parent;//父亲指针
13 };

对应的初始化代码

 1 //初始化结点
 2 Treenode* initNode(int level)
 3 {
 4     Treenode* node = (Treenode*)malloc(sizeof(Treenode));
 5     node->level = level;
 6     node->keyNum = 0;
 7     node->childNum = 0;
 8     node->keys = (int*)malloc(sizeof(int) * (level+1));//索引,从1开始记录
 9     node->children = (Treenode**)malloc(sizeof(Treenode*) * level);
10     node->parent = NULL;
11     for (int i = 0; i < level; i++)
12     {
13         node->keys[i] = 0;
14         node->children[i] = NULL;
15     }
16     node->keys[level] = 0;//并没有实际用途,只是为了方便返回孩子的索引
17     return node;
18 }

 

插入

其实我感觉插入很简单,总结下来就是,找到要插入的叶子!!!结点(也就是最下面),然后如果超出m-1那就取中间进行分裂就好!

调整的步骤在代码注释中也有

//判断该结点是否进行分裂。调整主要三个方面
//1.找出中间结点,把结点前面的键值给新的左孩子,后面的键值给新的右孩子
//2.将该节点的孩子分给新的左孩子和右孩子
//3.将中间结点插入该节点的父亲关键字数组中,并将新的左孩子和右孩子插入父亲节点的孩子数组

由最底层逐层向上调整(这可能也是为什么左右子树高度相等的原因吧)

 1 //在节点处寻找合适的插入索引
 2 int findSuiteIndex(Treenode* node, int data)
 3 {
 4     int index;
 5     //索引从1开始,因为0是没有用的边界
 6     for (index = 1; index <= node->keyNum; index++)
 7         if (data < node->keys[index])
 8             break;
 9     return index;
10 }
 1 //找到合适的叶子结点,先插入叶子(没有孩子的结点)结点再做调整
 2 Treenode* findSuiteLeafNode(Treenode* T, int data)
 3 {
 4     if (T->childNum == 0)
 5         return T;
 6     else
 7     {
 8         int index = findSuiteIndex(T, data);
 9         //找到对应的(索引+1),再去该子节点去搜索,见前面注释
10         return findSuiteLeafNode(T->children[index-1], data);
11     }
12 }
1 //插入结点函数
2 void insert(Treenode** T, int data)
3 {
4     Treenode* node = findSuiteLeafNode(*T,data);
5     //找到要插入的叶子结点
6     addData(node, data, T);//插入树
7 }

这些基本函数封装好了,剩下就是add的实现了

 1 //插入数据到B树
 2 void addData(Treenode* node, int data,Treenode**T)
 3 {
 4     //先找到索引,将data放入关键字数组
 5     int index = findSuiteIndex(node, data);
 6     //后面元素后移动,因为本来就预留了多余的空间
 7     for (int i = node->keyNum; i >= index; i--)
 8         node->keys[i + 1] = node->keys[i];
 9     node->keys[index] = data;
10     node->keyNum++;
11 
12     //判断该结点是否进行分裂。调整主要三个方面
13     //1.找出中间结点,把结点前面的给新的左孩子,后面的给新的右孩子
14     //2.将该节点的孩子分给新的左孩子和右孩子
15     //3.将中间结点插入该节点的父亲关键字数组中,并将新的左孩子和右孩子插入父亲节点的孩子数组
16     if (node->keyNum == node->level)
17     {
18         //取中间节点
19         int mid = node->level / 2 + node->level % 2;
20 
21         //生成新的左右孩子
22         Treenode* lchild = initNode(node->level);
23         Treenode* rchild = initNode(node->level);
24 
25         //将mid左边的赋给左孩子关键字数组
26         for (int i = 1; i < mid; i++)
27             addData(lchild, node->keys[i], T);
28       
29         //将mid右边的赋给右孩子关键字数组
30         for (int i = mid + 1; i <= node->keyNum; i++)
31             addData(rchild, node->keys[i], T);
32 
33         //把该结点下面对应的孩子赋给左孩子的孩子数组
34         for (int i = 0; i < mid; i++)
35         {
36             lchild->children[i] = node->children[i];
37             //如果该孩子结点不为空,需要改变孩子的某些信息
38             if (node->children[i] != NULL)
39             {
40                 node->children[i]->parent = lchild;
41                 lchild->childNum++;
42             }
43         }
44 
45         //把该结点下面对应的孩子赋给右孩子的孩子数组
46         int k = 0;//右孩子数组的索引值
47         for (int i = mid; i < node->childNum; i++)
48         {
49             rchild->children[k++] = node->children[i];
50             //如果该孩子结点不为空,需要改变孩子的某些信息
51             if (node->children[i] != NULL)
52             {
53                 node->children[i]->parent = rchild;
54                 rchild->childNum++;
55             }
56         }
57 
58         //将中间结点插入该节点的父亲关键字数组中,并将新的左孩子和右孩子插入父亲节点的孩子数组
59         //node是根节点的时候,分裂会改变根节点
60         if (node->parent == NULL)
61         {
62             //生成新的根结点
63             Treenode* newParent = initNode(node->level);
64             addData(newParent, node->keys[mid], T);
65             newParent->children[0] = lchild;
66             newParent->children[1] = rchild;
67             newParent->childNum = 2;
68             lchild->parent = newParent;
69             rchild->parent = newParent;
70             *T = newParent;
71         }
72         else
73         {
74             //找到mid结点应该插入的node父亲的关键字数组的索引
75             int indexparent = findSuiteIndex(node->parent, node->keys[mid]);
76             
77             lchild->parent = node->parent;
78             rchild->parent = node->parent;
79             //node原来所有的元素都比index要小,所以之间把左孩子插入index-1,右孩子应该在index的位置
80             node->parent->children[indexparent - 1] = lchild;
81             //插入新的右孩子前,如果index处有,需要整体后移
82             if (node->parent->children[indexparent] != NULL)
83             {
84                 for (int i = node->parent->childNum - 1; i >= indexparent; i--)
85                     node->parent->children[i + 1] = node->parent->children[i];
86             }
87             node->parent->children[indexparent] = rchild;
88             node->parent->childNum++;
89             //将mid插入父节点位置
90             addData(node->parent, node->keys[mid],T);
91         }
92     }
93 }

删除


删除其实分两种:1.非叶子结点:就选择它左孩子最大值或右孩子最小值进行替代,然后归结为删除叶子结点

                              2.叶子结点就比较复杂了:(1)左兄弟富有或者右兄弟富有(键值个数大于【m/2】-1),就旋转一下(比如:左兄弟富有,将parent该键值给该结点1号键值处,然后将左兄弟最大键值给parent就好了!!!别看它看起来是这样,实现不容易啊!特别别忘了左兄弟的最大的孩子也要给该结点成为他的第一个孩子!!!之前博主就是少了这个)

 (2)都很穷的时候,将parent处键值,左(右)兄弟(键值和孩子),自己合并成一个结点,在插入回parent结点处,别忘了对parent相关值进行改动哦!

和插入一样,需要从底层往跟进行调整,我采用栈比较好理解啦

      我的实现是,将跟到待删除的叶子!!!结点入栈,然后一个一个取出来(叶子----跟)进行判断是否需要调整就好了

 1 // 合并操作
 2 void merge(Treenode* P, int pos)
 3 {
 4     //          pos+1(P)
 5     // pos(LC)        pos+1(RC)
 6     Treenode* LC = P->children[pos];
 7     Treenode* RC = P->children[pos + 1];
 8 
 9     LC->keys[LC->keyNum + 1] = P->keys[pos + 1];
10     ++LC->keyNum;
11 
12     //将右兄弟移入LC
13     int m = LC->keyNum;
14     for (int i = 1; i <= RC->keyNum; ++i)
15     {
16         LC->keys[m + i] = RC->keys[i];
17         ++LC->keyNum;
18     }
19     int n = LC->childNum;
20     for (int i = 0; i < RC->childNum; ++i)
21     {
22         LC->children[ n+ i] = RC->children[i];
23         ++LC->childNum;
24     }
25 
26     for (int i = pos + 1; i < P->keyNum; ++i)
27     {
28         P->keys[i] = P->keys[i + 1];
29     }
30     for (int i = pos + 1; i < P->childNum-1; ++i)
31     {
32         P->children[i] = P->children[i + 1];
33     }
34     --P->keyNum;
35     --P->childNum;
36 }
  1 //删除键值
  2 bool deleteKey(int key, Treenode** Root)
  3 {
  4     //如果根节点为空或者没有键值时
  5     if (NULL == *Root || 0 == (*Root)->keyNum) return false;
  6 
  7     Treenode* T = *Root;//复制一份
  8 
  9     stack<Treenode*> NODE;//存储调整的那棵子树
 10 
 11     while (T) 
 12     {
 13         NODE.push(T);
 14         //找到第一个比他大的索引
 15         int i = findSuiteIndex(T, key);
 16         //         i-1(可能相等的点)     i(key比它小)
 17         //孩子  i-2            i-1                    i
 18 
 19         if (i-1 <= T->keyNum && T->keys[i-1] == key) 
 20         {// 删除键值在该节点中
 21             if (T->childNum==0) 
 22             {// 叶子节点,删除
 23                 for (int k=i-1; i <= T->keyNum - 1; ++i) 
 24                     T->keys[k] = T->keys[k + 1];
 25                 --T->keyNum;
 26                 break;
 27             }
 28             else 
 29             {// 非叶子节点,找后继/也可以找前驱(必存在)
 30                 Treenode* RC = T->children[i - 1];// 右孩子
 31                 //找右孩子最小值
 32                 while (RC->childNum!=0) RC = RC->children[0];
 33 
 34                 T->keys[i-1] = RC->keys[1];//替换
 35                 key = RC->keys[1];//改变待删除值
 36                 T = T->children[i - 1];
 37             }
 38         }
 39         else // 删除节点不在该节点中
 40             T = T->children[i-1];
 41     }
 42     // 删除后调整
 43     Treenode* P = NODE.top();
 44     NODE.pop();
 45 
 46     while (!NODE.empty()) 
 47     {
 48         T = P;
 49         P = NODE.top();//该节点根树
 50         NODE.pop();
 51 
 52         //比最小键值数小,做调整
 53         if (T->keyNum < 1) 
 54         {
 55             //找到该结点属于该根节点的第几个孩子
 56             int i = 0;
 57             for (; i <T->childNum; ++i) 
 58                 if (T == P->children[i]) break;
 59             
 60             //找该节点两边的兄弟结点
 61             Treenode* LB = i > 0 ? P->children[i - 1] : NULL;
 62             Treenode* RB = i < P->childNum-1 ? P->children[i + 1] : NULL;
 63 
 64             if (LB && LB->keyNum > 1) 
 65             {// 左兄弟存在且键值富余
 66              //        i(P)
 67              // i-1(LB)    i(T)
 68                 //T中键值往后移动,便于插入
 69                 for (int k = T->keyNum + 1; k > 1; --k)
 70                     T->keys[k] = T->keys[k - 1];
 71                     
 72                 for (int k = T->childNum; k > 0; --k)
 73                     T->children[k] = T->children[k - 1];
 74              
 75                 //旋转
 76                 T->keys[1] = P->keys[i];
 77                 T->children[0] = LB->children[LB->childNum - 1];
 78                 ++T->keyNum;
 79                 ++T->childNum;
 80 
 81                 P->keys[i] = LB->keys[LB->keyNum];
 82                 //LB->children[LB->childNum - 1] = NULL;
 83                 --LB->childNum;
 84                 --LB->keyNum;
 85             }
 86             else if (RB && RB->keyNum > 1) 
 87             {// 右兄弟存在且键值富余
 88                 //        i+1(P)
 89                 //   i(T)      i+1(RB)
 90                 T->keys[T->keyNum+1] = P->keys[i+1];
 91                 T->children[T->childNum] = RB->children[0];
 92                 ++T->keyNum;
 93                 ++T->childNum;
 94 
 95                 P->keys[i+1] = RB->keys[1];
 96                 for (int k = 1; k <= RB->keyNum - 1; ++k)
 97                     RB->keys[k] = RB->keys[k + 1];
 98                 
 99                 for (int k = 0; k < RB->childNum - 1; ++k)
100                     RB->children[k] = RB->children[k + 1];
101                 
102                 --RB->keyNum;
103                 --RB->childNum;
104             }
105             else if (LB) 
106             { // 左兄弟存在但不富余
107                 merge(P, i - 1);
108                 T = P->children[i - 1];
109             }
110             else if (RB) 
111             {// 右兄弟存在但不富余
112                 merge(P, i);
113                 T = P->children[i];
114             }
115         }
116     }
117     // 树根被借走,树高 -1
118     if (*Root == P && P->keyNum == 0)
119     {
120         *Root = P->children[0];
121         
122     }
123     return true;
124 }

查询

搜索到位空就好

 

 1 //查询该节点
 2 bool enquirytree(Treenode* node, int data)
 3 {
 4     //如果该节点没有值就没有这个data
 5     if (node == NULL)
 6         return 0;
 7     //查询该结点的关键字索引
 8     for (int i = 1; i <= node->keyNum; i++)
 9     {
10         if (data == node->keys[i])
11             return 1;
12         if (data < node->keys[i])//如果比i小,查询孩子
13             return enquirytree(node->children[i - 1],data);
14     }
15     //比最后的大
16     return enquirytree(node->children[node->keyNum], data);
17 }

 

热门相关:夜生活   妈妈的咪呀!我来了   豪门隐婚:老婆别闹了   傲娇总裁:蜜宠小甜妻!   豪门隐婚:老婆别闹了