Question

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

18.1-4

2^(2t)-1

18.1-5

没看懂题目

18.2 对 B 树的基本操作

18.2-1

18.2-2

待解决

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 树叶结点无指针

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

木有伪代码，直接上代码