# 一、定义 ### 1、B树 B树是为磁盘或其它直接存取辅助存储设备而设计的一种平衡查找树，主要特点是降低磁盘I/O操作次数。 B树以自然的方式推广二叉查找树。 B树的分支因子由磁盘特性所决定。  ### 2、B数的数据结构 int n：当前存储在结点x中的关键字数 key[N]：n个关键，以非降序存放 bool leaf;//TRUE:x是叶子；FALSE:x是内结点 node *child[N+1]：只有内结点才有。指向其n+1个孩子的指针。child[1].key <= key[1] <= child[2].key…… ### 3.B树的特征 （1）只有内结点才有指向子女的指针，且child[1].key <= key[1] <= child[2].key…… （2）每个叶结点具有相同的深度 （3）分支因子t>=2 （4）每个非根结点至少有t-1个关键字，如果是内结点，至少有t个子女 （5）每个结点至多有2t-1个关键字，如果是内结点，到多有2t个子女 ### 4.B树上的操作 B-Tree-Search(x, k) B-Tree-Create(T) B-Tree-Split-Child(x,i,y) B-Tree-Insert(T,k) B-Tree-Insert-Nonfull(x,k) B-Tree-Delete(T,x) # 二、代码 ### B_Tree.h ~~~ #include <iostream> using namespace std; #define N 10 int t = 2; //B树结点结构 struct node { int n;//当前存储在结点x中的关键字数 char key[N];//n个关键字，以非降序存放 bool leaf;//TRUE:x是叶子；FALSE:x是内结点 node *child[N+1];//指向其n+1个孩子的指针 //构造函数 node(int num, bool IsLeaf):n(num),leaf(IsLeaf){} //磁盘读写操作 void Disk_Read(){} void Disk_Write(){} }; //B树结构 class B_Tree { public: //指向根结点 node *root; B_Tree():root(NULL){} //从以x为根结点的树中寻找关键字为k的结点，若找到，将结果存入y中，返回其是第几个关键字 int B_Tree_Search(node *x, char k, node&y); //构造一棵带树结点的空树 void B_Tree_Create(); //分裂，把y分裂为两个结点，选择其中一个关键字插入到x中的第i个位置 void B_Tree_Split_Child(node *x, int i, node *y); //将关键字k插入到一个未满的结点x中 void B_Tree_Insert_Nonfull(node *x, char k); //向T中插入关键字k void B_Tree_Insert(char k); //删除T树中关键字为k的结点，由于是递归方法，当前处理的是x结点 void B_Tree_Delete(node *x, char k); //按关键字从小到大输出结点 void Print(node *n); }; //从以x为根结点的树中寻找关键字为k的结点，若找到，将结果存入y中，返回其是第几个关键字 int B_Tree::B_Tree_Search(node *x, char k, node&y) { int i = 1; //找到第一个关键字不大于k的i while(i < x->n && k > x->key[i]) i++; //若key[i] = k，则找到了 if(i <= x->n && k == x->key[i]) { //将结果存入y中 y = *x; //返回其是第几个关键字 return i; } //若没找到，则返回空 if(x->leaf) { // &y = NULL; return 0; } //若还有子树可以找，则递归查找第i个子树 x->child[i]->Disk_Read(); return B_Tree_Search(x->child[i], k, y); } //构造一棵带树结点的空树 void B_Tree::B_Tree_Create() { //生成一个根结点 //初始时，根结点为叶子结点，根结点中没有关键字 root = new node(0, true); root->Disk_Write(); } //分裂，把y分裂为两个结点，选择其中一个关键字插入到x中的第i个位置 void B_Tree::B_Tree_Split_Child(node *x, int i, node *y) { int j; //生成一个新结点z //要把y分裂为y和z，因此z的叶子属性与y相同 //分裂前y有2t-1个关键字，分裂后前t-1个属于y，后t-1个属于z，中间第t个属于x node *z = new node(t-1, y->leaf); y->n = t - 1; //后t-1个关键字依次复制给z for(j = 1; j < t; j++) z->key[j] = y->key[j+t]; //如果有孩子，孩子也要复制过去，原来有2t个子树，前t个属于y，后t个属于z if(y->leaf == false) { for(j = 1; j <= t; j++) z->child[j] = y->child[j+t]; } //使z作为x的第i+1个孩子(y已经是x的第i个孩子) for(j = x->n+1; j > i; j--) x->child[j+1] = x->child[j]; x->child[i+1] = z; //把y中第t个关键字插入到x的第i个位置 for(j = x->n; j >= i; j--) x->key[j+1] = x->key[j]; x->key[i] = y->key[t]; //x的关键字+1 x->n++; y->Disk_Write(); z->Disk_Write(); x->Disk_Write(); } //将关键字k插入到一个未满的结点x中 void B_Tree::B_Tree_Insert_Nonfull(node *x, char k) { int i = x->n; //若x是叶子结点 if(x->leaf) { //找到该插入的位置 while(i >= 1 && k < x->key[i]) { x->key[i+1] = x->key[i]; i--; } //插入关键字k x->key[i+1] = k; x->n++; x->Disk_Write(); } //若不是叶子结点 else { //找到该插入的位置 while(i >= 1 && k < x->key[i]) i--; i++; //读取其孩子，将关键字插入到它的孩子中，分两种情况 x->child[i]->Disk_Read(); //孩子已满 if(x->child[i]->n == 2 * t - 1) { //对孩子执行分裂操作，分裂后，孩子不变为不满 B_Tree_Split_Child(x, i, x->child[i]); if(k > x->key[i]) i++; } //孩子不满，直接对孩子进行插入操作 B_Tree_Insert_Nonfull(x->child[i], k); } } //向T中插入关键字k void B_Tree::B_Tree_Insert(char k) { node *r = root, *s; //若根结点已满 if(r->n == 2*t-1) { //申请一个新的结点,将新的结点作为根结点 root = new node(0, false); root->child[1] = r; //将原根结点分裂为两个结点，分别作为s的第0个孩子和第1个孩子 B_Tree_Split_Child(root, 1, r); //把关键字k插入到根结点中，此时根结点一定不满 B_Tree_Insert_Nonfull(root, k); } //若根结点不满 else //直接把关键字插入到根结点中 B_Tree_Insert_Nonfull(r, k); } //删除T树中关键字为k的结点，由于是递归方法，当前处理的是x结点 void B_Tree::B_Tree_Delete(node *x, char k) { int i, j; //找到x中第一个不小于k的关键字，即待处理的位置 for(i = 1; i <= x->n; i++) if(x->key[i] >= k) break; //y是关键字k之前的结点,即小于k的最大孩子 //z是关键字k之后的结点,即大于k的最小孩子 node *y = x->child[i], *z = x->child[i+1], *d; //若关键字k在结点x中的第i个位置 if(x->key[i] == k && i <= x->n) { //1)y是叶子结点，则直接从x中删除k if(x->leaf == true) { //关键字依次前移 for(j = i; j < x->n; j++) x->key[j] = x->key[j+1]; //关键字数-1 x->n--; return; } //2)x是内结点 //2-a：x中前于k的子结点y包含至少t个关键字 if(y->n >= t) { //找出k在以y为根的子树中的前驱d d = y; while(d->leaf == false) d = d->child[d->n+1]; //用d取代k x->key[i] = d->key[d->n]; //递归地删除d B_Tree_Delete(y, d->key[d->n]); } //2-b：x是位于k之后的子结点z包含至少t个关键字 else if(z->n >= t) { //找出k在以z为根的子树中的后继d d = z; while(d->leaf == false) d = d->child[1]; //用d取代k x->key[i] = d->key[1]; //递归地删除d B_Tree_Delete(z, d->key[1]); } //2-c：y和z都只有t-1个关键字，将k和z中所有关键字合并进y，使得x失去k和指向z的指针 else { //将k关键字合并进y y->key[y->n+1] = k; //将z中所有关键字合并进y for(j = 1; j <= z->n; j++) y->key[y->n+j+1] = z->key[j]; //如果有孩子，孩子也要合并 if(y->leaf == false) { //使得x指向z的指针 for(j = 1; j <= z->n+1; j++) y->child[y->n+j+1] = z->child[j]; } //y包含2t-1个关键字 y->n = y->n + 1 + z->n; //使得x失去k for(j = i; j < x->n; j++) x->key[j] = x->key[j+1]; //使x失去指向z的指针 for(j = i+1; j <= x->n; j++) x->child[j] = x->child[j+1]; x->n--; //如果x是根结点，x if(x->n == 0 && root == x) root = y; //释放z delete z; //将k从y中递归删除 B_Tree_Delete(y, k); } } //3)关键字不在结点x中，则必定包含k的正确的子树的根x->child[i] else { //x是叶子结点,找到根结点都没有找到k，则k不在树中 if(x->leaf == true) { cout<<"error:not exist"<<endl; return; } //x是内结点 //3-a:child[i]中只有t-1个关键字 if(y->n == t-1) { //它的相邻兄弟x->child[i+1](用z表示)包含至少t个关键字 if(i <= x->n && i <= x->n && z->n >= t) { //将x中的关键字下降至y y->n++; y->key[y->n] = x->key[i]; //将z的某一关键字上升至x x->key[i] = z->key[1]; for(j = 1; j < z->n; j++) z->key[j] = z->key[j+1]; //将z适合的子女指针移到y 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的关键字数-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 && root == x) 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]; //把指向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 && root == x) root = y; } } } //递归执行删除操作 B_Tree_Delete(y, k); } } //按关键字从小到大输出结点 void B_Tree::Print(node *n) { int i; for(i = 1; i <= n->n; i++) { if(n->leaf == false) Print(n->child[i]); cout<<n->key[i]<<' '; } if(n->leaf == false) Print(n->child[n->n+1]); } ~~~ ### main.cpp ~~~ #include <iostream> using namespace std; #include "B_Tree.h" int main() { //测试数据 char ch[] = {'F','S','Q','K','C','L','H','T','V','W','M','R','N','P','A','B','X','Y','D','Z','E'}; //生成一棵B树 B_Tree *T = new B_Tree; T->B_Tree_Create(); //依次插入关键字 cout<<"插入测试"<<endl; int i; for(i = 0; i < 21; i++) { T->B_Tree_Insert(ch[i]); T->Print(T->root); cout<<endl; } //输出这棵树 T->Print(T->root); cout<<endl; //B树删除操作测试 cout<<"查找与删除测试"<<endl; char c; for(i = 0; i < 100; i++) { cin>>c; T->B_Tree_Delete(T->root, c); T->Print(T->root); cout<<endl; } return 0; } ~~~ # 三、练习 ### 18.1B树的定义 18.1-1 若t=1，树中的结点最少有0个关键字，就没有意义了 18.1-2 t=2 18.1-3 [http://zh.clrs-ans.wikia.com/index.php?title=18.1_B%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89&variant=zh-cn](http://zh.clrs-ans.wikia.com/index.php?title=18.1_B%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89&variant=zh-cn)     18.1-4 2^(2t)-1 18.1-5 没看懂题目 ### 18.2对B树的基本操作 18.2-1  18.2-2 待解决 [http://bbs.csdn.net/topics/390279127](http://bbs.csdn.net/topics/390279127) 18.2-3 类似于红黑树中的找前驱和后继的操作 ~~~ //若要找x->key[i]的前驱d d = x->child[i]; while(d->leaf == false) d = d->child[d->n+1]; ~~~ ~~~ //若要找x->key[i]的后继d d = x->child[i+1]; while(d->leaf == false) d = d->child[1]; ~~~ 18.2-4 在网上找了份答案 说是 至少n - 2lg（N） - 2个节点 没有解答！ 总之渐进意义上说 是n个 没必要太纠结与细节 没想到怎么求，写了个程序来计算，依次插入1-n，每分裂一次就cnt+1 ~~~ #include <iostream> using namespace std; #define N 10 int t = 2, cnt; //B树结点结构 struct node { int n;//当前存储在结点x中的关键字数 int key[N];//n个关键字，以非降序存放 bool leaf;//TRUE:如果x是叶子FALSE:内结点 node *child[N+1];//指向其n+1个孩子的指针 }; //B树结构 struct B_Tree { //指向根结点 node *root; }; //磁盘读写操作 void Disk_Read(node *x){} void Disk_Write(node *x){} //构造一棵带树结点的空树 void B_Tree_Create(B_Tree *T) { //生成一个根结点 node *x = new node; //初始时，根结点为叶子结点 x->leaf = true; //初始时，根结点中没有关键字 x->n = 0; Disk_Write(x); T->root = x; cnt = 1; } //分裂，把y分裂为两个结点，选择其中一个关键字插入到x中的第i个位置 void B_Tree_Split_Child(node *x, int i, node *y) { cnt++; int j; //生成一个新结点z node *z = new node; //要把y分裂为y和z，因此z的叶子属性与y相同 z->leaf = y->leaf; //分裂前y有2t-1个关键字，分裂后前t-1个属于y，后t-1个属于z，中间第t个属于x z->n = t - 1;y->n = t - 1; //后t-1个关键字依次复制给z for(j = 1; j < t; j++) z->key[j] = y->key[j+t]; //如果有孩子，孩子也要复制过去，原来有2t个子树，前t个属于y，后t个属于z if(y->leaf == false) { for(j = 1; j <= t; j++) z->child[j] = y->child[j+t]; } //使z作为x的第i+1个孩子(y已经是x的第i个孩子) for(j = x->n+1; j > i; j--) x->child[j+1] = x->child[j]; x->child[i+1] = z; //把y中第t个关键字插入到x的第i个位置 for(j = x->n; j >= i; j--) x->key[j+1] = x->key[j]; x->key[i] = y->key[t]; //x的关键字+1 x->n++; Disk_Write(y); Disk_Write(z); Disk_Write(x); } //将关键字k插入到一个未满的结点x中 void B_Tree_Insert_Nonfull(node *x, int k) { int i = x->n; //若x是叶子结点 if(x->leaf) { //找到该插入的位置 while(i >= 1 && k < x->key[i]) { x->key[i+1] = x->key[i]; i--; } //插入关键字k x->key[i+1] = k; x->n++; Disk_Write(x); } //若不是叶子结点 else { //找到该插入的位置 while(i >= 1 && k < x->key[i]) i--; i++; //读取其孩子，将关键字插入到它的孩子中，分两种情况 Disk_Read(x->child[i]); //孩子已满 if(x->child[i]->n == 2 * t - 1) { //对孩子执行分裂操作，分裂后，孩子不变为不满 B_Tree_Split_Child(x, i, x->child[i]); if(k > x->key[i]) i++; } //孩子不满，直接对孩子进行插入操作 B_Tree_Insert_Nonfull(x->child[i], k); } } //向T中插入关键字k void B_Tree_Insert(B_Tree *T, int k) { node *r = T->root; //若根结点已满 if(r->n == 2*t-1) { //申请一个新的结点 node *s = new node; //将的结点作为根结点 T->root = s; s->leaf = false; s->n = 0; s->child[1] = r; //将原根结点分裂为两个结点，分别作为s的第0个孩子和第1个孩子 B_Tree_Split_Child(s, 1, r); //把关键字k插入到根结点中，此时根结点一定不满 B_Tree_Insert_Nonfull(s, k); } //若根结点不满 else //直接把关键字插入到根结点中 B_Tree_Insert_Nonfull(r, k); } int main() { //生成一棵B树 B_Tree *T = new B_Tree; B_Tree_Create(T); //依次插入关键字 int i; for(i = 1; i <= 100; i++) { B_Tree_Insert(T, i); cout<<i<<' '<<cnt<<' '<<endl; } return 0; } ~~~ 18.2-5 见[算法导论-18.2-5-B树叶结点无指针](http://blog.csdn.net/mishifangxiangdefeng/article/details/7945167) 18.2-7 一棵具有n个结点且度为t的B树，可计算其高度h（P266定理18.1）。对一棵B树的操作时间T=读取磁盘页的时间*读取磁盘页的次数。根据代码可知，读取磁盘页的次数=B树的高度。 T = （a+bt）*h，代入a,b,h，求T的最大值 ### 18.3从B树中删除关键字 18.3-2 木有伪代码，直接上代码 # 四、思考题 ### 18-1辅存上的栈 a)2n次，O(mn) 假设一直是PUSH，且页面字数接近于m b)2(n/m)次,O((n/m)*m) 每连续个字m个字处理一次，共处理n/m次。每次处理包括存一次（m个字），取一次（0个字） c)2n次,O(mn) 最坏情况下，当页面满时PUSH，当页面只有一个字是POP，其中： PUSH操作：存一次（m个字），取一次（0个字） POP操作：存一次（0个字），取一次（m个字） d)待解决 ### 18-2连接与分裂2-3-4树 见[算法导论-18-2-连接与分裂2-3-4树](http://blog.csdn.net/mishifangxiangdefeng/article/details/7957517) 关于2楼问题的解答： ~~~ //删除T树中关键字为k的结点，由于是递归方法，当前处理的是x结点 void B_Tree::B_Tree_Delete2(node *x, char k) { int i, j; //找到x中第一个不小于k的关键字，即待处理的位置 for(i = 1; i <= x->n; i++) if(x->key[i] >= k) break; //y是关键字k之前的结点,即小于k的最大孩子 //z是关键字k之后的结点,即大于k的最小孩子 node *y = x->child[i], *z = x->child[i+1], *d; //若关键字k在结点x中的第i个位置 if(x->key[i] == k && i <= x->n) { //1)y是叶子结点，则直接从x中删除k if(x->leaf == true) { //关键字依次前移 for(j = i; j < x->n; j++) x->key[j] = x->key[j+1]; //关键字数-1 x->n--; return; } //2)x是内结点 //2-a：x中前于k的子结点y包含至少t个关键字 if(y->n >= t) { //找出k在以y为根的子树中的前驱d d = y; while(d->leaf == false) d = d->child[d->n+1]; //用d取代k x->key[i] = d->key[d->n]; //递归地删除d B_Tree_Delete2(y, d->key[d->n]); } //2-b：x是位于k之后的子结点z包含至少t个关键字 else if(z->n >= t) { //找出k在以z为根的子树中的后继d d = z; while(d->leaf == false) d = d->child[1]; //用d取代k x->key[i] = d->key[1]; //递归地删除d B_Tree_Delete2(z, d->key[1]); } //2-c：y和z都只有t-1个关键字，将k和z中所有关键字合并进y，使得x失去k和指向z的指针 else { //将z并入y中，y是x的第i个孩子 B_Tree_Merge(x, y, z, i); //将k从y中递归删除 B_Tree_Delete2(y, k); } } //3)关键字不在结点x中，则必定包含k的正确的子树的根x->child[i] else { //x是叶子结点,找到根结点都没有找到k，则k不在树中 if(x->leaf == true) { cout<<"error:not exist"<<endl; return; } //x是内结点 //3-a:child[i]中只有t-1个关键字 if(y->n == t-1) { //它的相邻兄弟x->child[i+1](用z表示)包含至少t个关键字 if(i <= x->n && i <= x->n && z->n >= t) { //将x中的关键字下降至y y->n++; y->key[y->n] = x->key[i]; //将z的某一关键字上升至x x->key[i] = z->key[1]; for(j = 1; j < z->n; j++) z->key[j] = z->key[j+1]; //将z适合的子女指针移到y 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的关键字数-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) { //将z并入y中，y是x的第i个孩子 B_Tree_Merge(x, y, z, i); //将k从y中递归删除 B_Tree_Delete2(y, k); } //与前面一个结点合并 else { //将y并入z中，z是x的第i-1个孩子 B_Tree_Merge(x, z, y, i-1); //将k从z中递归删除 B_Tree_Delete2(z, k); } } } //递归执行删除操作 B_Tree_Delete2(y, k); } } //left是parent的第pos个孩子，right是parent的第pos+1个孩子，把parent->key[pos]和right都合并到left中 void B_Tree::B_Tree_Merge(node *parent, node *left, node *right, int pos) { int j; //将k关键字合并进left left->key[left->n+1] = parent->key[pos]; //将right中所有关键字合并进left for(j = 1; j <= right->n; j++) left->key[left->n+j+1] = right->key[j]; //如果有孩子，孩子也要合并 if(left->leaf == false) { //使得parent指向z的指针 for(j = 1; j <= right->n+1; j++) left->child[left->n+j+1] = right->child[j]; } //left包含2t-1个关键字 left->n = left->n + 1 + right->n; //使得parent失去k for(j = pos; j < parent->n; j++) parent->key[j] = parent->key[j+1]; //使parent失去指向right的指针 for(j = pos+1; j <= parent->n; j++) parent->child[j] = parent->child[j+1]; parent->n--; //如果x是根结点，x if(parent->n == 0 && root == parent) root = left; //释放z delete right; } ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~