《算法导论》第十八章——B树
虽然写这个博客主要目的是为了给我自己做一个思路记忆录，但是如果你恰好点了进来，那么先对你说一声欢迎。我并不是什么大触，只是一个菜菜的学生，如果您发现了什么错误或者您对于某些地方有更好的意见，非常欢迎您的斧正！
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.****.net/apt1203jn/article/details/79587593
我对分裂的理解：如果一个结点满了，就按其中间关键字分裂，这样就保证了每个关键字都不是满的。插入的时候，就可以直接插入到结点中，如果这个插入操作使得这个结点满了，就对这个结点再进行分裂。
在沿树单程下行方式向B树插入关键字
18.3从B树中删除关键字
1、如果是叶节点中的关键字，直接删除
2、a：如果左儿子中关键字个数≥t，在左儿子中寻找前驱，代替删除结点
b：如果右儿子中关键字个数≤t，在左儿子中寻找后继，代替删除结点
c：如果左右儿子关键字都只有t-1个，合并左右结点
3、还有两种情况，不知道怎么描述，看图吧！
第一种：
第二种：
这个第三种情况看看是能看懂的，不过代码十分复杂的，我借鉴了windmissing的博客：算法导论 第18章 B树
https://blog.****.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();
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);
}
主函数
#include "B树.h"
#include <stdio.h>
int main()
{
TestBTree();
getchar();
getchar();
return 0;
}
运行结果
参考文章与博客：
慵懒de疯子的博客：浅析B-树分裂
https://blog.****.net/apt1203jn/article/details/79587593
iffTimes的博客：算法导论 第十八章；B树
https://blog.****.net/u010183397/article/details/46941045
windmissing的博客：算法导论 第18章 B树
https://blog.****.net/mishifangxiangdefeng/article/details/7798672