《算法导论》第十八章——B树_算法导论18答案

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。
B数与红黑树的不同之处在于B树的结点可以有很多个孩子。

18.1B树的定义

一棵B树T具有以下性质（根为T.root）

B树的高度

18.2B树上的基本操作

搜索B树

搜索B树与二叉树搜索相似，只是每个结点做的不是二叉而是根据结点的孩子做分支选择。更严格地说，是做(x.n+1)路的分支选择。

创建一棵空的B树

为了创建一棵B树，先用B_Tree_Create来创建一个空的根结点，然后调用B_Tree_Insert来添加新的结点。

向B树中插入一个关键字

经典二叉树插入：找到位置，新建结点，插入进去。
对于B树，我们可以看一下这个过程：

分裂B树中的结点

图解过程我找到一篇非常好的博客，在这里分享给大家，它的图画的很清晰。
慵懒de疯子的博客：浅析B-树分裂
https://blog.csdn.net/apt1203jn/article/details/79587593

我对分裂的理解：如果一个结点满了，就按其中间关键字分裂，这样就保证了每个关键字都不是满的。插入的时候，就可以直接插入到结点中，如果这个插入操作使得这个结点满了，就对这个结点再进行分裂。

在沿树单程下行方式向B树插入关键字

18.3从B树中删除关键字

1、如果是叶节点中的关键字，直接删除

2、a：如果左儿子中关键字个数≥t，在左儿子中寻找前驱，代替删除结点
b：如果右儿子中关键字个数≤t，在左儿子中寻找后继，代替删除结点
c：如果左右儿子关键字都只有t-1个，合并左右结点

3、还有两种情况，不知道怎么描述，看图吧！
第一种：

第二种：

这个第三种情况看看是能看懂的，不过代码十分复杂的，我借鉴了windmissing的博客：算法导论 第18章 B树
https://blog.csdn.net/mishifangxiangdefeng/article/details/7798672
有兴趣的话可以去看看她的代码。

最后是代码部分（建议粘贴到自己的编辑器中运行一下：）
B树.h

#pragma once
#include <iostream>
#define Disk_Write(x)
#define Disk_Read(x)
#define t 2			/*最小度数*/
#define MAX 2*t	/*内部结点最多的孩子个数*/
using namespace std;

/*B树的结点*/
typedef struct BTreeNode
{
	int n;						/*储存在这个结点中的关键字个数*/
	char key[MAX];				/*MAX个关键字，升序*/
	bool leaf;					/*判断是否是叶结点*/
	BTreeNode *child[MAX + 1];	/*指向孩子结点*/
}BTnode;

/*B树*/
typedef struct BTree
{
	BTnode* root;
}BTree;

/*搜索B树*/
BTnode* B_Tree_Search(BTnode* x, char k, int &i);

/*创建一棵空的B树*/
void B_Tree_Create(BTree* T, string ch);

/*分裂B树中的结点*/
void B_Tree_Split_Child(BTnode* x, int i);

/*将关键字插入到结点x*/
void B_Tree_Insert_Nonfull(BTnode* x, char k);

/*向B树中插入一个关键字*/
void B_Tree_Insert(BTree* T, char k);

/*从B树中删除关键字*/
void B_Tree_Delete(BTree* &T, BTnode* x, char k);

/*打印B树*/
void B_Tree_Print(BTnode* x);


void B_Tree_PrintDetail(BTnode *x);

/*测试函数*/
void TestBTree();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

B树.cpp

#include "B树.h"
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;

/*搜索B树*/
BTnode* B_Tree_Search(BTnode* x, char k, int &i)
{
	i = 1;
	while (i <= x->n && k > x->key[i])/*计算最小下标i，使得k≤x.key[i]*/
		i++;
	if (i <= x->n && k == x->key[i])
		return x;
	else if (x->leaf)/*没有找到这个关键字*/
	{
		i = 0;
		return NULL;
	}
	else 
	{
		Disk_Read(x->child[i]);
		return B_Tree_Search(x->child[i], k, i);/*对子树再次寻找*/
	}
}

