Question

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 树

关于 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;
}