c/c++手撕B树

• B-树是一个非二叉树的多路平衡查找树(数据有序)，是一颗所有数据都存储在树叶节点上的树，不一定存储具体的数据，也可以是指向包含数据的记录的指针或地址

• 对于阶为M(子节点数量在2和M之间)的B-树具有一下结构特性：

  1. 树的根节点或者叶子节点，或者子节点数的范围为[2,M]

  2. B树每个结点关键字数量为[ceil(2/M)-1,M-1]

  3. 除根外，所有非树叶节点的子节点数在[ceil(2/M),M]之间，ceil为向上取整函数

  4. 所有的树叶都在相同的深度上

插入操作

• 插入在叶子节点进行

• 向B树中插入数据，根据非叶子节点的关键字找到正确的存储数据的叶子节点。

• 如果节点内的数据小于M-1(M为阶数)，就根据排列规则插入；如果节点能够存储的数据已经满了，就进行分裂节点(叶子节点)

  分裂节点操作步骤：

  1. 先看看该叶子节点的关键字数量是否小于M-1(M为阶数)

  2. 按顺序插入进去，节点的关键字数量如果大于M-1，就将该叶子节点分裂成两个叶子节点，两个叶子节点的数据各占原叶子节点的一半，中间的关键字(数据)作为根节点的关键字，剩下分成两部分的节点作为其(中间关键字形成的根节点)左右节点。当根节点大于M-1的时候，就分裂根节点！

  3. 如果小于则根据插入的关键字大小按顺序插入。

删除操作

1. 通过递归找到指定删除的节点

2. 删除的关键字在非叶子节点上，就将其左边的指向叶子节点中的最大值跟要删除的关键字互换，就递归进去删除最大值。

3. 删除的关键字在叶子节点上

   1. 叶子节点的关键字个数大于ceil(M/2-1),直接删除

   2. 叶子节点的关键字个数等于ceil(M/2-1),向父节点借关键字

4. 递归返回上一层后检查该节点的关键字数，如果小于ceil(M/2-1)，就向父节点借关键字，合并该关键字的左右节点，然后不断返回上一层，不断地检查，向父节点借关键字，合并子节点直到返回到根节点。

实现的代码：

我这里使用到了c 的STL的动态数组vector容器和pair对组，大部分还是用c写的，毕竟数据结构用c手撕才有意义，代码中的nullptr对应着c的NULL，splitNode函数为分裂节点函数，merge函数为合并节点函数

1.  
   #include <iostream>
2.  
   #include <vector>
3.  
   using namespace std;
4.  
    
5.  
   struct btree{
6.  
   int level; //树的阶数
7.  
   vector<int>keys; //关键字数组
8.  
   vector<btree*>child; //子节点数组
9.  
   int keynum; //节点的关键字数目
10.  
    btree* parent; //子节点的父节点
11.  
    };
12.  
     
13.  
    btree* createNode(int level){
14.  
    auto p=new btree;
15.  
    p->level=level;
16.  
    p->keynum=0;
17.  
    p->parent= nullptr;
18.  
    for(int i=0;i<=p->level;i ){
19.  
    p->child.push_back(nullptr);
20.  
    p->keys.push_back(0);
21.  
    }
22.  
    return p;
23.  
    }
24.  
     
25.  
    pair<btree*,int> find(btree* root,int key){
26.  
    int i;
27.  
    for(i=root->keynum;i>0;i--){
28.  
    if(key<root->keys[i]){
29.  
    continue;
30.  
    }else if(key>root->keys[i]){
31.  
    break;
32.  
    }else{
33.  
    return make_pair(root,i);
34.  
    }
35.  
    }
36.  
    pair<btree*,int>p=find(root->child[i],key);
37.  
    return p;
38.  
    }
39.  
     
40.  
     