/*创建一棵空的B树*/
void B_Tree_Create(BTree* T, string ch)
{
	BTnode* x = new BTnode();/*新建一个结点*/
	x->leaf = true;
	x->n = 0;

	Disk_Write(x);
	T->root = x;

	for (int i = 0; i < ch.length(); i++)
	{
		B_Tree_Insert(T, ch[i]);
	}
}

/*分裂B树中的结点*/
void B_Tree_Split_Child(BTnode* x, int i)/*一个非满的内部结点x，使x.child[i]为满子结点的下标i*/
{
	BTnode* z = new BTnode();
	BTnode* y = x->child[i];
	z->leaf = y->leaf;
	z->n = t - 1;

	for (int j = 1; j <= t - 1; j++)/*把y的t-1个关键字分给z*/
	{
		z->key[j] = y->key[j + t];
	}

	if (y->leaf==false)/*如果y有孩子，就把这个孩子给z*/
	{
		for (int j = 1; j <= t; j++)
		{
			z->child[j] = y->child[j + t];
		}
	}

	y->n = t - 1;

	for (int j = x->n + 1; j >= i + 1; j--)/*把z插入为x的一个孩子*/
	{
		x->child[j + 1] = x->child[j];
	}
	x->child[i + 1] = z;

	for (int j = x->n; j >= i; j--)/*提升y的中间关键字到x*/
	{
		x->key[j + 1] = x->key[j];
	}
	x->key[i] = y->key[t];
	x->n++;

	Disk_Write(y);
	Disk_Write(z);
	Disk_Write(x);
}

/*将关键字插入到结点x*/
void B_Tree_Insert_Nonfull(BTnode* x, char k)
{
	int i = x->n;
	if (x->leaf)/*x是叶结点*/
	{
		while (i >= 1 && k < x->key[i])/*寻找要插入的位置*/
		{
			x->key[i + 1] = x->key[i];/*把数据后移*/
			i--;
		}
		x->key[i + 1] = k;
		x->n++;
		Disk_Write(x);
	}
	else/*x不是叶节点*/
	{
		while (i >= 1 && k < x->key[i])
		{
			i--;
		}
		i++;
		Disk_Read(x->child[i]);
		if (x->child[i]->n == 2 * t - 1)/*如果x的子结点是满的*/
		{
			B_Tree_Split_Child(x, i);/*分裂这个孩子*/
			if (k > x->key[i])
				i++;
		}
		B_Tree_Insert_Nonfull(x->child[i], k);/*插入到孩子中*/
	}
}

/*向B树中插入一个关键字*/
void B_Tree_Insert(BTree* T, char k)
{
	BTnode* r = T->root;
	if (r->n == 2 * t - 1)
	{
		BTnode* s = new BTnode();
		T->root = s;
		s->leaf = false;
		s->n = 0;
		s->child[1] = r;
		B_Tree_Split_Child(s, 1);/*分裂原来的根结点*/
		B_Tree_Insert_Nonfull(s, k);
	}
	else 
	{
		B_Tree_Insert_Nonfull(r, k);
	}
}

