数据结构备忘录：B树的插入和删除
程序员文章站
2022-12-05 08:44:01
B树的删除(仅考虑阶数m>=3的情形) 在非叶节点中删除关键码，只需从关键码右侧指针指向的子树中寻找最小关键码(沿最左侧指针向下走到叶节点，叶节点最左侧关键码即是)替换该关键码，并从最小关键码所在叶节点删除该最小关键码即可。这样只讨论在叶节点中删除关键码。 在叶节点中删除给定关键码，先删去该关键码及 ......
B树的删除(仅考虑阶数m>=3的情形)
在非叶节点中删除关键码，只需从关键码右侧指针指向的子树中寻找最小关键码(沿最左侧指针向下走到叶节点，叶节点最左侧关键码即是)替换该关键码，并从最小关键码所在叶节点删除该最小关键码即可。这样只讨论在叶节点中删除关键码。
在叶节点中删除给定关键码，先删去该关键码及其右侧空指针，然后若该叶节点为根节点，则删除操作结束(删除后的B树可能为空树)，若该叶节点不为根节点且关键码数大于等于ceil(m/2)-1,则删除操作结束。若该叶节点不为根节点且关键码数等于ceil(m/2)-2，则令该叶节点为当前节点，然后
设删除过程中当前节点关键数等于ceil(m/2)-2.
若当前节点为根节点且关键码数为0，则令根节点指针指向根节点唯一子树,删除根节点，删除操作结束
若当前节点不为根节点，则若该节点有右兄弟节点且右兄弟节点关键码数大于等于ceil(m/2)，则将父节点指向当前节点的指针右侧关键码下移至当前节点最右侧，将右兄弟节点最左侧指针移至当前节点最右侧，最后将右兄弟最左侧关键码上移至父节点指向其指针的左侧，删除操作结束。
若当前节点不为根节点，有右兄弟且右兄弟关键码数等于ceil(m/2)-1,则将父节点中指向当前节点的指针右侧关键码下移至当前节点最右侧，然后将右兄弟完整拼接至当前节点右侧，随后删除右兄弟节点和父节点中指向它的指针。此时父节点关键码子树数减一，若父节点为根节点且关键码数为0则回溯至父节点；若父节点不为根节点且关键码数大于等于ceil(m/2)-1，则删除操作结束；若父节点不为根节点且关键码数等于ceil(m/2)-2,则回溯至父节点
若当前节点不为根节点，没有右兄弟节点但有左兄弟节点，且左兄弟节点关键码数大于等于ceil(m/2),则将父节点中指向当前节点的指针左侧关键码下移至当前节点最左端，左兄弟最右侧关键码上移至父节点中指向它的指针右侧关键码位置，左兄弟最右侧指针移至当前节点最左端，随后删除操作结束
若当前节点不为根节点，没有右兄弟但有左兄弟，且左兄弟关键码数等于ceil(m/2)-1,则将父节点中指向当前节点的指针左侧关键码下移至当前节点最左端，左兄弟完整拼接至当前节点左侧，删除左兄弟和父节点中指向它的指针，此时父节点关键码子树数减一，若父节点为根节点且关键码数为0则回溯至父节点；若父节点不为根节点且关键码数大于等于ceil(m/2)-1，则删除操作结束；若父节点不为根节点且关键码数等于ceil(m/2)-2,则回溯至父节点
B树的插入(仅考虑阶数m>=3的情形)
在空树中插入直接新建根节点，两指针域置空，填入关键码,再令root指向根节点
若在非空树中插入
那么仅在叶节点上插入，通过搜索在叶节点中找到插入位置，将关键码和空指针构成的二元组插入至叶节点，若插入后叶节点关键码数小于等于m-1则插入结束，否则令叶节点为当前节点
现设插入过程中当前节点关键码数为m，以当前节点从左至右第ceil(m/2)个关键码为分割点将当前节点分隔为左右两部分(即分割点左侧和右侧的部分),左侧分割部分为原当前节点，若原当前节点为根节点，则直接新建根节点，两指针域分别指向左右分割部分，中间关键码即为原当前节点第ceil(m/2)个关键码，令root指向新根节点插入结束。
若原当前节点不为根节点，则将右侧分割部分的指针和原当前节点第ceil(m/2)个关键码构成的二元组插入至父节点中原当前节点对应的二元组右侧，此时父节点关键码子树数增一，若父节点关键码数小于等于m-1则插入结束，若父节点关键码数等于m,则以父节点为当前节点，回溯处理
插入和删除的C++实现(如有错误欢迎指出)
1 #include "stdafx.h"
2 #include <iostream>
3 #include <map>
4 #include <stack>
5 #include <vector>
6 using namespace std;
7
8 const int M = 4; //B树阶数
9 template <typename T>
10 struct BTreeNode
11 {
12 BTreeNode *p = nullptr;
13 map<T, BTreeNode<T> *> keyptrmap; //节点数据域和指针域
14 };
15
16 template <typename T>
17 pair<typename map<T, BTreeNode<T> *>::iterator, bool> SerachBTreeNode(BTreeNode<T> *ptr, pair<typename map<T, BTreeNode<T> *>::iterator, bool> d) //返回值：尾后+fasle表示第一指针,尾后+true表示失败,非尾后+true即为对应指针
18 {
19 typename map<T, BTreeNode<T> *>::iterator m; //实参pair:尾后+false表示从第一指针后一指针开始搜索,尾后+true表示从头搜索,非尾后+true表示从非尾后后一位置开始搜索
20 if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
21 {
22 if (ptr->p != nullptr)
23 return { d.first, false };
24 m = ptr->keyptrmap.begin();
25 }
26 else if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), false))
27 {
28 m = ptr->keyptrmap.begin();
29 }
30 else
31 {
32 m = d.first;
33 ++m;
34 }
35
36 for (; m != ptr->keyptrmap.end(); ++m)
37 {
38 if (m->second != nullptr)
39 return { m, true };
40 }
41 return { m, true };
42 }
43
44 template <typename T>
45 bool isBTree(BTreeNode<T> *root) //判断给定多叉树是否为B树
46 {
47 struct temp
48 {
49 T min; //节点某子树中最小节点值
50 T max; //节点某子树中最大节点值
51 T nodemin; //节点代表子树中最小值
52 T nodemax; //节点代表子树中最大值
53 };
54 struct memory
55 {
56 BTreeNode<T> *p;
57 pair<map<T, BTreeNode<T> *>::iterator, bool> direction;
58 temp minmax;
59 memory(BTreeNode<T> *p, const pair<map<T, BTreeNode<T> *>::iterator, bool> &d) :p(p), direction(d) {}
60 };
61
62 BTreeNode<T> *ptr = root;
63 pair<map<T, BTreeNode<T> *>::iterator, bool> d(ptr->keyptrmap.end(), true);
64 BTreeNode<T> *const dest = ptr;
65 stack<memory> arrange;
66 bool TF = false;
67 int level = 0;
68 int beforelevel = 0;
69 while (true)
70 {
71 if (SerachBTreeNode(ptr, d) == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
72 {
73 if (ptr == dest)
74 {
75 if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
76 {
77 if (1 <= ptr->keyptrmap.size() && ptr->keyptrmap.size() <= M-1)
78 return true;
79 else
80 {
81 cout << "当前树只有根节点,但根节点子树数量不符合要求,非B树"<<endl;
82 return false;
83 }
84 }
85 else
86 {
87 if (1 <= ptr->keyptrmap.size() && ptr->keyptrmap.size() <= M - 1)
88 {
89 typename map<T, BTreeNode<T> *>::iterator temp = ptr->keyptrmap.end();
90 --temp;
91 if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true))
92 {
93 if (arrange.top().minmax.min > temp->first)
94 {
95 return true;
96 }
97 else
98 {
99 cout << "当前树不是" << M << "路搜索树,非B树" << endl;
100 return false;
101 }
102 }
103 else
104 {
105 cout << "失败节点不在同一层,非B树" << endl;
106 return false;
107 }
108 }
109 else
110 {
111 cout << "当前树根节点子树数量不符合要求,非B树";
112 return false;
113 }
114 }
115 }
116 else
117 {
118 if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
119 {
120 ++level;
121 if (TF == false)
122 {
123 beforelevel = level;
124 TF = true;
125 }
126 else
127 {
128 if (level != beforelevel)
129 {
130 cout << "失败节点不在同一层,非B树" << endl;
131 return false;
132 }
133 beforelevel = level;
134 }
135
136 if ((M + 1) / 2 - 1 <= ptr->keyptrmap.size() && ptr->keyptrmap.size() <= M - 1)
137 {
138 typename map<T, BTreeNode<T> *>::iterator temp = arrange.top().p->keyptrmap.end();
139 --temp;
140 if (arrange.top().direction == pair<map<T, BTreeNode<T> *>::iterator, bool>(arrange.top().p->keyptrmap.end(), false))
141 {
142 arrange.top().minmax.nodemin = ptr->keyptrmap.begin()->first;
143 arrange.top().minmax.min = ptr->keyptrmap.begin()->first;
144 typename map<T, BTreeNode<T> *>::iterator it = ptr->keyptrmap.end();
145 --it;
146 arrange.top().minmax.max = it->first;
147 }
148 else if (arrange.top().direction == pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true))
149 {
150 typename map<T, BTreeNode<T> *>::iterator it = ptr->keyptrmap.end();
151 --it;
152 arrange.top().minmax.nodemax = it->first;
153 arrange.top().minmax.min = ptr->keyptrmap.begin()->first;
154 arrange.top().minmax.max = it->first;
155 }
156 else
157 {
158 arrange.top().minmax.min = ptr->keyptrmap.begin()->first;
159 typename map<T, BTreeNode<T> *>::iterator it = ptr->keyptrmap.end();
160 --it;
161 arrange.top().minmax.max = it->first;
162 }
163 }
164 else
165 {
166 cout << "当前树叶节点数量不符合要求,非B树" << endl;
167 return false;
168 }
169 }
170 else
171 {
172 if ((M + 1) / 2 - 1 <= ptr->keyptrmap.size() && ptr->keyptrmap.size() <= M - 1)
173 {
174 typename map<T, BTreeNode<T> *>::iterator temp = ptr->keyptrmap.end();
175 --temp;
176 if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true))
177 {
178 if (arrange.top().minmax.min > temp->first)
179 {
180 T key1 = arrange.top().minmax.nodemin;
181 T key2 = arrange.top().minmax.nodemax;
182 arrange.pop();
183 arrange.top().minmax.min = key1;
184 arrange.top().minmax.max = key2;
185 typename map<T, BTreeNode<T> *>::iterator temp = arrange.top().p->keyptrmap.end();
186 --temp;
187 if (arrange.top().direction == pair<map<T, BTreeNode<T> *>::iterator, bool>(arrange.top().p->keyptrmap.end(), false))
188 {
189 arrange.top().minmax.nodemin = arrange.top().minmax.min;
190 }
191 else if (arrange.top().direction == pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true))
192 {
193 arrange.top().minmax.nodemax = arrange.top().minmax.max;
194 }
195 }
196 else
197 {
198 cout << "当前树不是" << M << "路搜索树,非B树" << endl;
199 return false;
200 }
201 }
202 else
203 {
204 cout << "失败节点不在同一层,非B树" << endl;
205 return false;
206 }
207 }
208 else
209 {
210 cout << "当前树分支节点子树数量不符合要求,非B树" << endl;
211 return false;
212 }
213 }
214 --level;
215 ptr = arrange.top().p;
216 d = arrange.top().direction;
217 }
218 }
219 else
220 {
221 BTreeNode<T> *interval = nullptr;
222 if (d == pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true))
223 {
224 if (SerachBTreeNode(ptr, d) != pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), false))
225 {
226 cout << "失败节点不在同一层,非B树" << endl;
227 return false;
228 }
229 arrange.push(memory(ptr, SerachBTreeNode(ptr, d)));
230 interval = ptr->p;
231 ++level;
232 }
233 else
234 {
235 typename map<T, BTreeNode<T> *>::iterator temp = SerachBTreeNode(ptr, d).first;
236 if (d.first == ptr->keyptrmap.end())
237 {
238 if (temp == ptr->keyptrmap.begin())
239 {
240 if (!(arrange.top().minmax.max < temp->first))
241 {
242 cout << "当前树不是" << M << "路搜索树,非B树" << endl;
243 return false;
244 }
245 }
246 else
247 {
248 cout << "失败节点不在同一层,非B树"<<endl;
249 return false;
250 }
251 }
252 else
253 {
254 --temp;
255 if (temp == d.first)
256 {
257 ++temp;
258 if (!(arrange.top().minmax.max < temp->first && arrange.top().minmax.min > d.first->first))
259 {
260 cout << "当前树不是" << M << "路搜索树,非B树" << endl;
261 return false;
262 }
263 }
264 else
265 {
266 cout << "失败节点不在同一层,非B树" << endl;
267 return false;
268 }
269 }
270
271 arrange.top().direction = pair<map<T, BTreeNode<T> *>::iterator, bool>(temp, true);
272 interval = temp->second;
273 }
274 ptr = interval;
275 d = pair<map<T, BTreeNode<T> *>::iterator, bool>(ptr->keyptrmap.end(), true);
276 }
277 }
278 }
279
280 template <typename T>
281 BTreeNode<T> *InsertBTree(BTreeNode<T> *root, T key) //B树插入函数
282 {
283 if (root == nullptr)
284 {
285 root = new BTreeNode<T>;
286 root->keyptrmap.insert(make_pair(key, nullptr));
287 return root;
288 }
289 else
290 {
291 BTreeNode<T> *current = root;
292 stack<pair<BTreeNode<T> *, map<T, BTreeNode<T> *>::iterator>> stackforback;
293
294 while (true)
295 {
296 typename map<T, BTreeNode<T> *>::iterator scankey = current->keyptrmap.begin();
297 while (key > scankey->first)
298 {
299 ++scankey;
300 if (scankey == current->keyptrmap.end())
301 {
302 break;
303 }
304 }
305 if (scankey != current->keyptrmap.end())
306 {
307 if (scankey->first == key)
308 {
309 cout << "关键码" << key << "已存在，插入失败" << endl;
310 return root;
311 }
312 else
313 {
314 if (current->p == nullptr)
315 {
316 current->keyptrmap.insert(make_pair(key, nullptr));
317 break;
318 }
319 else
320 {
321 stackforback.push(make_pair(current, scankey));
322 if (scankey != current->keyptrmap.begin())
323 {
324 --scankey;
325 current = scankey->second;
326 }
327 else
328 {
329 current = current->p;
330 }
331 }
332 }
333 }
334 else
335 {
336 if (current->p == nullptr)
337 {
338 current->keyptrmap.insert(make_pair(key, nullptr));
339 break;
340 }
341 else
342 {
343 stackforback.push(make_pair(current, scankey));
344 --scankey;
345 current = scankey->second;
346 }
347 }
348 }
349
350 if (current->keyptrmap.size() <= M - 1)
351 {
352 return root;
353 }
354 else
355 {
356 while (true)
357 {
358 BTreeNode<T> *ptr = new BTreeNode<T>;
359 typename map<T, BTreeNode<T> *>::iterator temp = current->keyptrmap.begin();
360 ptr->p = current->p;
361 while (ptr->keyptrmap.size() < (M + 1) / 2 - 1)
362 {
363 ptr->keyptrmap.insert(*temp);
364 temp = current->keyptrmap.erase(temp);
365 }
366 current->p = temp->second;
367
368 if (stackforback.empty() == true)
369 {
370 root = new BTreeNode<T>;
371 root->p = ptr;
372 root->keyptrmap.insert(make_pair(temp->first, current));
373 current->keyptrmap.erase(temp);
374 return root;
375 }
376 else
377 {
378 stackforback.top().first->keyptrmap.insert(make_pair(temp->first, current));
379 current->keyptrmap.erase(temp);
380 typename map<T, BTreeNode<T> *>::iterator it = stackforback.top().second;
381 --it;
382 if (it == stackforback.top().first->keyptrmap.begin())
383 {
384 stackforback.top().first->p = ptr;
385 }
386 else
387 {
388 --it;
389 it->second = ptr;
390 }
391 if (stackforback.top().first->keyptrmap.size() <= M - 1)
392 {
393 return root;
394 }
395 else
396 {
397 current = stackforback.top().first;
398 stackforback.pop();
399 }
400 }
401 }
402 }
403 }
404 }
405
406 template <typename T>
407 BTreeNode<T> *DelBTree(BTreeNode<T> *root, T key) //B树删除函数
408 {
409 BTreeNode<T> *current = root;
410 stack<pair<BTreeNode<T> *, map<T, BTreeNode<T> *>::iterator>> stackforback;
411
412 while (true)
413 {
414 typename map<T, BTreeNode<T> *>::iterator scankey = current->keyptrmap.begin();
415 while (key > scankey->first)
416 {
417 ++scankey;
418 if (scankey == current->keyptrmap.end())
419 {
420 break;
421 }
422 }
423 if (scankey != current->keyptrmap.end())
424 {
425 if (scankey->first == key)
426 {
427 if (current->p == nullptr)
428 {
429 current->keyptrmap.erase(scankey);
430 }
431 else
432 {
433 stackforback.push(make_pair(current, ++scankey));
434 --scankey;
435 BTreeNode<T> *q = scankey->second;
436 while (q->p != nullptr)
437 {
438 stackforback.push(make_pair(q, q->keyptrmap.begin()));
439 q = q->p;
440 }
441 BTreeNode<T> *temp = scankey->second;
442 current->keyptrmap.erase(scankey);
443 current->keyptrmap.insert(make_pair(q->keyptrmap.begin()->first, temp));
444 q->keyptrmap.erase(q->keyptrmap.begin());
445 current = q;
446 }
447 break;
448 }
449 else
450 {
451 if (current->p == nullptr)
452 {
453 cout << "关键字" << key << "不存在，删除失败" << endl;
454 return root;
455 }
456 else
457 {
458 stackforback.push(make_pair(current, scankey));
459 if (scankey != current->keyptrmap.begin())
460 {
461 --scankey;
462 current = scankey->second;
463 }
464 else
465 {
466 current = current->p;
467 }
468 }
469 }
470 }
471 else
472 {
473 if (current->p == nullptr)
474 {
475 cout << "关键字" << key << "不存在，删除失败" << endl;
476 return root;
477 }
478 else
479 {
480 stackforback.push(make_pair(current, scankey));
481 --scankey;
482 current = scankey->second;
483 }
484 }
485 }
486
487 if (current == root)
488 {
489 if (current->keyptrmap.empty() == true)
490 {
491 delete current;
492 return nullptr;
493 }
494 else
495 {
496 return current;
497 }
498 }
499 else
500 {
501 if (current->keyptrmap.size() >= (M + 1) / 2 - 1)
502 {
503 return root;
504 }
505 else
506 {
507 while (true)
508 {
509 if (current == root)
510 {
511 current = current->p;
512 delete root;
513 return current;
514 }
515 else
516 {
517 typename map<T, BTreeNode<T> *>::iterator temp = stackforback.top().second;
518 if (temp != stackforback.top().first->keyptrmap.end())
519 {
520 if (temp->second->keyptrmap.size() >= (M + 1) / 2)
521 {
522 current->keyptrmap.insert(make_pair(temp->first, temp->second->p));
523 BTreeNode<T> *ptr = temp->second;
524 stackforback.top().first->keyptrmap.erase(temp);
525 stackforback.top().first->keyptrmap.insert(make_pair(ptr->keyptrmap.begin()->first, ptr));
526 ptr->p = ptr->keyptrmap.begin()->second;
527 ptr->keyptrmap.erase(ptr->keyptrmap.begin());
528 return root;
529 }
530 else
531 {
532 current->keyptrmap.insert(make_pair(temp->first, temp->second->p));
533 current->keyptrmap.insert(temp->second->keyptrmap.begin(), temp->second->keyptrmap.end());
534 delete temp->second;
535 stackforback.top().first->keyptrmap.erase(temp);
536 if (stackforback.top().first == root)
537 {
538 if (stackforback.top().first->keyptrmap.size() == 0)
539 {
540 current = stackforback.top().first;
541 stackforback.pop();
542 }
543 else
544 {
545 return root;
546 }
547 }
548 else
549 {
550 if (stackforback.top().first->keyptrmap.size() >= (M + 1) / 2 - 1)
551 {
552 return root;
553 }
554 else
555 {
556 current = stackforback.top().first;
557 stackforback.pop();
558 }
559 }
560 }
561 }
562 else
563 {
564 --temp;
565 BTreeNode<T> *ptr = nullptr;
566 if (temp != stackforback.top().first->keyptrmap.begin())
567 {
568 typename map<T, BTreeNode<T> *>::iterator before = temp;
569 --before;
570 ptr = before->second;
571 }
572 else
573 {
574 ptr = stackforback.top().first->p;
575 }
576
577 if (ptr->keyptrmap.size() >= (M + 1) / 2)
578 {
579 current->keyptrmap.insert(make_pair(temp->first, current->p));
580 typename map<T, BTreeNode<T> *>::iterator left = ptr->keyptrmap.end();
581 --left;
582 current->p = left->second;
583 stackforback.top().first->keyptrmap.erase(temp);
584 stackforback.top().first->keyptrmap.insert(make_pair(left->first, current));
585 ptr->keyptrmap.erase(left);
586 return root;
587 }
588 else
589 {
590 ptr->keyptrmap.insert(make_pair(temp->first, current->p));
591 ptr->keyptrmap.insert(current->keyptrmap.begin(), current->keyptrmap.end());
592 delete current;
593 stackforback.top().first->keyptrmap.erase(temp);
594
595 if (stackforback.top().first == root)
596 {
597 if (stackforback.top().first->keyptrmap.size() == 0)
598 {
599 current = stackforback.top().first;
600 stackforback.pop();
601 }
602 else
603 {
604 return root;
605 }
606 }
607 else
608 {
609 if (stackforback.top().first->keyptrmap.size() >= (M + 1) / 2 - 1)
610 {
611 return root;
612 }
613 else
614 {
615 current = stackforback.top().first;
616 stackforback.pop();
617 }
618 }
619 }
620 }
621 }
622 }
623 }
624 }
625 }
626
627 int main()
628 {
629 vector<int> seq{ 2, 7, 5, 19, 10, 18, 16, 12, 11, 15, 13, 14, 21, 29, 25, 20, 22, 28, 23, 26 };
630 BTreeNode<int> *root = nullptr;
631 for (vector<int>::const_iterator p = seq.cbegin(); p != seq.cend(); ++p)
632 {
633 cout << "插入节点" << *p << endl;
634 root = InsertBTree(root, *p);
635 cout << endl;
636 if (isBTree(root) == true)
637 {
638 cout << "当前树是B树";
639 cout << endl;
640 }
641 else
642 {
643 cerr << "错误当前树不是B树!" << endl;
644 exit(0);
645 }
646 }
647 cout << endl;
648 for (vector<int>::const_iterator p = seq.cbegin(); p != seq.cend(); ++p)
649 {
650 cout << "删除节点" << *p << endl;
651 root = DelBTree(root, *p);
652 if (root != nullptr)
653 {
654 if (isBTree(root) == true)
655 {
656 cout << "当前树是B树";
657 cout << endl;
658 }
659 else
660 {
661 cerr << "错误当前树不是B树!" << endl;
662 exit(0);
663 }
664 }
665 else
666 cout << "NULL";
667 cout << endl;
668 }
669 return 0;
670 }
运行结果：
上一篇： JDK5 新特性
下一篇： C++primer第九章习题解答