41.  
    void splitNode(btree* &root,btree* p,int index){
42.  
    if(p!=nullptr){
43.  
    if(p->keynum==p->level){
44.  
    //分裂节点
45.  
    int mid=p->keynum/2 p->keynum%2;
46.  
    btree* newnode= createNode(p->level);
47.  
    newnode->parent=p->parent;
48.  
    for(int j=root->keynum;j>index-1;j--){
49.  
    root->keys[j 1]=root->keys[j];
50.  
    }
51.  
    root->keys[index]=p->keys[mid];
52.  
    root->keynum ;
53.  
    for(int j=mid 1;j<=p->keynum;j ){
54.  
    newnode->keys[j-mid]=p->keys[j];
55.  
    newnode->keynum ;
56.  
    }
57.  
    p->keynum=p->keynum-newnode->keynum-1;
58.  
    int k;
59.  
    for(k=root->level-1;k>index-1;k--){
60.  
    root->child[k 1]=root->child[k];
61.  
    }
62.  
    k ;
63.  
    root->child[k]=newnode;
64.  
    }
65.  
    }
66.  
    if(root->keynum==root->level) {
67.  
    btree *newchild = createNode(root->level);
68.  
    int mid = root->keynum / 2 root->keynum % 2;
69.  
    for (int i = mid 1; i <= root->level; i ) {
70.  
    newchild->keys[i - mid] = root->keys[i];
71.  
    newchild->keynum ;
72.  
    }
73.  
    for (int j = newchild->keynum; j <= newchild->level; j ) {
74.  
    if(root->child[j])
75.  
    root->child[j]->parent=newchild;
76.  
    newchild->child[j - newchild->keynum] = root->child[j];
77.  
    root->child[j] = nullptr;
78.  
    }
79.  
    if (root->parent == nullptr) {
80.  
    btree *newnode = createNode(root->level);
81.  
    newnode->keys[1] = root->keys[mid];
82.  
    newnode->keynum ;
83.  
    root->keynum = root->level - newchild->keynum - 1;
84.  
    newnode->child[0] = root;
85.  
    newnode->child[1] = newchild;
86.  
    root->parent = newnode;
87.  
    newchild->parent = newnode;
88.  
    root = newnode;
89.  
    } else {
90.  
    newchild->parent = root->parent;
91.  
    root->keynum = root->level - newchild->keynum - 1;
92.  
    int a = root->parent->keynum;
93.  
    while (a > 0 && root->keys[mid] < root->parent->keys[a]) {
94.  
    root->parent->keys[a 1] = root->parent->keys[a];
95.  
    root->parent->child[a 1] = root->parent->child[a];
96.  
    a--;
97.  
    }
98.  
    a ;
99.  
    root->parent->keys[a] = root->keys[mid];
100.  
     root->parent->keynum ;
101.  
     root->parent->child[a] = newchild;
102.  
     }
103.  
     }
104.  
     }
105.  
      
106.  
     btree* insert(btree* &root,int key){
107.  
     if(0==root->keynum){
108.  
     root->keys[1]=key;
109.  
     root->keynum ;
110.  
     return root;
111.  
     }
112.  
     int index=root->keynum;
113.  
     while (index>0&&key<root->keys[index]){
114.  
     root->keys[index 1]=root->keys[index];
115.  
     index--;
116.  
     }
117.  
     index ;
118.  
     if(root->child[0]!=nullptr){
119.  
     btree* p;
120.  
     if(index==root->keynum){
121.  
     p=root->child[index 1];
122.  
     }else{
123.  
     p=root->child[index-1];
124.  
     }
125.  
     if(root->child[0]->child[0]!=nullptr){
126.  
     p= insert(p,key);
127.  
     }else if(root->child[0]->child[0]==nullptr){
128.  
     int i=p->keynum;
129.  
     while (i>0&&key<p->keys[i]){
130.  
     p->keys[i 1]=p->keys[i];
131.  
     i--;
132.  
     }
133.  
     i ;
134.  
     p->keys[i]=key;
135.  
     p->keynum ;
136.  
     }
137.  
     splitNode(root,p,index);
138.  
     }else{
139.  
     root->keys[index]=key;
140.  
     root->keynum ;
141.  
     splitNode(root, nullptr,-1);
142.  
     }
143.  
     return root;
144.  
     }