/*从B树中删除关键字*/
void B_Tree_Delete(BTree* &T,BTnode* x, char k)
{
	int i, j;

	for (i = 1; i <= x->n; i++)
	{
		if (x->key[i] >= k)
			break;
	}

	BTnode* y = x->child[i];/*y是k前面的结点*/
	BTnode* z = x->child[i + 1];/*z是k后面的结点*/
	BTnode *d;

	if (x->key[i] == k && i <= x->n)/*关键字在x中第i个位置*/
	{
		if (x->leaf == true)/*x是叶结点*/
		{
			for (j = i; j < x->n; j++)
			{
				x->key[j] = x->key[j + 1];/*关键字前移*/
			}
			x->n--;
			return;
		}
		if (y->n >= t)/*情况2a*/
		{
			d = y;
			while (d->leaf == false)
			{
				d = d->child[d->n + 1];/*寻找前驱*/
			}
			x->key[i] = d->key[d->n];
			B_Tree_Delete(T, y, d->key[d->n]);
		}
		else if (z->n >= t)/*情况2b*/
		{
			d = z;
			while (d->leaf == false)
			{
				d = d->child[1];/*寻找后继*/
			}
			x->key[i] = d->key[1];
			B_Tree_Delete(T, y, d->key[d->n]);
		}
		else/*情况2c*/
		{
			y->key[y->n + 1] = k;
			for (j = 1; j <= z->n; j++)
				y->key[y->n + j + 1] = z->key[j];
			if (y->leaf == false)
			{
				for (j = 1; j <= z->n + 1; j++)
					y->child[y->n + j + 1] = z->child[j];
			}
			y->n = y->n + 1 + z->n;
			for (j = i; j < x->n; j++)
				x->key[j] = x->key[j + 1];
			for (j = i + 1; j <= x->n; j++)
				x->child[j] = x->child[j + 1];
			x->n--;
			if (x->n == 0 && T->root == x)
				T->root = y;
			delete z;
			B_Tree_Delete(T, y, k);
		}
	}
	else
	{
		if (x->leaf == true)
		{
			cout << "不存在！" << endl;
			return;
		}
		if (y->n == t - 1)/*情况3第一种*/
		{
			if (i <= x->n && i <= x->n && z->n >= t)
			{
				y->n++;
				y->key[y->n] = x->key[i];
				x->key[i] = z->key[1];
				for (j = 1; j < z->n; j++)
					z->key[j] = z->key[j + 1];
				if (y->leaf == false)
				{
					y->child[y->n + 1] = z->child[1];
					for (j = 1; j <= z->n; j++)
						z->child[j] = z->child[j + 1];
				}
				z->n--;
			}
			//它的相邻兄弟x->child[i-1]包含至少t个关键字
			else if (i > 1 && x->child[i - 1]->n >= t)
			{
				//将x中的关键字下降至y
				for (j = y->n; j >= 1; j--)
					y->key[j + 1] = y->key[j];
				y->key[1] = x->key[i - 1];
				y->n++;
				//将y的相邻兄弟x->child[i-1]的某一关键字上升至x
				x->key[i - 1] = x->child[i - 1]->key[x->child[i - 1]->n];
				//将该兄弟适合的子女指针移到y
				if (y->leaf == false)
				{
					for (j = y->n; j >= 1; j--)
						y->child[j + 1] = y->child[j];
					y->child[1] = x->child[i - 1]->child[x->child[i - 1]->n + 1];
				}
				//x->child[i-1]的关键字数-1
				x->child[i - 1]->n--;
			}
			//y和其所有相邻兄弟都只有t-1个关键字，则与其中一个兄弟合并
			else
			{
				//与后面一个结点(用z表示)合并
				if (i <= x->n)
				{
					//将x->key[i]并入y中
					y->key[y->n + 1] = x->key[i];
					//将z中所有关键字并入y中
					for (j = 1; j <= z->n; j++)
						y->key[j + y->n + 1] = z->key[j];
					//如果有孩子，所有孩子也要并入
					if (y->leaf == false)
					{
						for (j = 1; j <= z->n + 1; j++)
							y->child[j + y->n + 1] = z->child[j];
					}
					//修改y的关键字数
					y->n = y->n + 1 + z->n;
					//将x->key[i]从x中移出
					for (j = i; j < x->n; j++)
						x->key[j] = x->key[j + 1];
					//把指向z的指针从x->child中移出
					for (j = i + 1; j <= x->n; j++)
						x->child[j] = x->child[j + 1];
					//x的关键字数-1
					x->n--;
					//若根结点被删除，更新根结点
					if (x->n == 0 && T->root == x)
						T->root = y;
				}
				//与前面一个结点合并
				else
				{
					//令z=x->child[i-1],y=x->child[i]，把z并入y中
					z = y; i--;
					y = x->child[i];
					//将x->key[i]并入y中
					y->key[y->n + 1] = x->key[i];
					//将z中所有关键字并入y中
					for (j = 1; j <= z->n; j++)
						y->key[j + y->n + 1] = z->key[j];
					//如果有孩子，所有孩子也要并入
					if (y->leaf == false)
					{
						for (j = 1; j <= z->n + 1; j++)
							y->child[j + y->n + 1] = z->child[j];
					}
					//修改y的关键字数
					y->n = y->n + 1 + z->n;
					//将x->key[i]从x中移出
					for (j = i; j < x->n; j++)
						x->key[j] = x->key[j + 1];
					for (j = i + 1; j <= x->n; j++)
						x->child[j] = x->child[j + 1];
					x->n--;
					if (x->n == 0 && T->root == x)
						T->root = y;
				}
			}
		}
		B_Tree_Delete(T,y, k);
	}
}