145.  
      
146.  
     int findmax(btree* root){
147.  
     if(nullptr==root){
148.  
     return 0;
149.  
     }else if(root->child[0]!= nullptr){
150.  
     return findmax(root->child[root->keynum]);
151.  
     }
152.  
     return root->keys[root->keynum];
153.  
     }
154.  
      
155.  
      
156.  
     void merge(btree* &root,int key,int min,int n){
157.  
     int n1 = root->child[n-1]->keynum;
158.  
     int n2 = root->child[n]->keynum;
159.  
     if (n1 > min) {
160.  
     for (int j = n2; j > 0; j--) {
161.  
     root->child[n]->keys[j 1] = root->child[n]->keys[j];
162.  
     root->child[n]->child[j 1] = root->child[n]->child[j];
163.  
     }
164.  
     root->child[n]->child[1] = root->child[n]->child[0];
165.  
     root->child[n]->keys[1] = root->keys[n];
166.  
     root->keys[n]=root->child[n-1]->keys[n1];
167.  
     root->child[n]->child[0] = root->child[n-1]->child[n1];
168.  
     root->child[n-1]->child[n1] = nullptr;
169.  
     root->child[n-1]->child[0]->parent = root->child[n-1];
170.  
     root->child[n-1]->keynum--;
171.  
     root->child[n-1]->keys[n1] = NULL;
172.  
     root->child[n]->keynum ;
173.  
     } else if (n2 > min) {
174.  
     root->child[n-1]->keys[n1 1]=root->keys[n];
175.  
     root->keys[n]=root->child[n]->keys[1];
176.  
     root->child[n-1]->child[n1 1] = root->child[n]->child[0];
177.  
     root->child[n-1]->child[n1 1]->parent = root->child[n-1];
178.  
     root->child[n-1]->keynum ;
179.  
     for (int j = 1; j < n2; j ) {
180.  
     root->child[n]->keys[j] = root->child[n]->keys[j 1];
181.  
     root->child[n]->child[j - 1] = root->child[n]->child[j];
182.  
     }
183.  
     root->child[n]->child[n2-1]=root->child[n]->child[n2];
184.  
     root->child[n]->keys[n2] = NULL;
185.  
     root->child[n]->child[n2] = nullptr;
186.  
     root->child[n]->keynum--;
187.  
     } else {
188.  
     root->child[n-1]->keys[n1 1]=root->keys[n];
189.  
     root->child[n-1]->keynum ;
190.  
     int n3 = n2 n1 1;
191.  
     for (int j = n1 2; j <= n3; j ) {
192.  
     root->child[n-1]->keys[j] = root->child[n]->keys[j - n1-1];
193.  
     root->child[n-1]->child[j-1]=root->child[n]->child[j];
194.  
     root->child[n-1]->keynum ;
195.  
     }
196.  
     root->child[n]=nullptr;
197.  
     int index = root->keynum;
198.  
     while (index > n && key < root->keys[index]) {
199.  
     root->keys[index-1]=root->keys[index];
200.  
     root->child[index-1]=root->child[index];
201.  
     index--;
202.  
     }
203.  
     root->child[root->keynum]= nullptr;
204.  
     root->keynum--;
205.  
     if(root->parent== nullptr&&root->keynum==0){
206.  
     root->child[0]->parent= nullptr;
207.  
     root=root->child[0];
208.  
     }
209.  
     }
210.  
     }
211.  
      