/*打印B树*/
void B_Tree_Print(BTnode* x)
{
	for (int i = 1; i <= x->n; i++)
	{
		if (x->leaf == false)
			B_Tree_Print(x->child[i]);
		cout << x->key[i] << " ";
	}
	if (x->leaf == false)
		B_Tree_Print(x->child[x->n+1]);
}
void B_Tree_PrintDetail(BTnode *x)
{

	cout << "根结点:";
	for (int i = 1; i <= x->n; i++)
		cout << x->key[i] << "  ";
	cout << endl;

	cout << "根结点的孩子:" << endl;
	for (int j = 1; j <= x->n + 1; j++)
	{
		BTnode *child = x->child[j];
		for (int i = 1; i <= child->n; i++)
			cout << child->key[i] << "   ";
		cout << endl;
	}

	for (int i = 1; i <= x->n + 1; i++)
	{
		cout << "第 " << i << "个孩子" << endl;
		BTnode *ccc = x->child[i];
		int m = ccc->n + 1;
		for (int j = 1; j <= m; j++)
		{
			BTnode *c1 = ccc->child[j];
			for (int jj = 1; jj <= c1->n; jj++)
				cout << c1->key[jj] << "  ";
			cout << endl;
		}
	}
}

/*测试函数*/
void TestBTree()
{
	string ch= "KSQFCLHTVWMRNPABXYDZE";
	BTree *T = new BTree();
	B_Tree_Create(T, ch);
	cout << "创建一棵B树：" << endl;
	B_Tree_Print(T->root);
	cout << endl;
	B_Tree_PrintDetail(T->root);

	cout << endl;
	cout << "输入你想寻找的数：";
	char key;
	int i = 0;
	cin >> key;
	BTnode* value = B_Tree_Search(T->root, key, i);
	if (value == NULL)
		cout << "不存在！" << endl;
	else
	{
		for (int j = 1; j <= value->n; j++)
			cout << value->key[j] << " ";
	}
	cout << endl;

	cout << "输入你想要删除的数：";
	cin >> key;
	B_Tree_Delete(T, T->root, key);
	cout << "删除之后：" << endl;
	B_Tree_Print(T->root);
	cout << endl;
	B_Tree_PrintDetail(T->root);

	cout << "重新插入这颗结点后：" << endl;
	B_Tree_Insert(T, key);
	B_Tree_Print(T->root);
	cout << endl;
	B_Tree_PrintDetail(T->root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399

主函数

#include "B树.h"
#include <stdio.h>

int main()
{
	TestBTree();
	getchar();
	getchar();
	return 0;
}
1
2
3
4
5
6
7
8
9
10

运行结果

参考文章与博客：
慵懒de疯子的博客：浅析B-树分裂
https://blog.csdn.net/apt1203jn/article/details/79587593

iffTimes的博客：算法导论 第十八章；B树
https://blog.csdn.net/u010183397/article/details/46941045

windmissing的博客：算法导论 第18章 B树
https://blog.csdn.net/mishifangxiangdefeng/article/details/7798672