212.  
     void del(btree* &root,int key){
213.  
     if(nullptr==root){
214.  
     return;
215.  
     }else{
216.  
     int i;
217.  
     for(i=root->keynum;i>0;i--){
218.  
     if(key<root->keys[i]){
219.  
     continue;
220.  
     }else if(key>root->keys[i]){
221.  
     del(root->child[i],key);
222.  
     }else{
223.  
     break;
224.  
     }
225.  
     }
226.  
     int min=(root->level/2 root->level%2)-1;
227.  
     if(0==i){
228.  
     if(root->child[i]&&root->child[i 1]){
229.  
     if(root->child[i]->keynum>=min&&root->child[i 1]->keynum>=min){
230.  
     del(root->child[i],key);
231.  
     }
232.  
     }
233.  
     i ;
234.  
     }
235.  
     if(root->child[0]!= nullptr){
236.  
     if(root->keynum>=min){
237.  
     if(root->keys[i]==key){
238.  
     int temp= findmax(root->child[i-1]);
239.  
     root->keys[i]=temp;
240.  
     del(root->child[i-1],temp);
241.  
     merge(root,key,min,i);
242.  
     }else if(key<root->keys[i]){
243.  
     if(root->child[i-1]->keynum<min){
244.  
     merge(root,key,min,i);
245.  
     }
246.  
     }else{
247.  
     if(root->child[i]->keynum<min){
248.  
     merge(root,key,min,i);
249.  
     }
250.  
     }
251.  
     }else{
252.  
     merge(root,key,min,i);
253.  
     }
254.  
     }else{
255.  
     int j;
256.  
     for(j=1;j<root->keynum;j ){
257.  
     if(root->keys[j]==key){
258.  
     break;
259.  
     }
260.  
     }
261.  
     for(int d=j;d<root->keynum;d ){
262.  
     root->keys[d]=root->keys[d 1];
263.  
     }
264.  
     root->keys[root->keynum]=NULL;
265.  
     if(root->keynum>min){
266.  
     root->keynum--;
267.  
     }else{
268.  
     root->keynum--;
269.  
     int index=root->parent->keynum;
270.  
     for(int k=root->keynum;k>0;k--){
271.  
     root->keys[k 1]=root->keys[k];
272.  
     }
273.  
     while (index>0&&key<=root->parent->keys[index]){
274.  
     index--;
275.  
     }
276.  
     if(0==index){
277.  
     root->keys[root->keynum 1]=root->parent->keys[1];
278.  
     }else{
279.  
     root->keys[root->keynum 1]=root->parent->keys[index];
280.  
     }
281.  
     }
282.  
     }
283.  
     }
284.  
     }
285.  
      
286.  
     //中序遍历
287.  
     void inorderprint(btree* root){
288.  
     if(nullptr!=root){
289.  
     int i;
290.  
     for(i=0;i<root->keynum;i ){
291.  
     if(root->child[i]!= nullptr){
292.  
     inorderprint(root->child[i]);
293.  
     }
294.  
     cout<<root->keys[i 1]<<" ";
295.  
     }
296.  
     if(root->child[i]!= nullptr)
297.  
     inorderprint(root->child[i]);
298.  
     }
299.  
     }
300.  
      
301.  
      
302.  
     int main(){
303.  
     btree* root= createNode(4);
304.  
     insert(root,1);
305.  
     insert(root,2);
306.  
     insert(root,3);
307.  
     insert(root,4);
308.  
     insert(root,10);
309.  
     insert(root,15);
310.  
     insert(root,23);
311.  
     insert(root,28);
312.  
     insert(root,30);
313.  
     insert(root,31);
314.  
     insert(root,32);
315.  
     insert(root,33);
316.  
     insert(root,34);
317.  
     insert(root,35);
318.  
     insert(root,36);
319.  
     insert(root,37);
320.  
     insert(root,38);
321.  
     insert(root,39);
322.  
     insert(root,40);
323.  
     insert(root,41);
324.  
     insert(root,42);
325.  
     insert(root,43);
326.  
     insert(root,44);
327.  
     del(root,31);
328.  
     inorderprint(root);
329.  
     system("pause");
330.  
     return 0;
331.  
     }

这篇好文章是转载于：学新通技术网