六、查找

六、查找

1. 静态查找表

静态查找表在查找过程中不改变表中数据——不插不删，故采用顺序存储结构。它适用于数据不变动或不常变动的表。根据静态查找表中数据是否按关键字有序，又可分为顺序查找（无序）和折半查找（有序）。

实现：

//静态查找表类
template<typename D>class SqTable
{//带模板的静态查找表类
protected:
  D *elem;  //存储基址，0 好单元留空
  int length;
public:
  SqTable()
  {//构造函数
    elem = NULL;
    length = 0;
  }
  ~SqTable()
  {//析构函数
    if (elem != NULL)
      delete[] elem;
  }
  void CreateSeqFromFile(char* FileName)
  {//由数据文件构造静态查找表
    ifstream fin(FileName);
    fin >> length;
    elem = new D[length + 1];
    assert(elem != NULL);
    for(int i = 1; i <= length; i++)
      InputFromFile(fin, elem[i]);
    fin.close();
  }
  void OutputToFile(char* FileName)const
  {//向数据文件输出静态查找表中的所有数据元素
    ofstream fout(FileName);
    if (elem != NULL)
      for(int i = 1; i <= length; i++)
        OutputToFile(fout, elem[i]);
    fout.close();
  }
  int SearchSeq(KeyType k)const
  {//在无序的静态查找表中顺序查找主关键字等于k的数据元素，若找到返回位置，否则返回0
    int i;
    elem[0].key = k;
    for(i = length; !EQ(k, elem[i].key); i--)
    return i;  //找不到时，i 为 0
  }
  int SearchBin(KeyType k)const
  {//在有序的静态查找表中折半查找主关键字等于k的数据元素，若找到返回位置，否则返回0
    int mid, low = 1, high = length;
    while(low <= high)
    {
      mid = (low + high) / 2;
      if EQ(k, elem[mid].key)
        return mid;
      else if LT(k, elem[mid].key)  //小于
        high = mid - 1;
      else  //大于
        low = mid + 1;
    }
    return 0;  //表中不存在返回 0
  }
  bool GetElem(int i, D &e)const
  {//用 e 返回静态查找表中第 i 个元素的值
    if (i < 1 || i > length)
      return false;
    e = elem[i];
    return true;
  }
  void Traverse(void(*visit) (D*))const
  {//按顺序遍历
    for(int i = 1; i <= length; i++)
      visit(&elem[i]);
  }
};

折半查找在大数据量时很有效。利用 STL 可以对无序数据进行查找。

2. 静态树表

如果有序数据的查找概率已知且差别很大，则折半查找并不是最佳的。这种情况可采用静态树表算法：把有序的静态查找表根据被查找的概率生成一棵二叉树，使查找二叉树每个结点的左右子树的概率尽量相等，以此缩短平均查找长度。这棵二叉树称为 “次优查找树” ，可以证明它不是最优的，但是近似最优。

实现：

//结点数据结构
struct S
{
  KeyType key;  //关键字
  int weight;  //权值
  int sw;  //累计权值
};

//静态树表类
template<typename D>class SOSTree: public SqTable<D>
{//带模板并继承 SqTable<D> 的静态树表类
private:
  void FindSW()
  {//按照有序表中各数据元素的 weight 域累计权值 sw
    if (length > 0)
    {
      elem[0].sw = 0;  //置边界值
      cout << endl << "sw = 0  " ;
      for(int i = 1; i <= length; i++)
      {
        elem[i].sw = elem[i - 1].sw + elem[i].weight;
        cout << setw(6) << elem[i].sw;
      }
    }
  }
  void SecondOptimal(BiTNode<D>* &p, int low, int high)
  {//由有序表递归构造次优查找树 p
    int j, i = low;
    int dw = elem[high].sw + elem[low - 1].sw;
    int min = abs(elem[high].sw - elem[low].sw);
    for(j = low + 1; j <= length; ++j)
      if (abs(dw - elem[j].sw - elem[j-1].sw) < min)
      {
        i = j;
        min = abs(dw - elem[j].sw - elem[j-1].sw);
      }
    p = new BiTNode<D>;
    assert(p != NULL);
    p->data = elem[i];
    if (i ==low)  
      p->lchild = NULL;
    else
      SecondOptimal(p->rchild, low, i-1);
    if (i == high)
      p->rchild = NULL;
    else
      SecondOptimal(p->lchild, i+1, high);
  }
public:
  BiTNode<D> t;  //采用二叉链表结构的二叉树 t 作为次优查找树
  void CreateSOSTree()
  {//由有序表构造次优查找树 t 
    if (length > 0)
    {
      FindSW();
      SecondOptimal(t.root, 1, length);
    }
  }
  BiTNode<D>* SearchSOSTree(KeyType k)const
  {//查找关键字等于 k 的元素，返回其指针，否则返回空指针
    BiTNode<D>* p = t.root;
    while(p != NULL)
    {
      if EQ(k, p->data.key)
        return p;
      else if LT(k, p->data.key)
        p = p->lchild;
      else
        p = p->rchild;
    }
    return NULL;
  }
};

3. 哈希表的插入、删除及查找

哈希表也称 “散列表” ，它是通过计算求得关键字的哈希地址的。如果哈希地址冲突小，在数据量大的情况下查找效率是很高的。

实现：

//开地址法哈希表
const int SUCCESS = 1;  //成功
const int UNSUCCESS = 0;  //不成功
const int DUPLICATE = -1;  //副本
const int N = 4;  //hashsize[] 的容量
int hashsize[N] = {11, 19, 37, 73};  //哈希表容量递增表，一个合适的素数序列

template<typename D>class HashTable;
{//带模板的开地址法哈希表类
private:
  D *elem;  //存储基址
  int count, length;
  int sizeindex;  //当前容量
  int *rando;  //随机数数组指针
  int Hash(KeyType key)
  {//一个简单的哈希函数
    return key % length;
  }
  int Hash2(KeyType key)
  {//双散列探查法的第二个哈希函数
    return key % (length-2);
  }
  void Random()
  {//建立伪随机数组（用于随机探查法）
    bool *ra = new bool[length];  //[0] 不用
    rando = new int[length];  //[0] 不用
    int i;
    for(i = 1; i < length; i++)  //设置 ra[i] 初值
      ra[i] = false;  //i 不再随机数数组的标志
//  srand(time(0));  //设置随机数种子
    for(i = 1; i < length; i++)  //依次给 rando[i] 赋随机值
    {
      do
      {
        rando[i] = rand() % (length - 1) + 1;  //给rando[i]赋值(1 ~ length-1)
        if (!ra[rando[i]])  //伪随机数数组中没有此数
          ra[rando[i]] = true;  //赋值成功
        else
          rando[i] = 0;  //赋值失败
      }while(rando[i] == 0);  //赋值失败则重新赋值
      cout << "rando[" << i << "] = " << rando[i] << endl;
    }
    delete[] ra;
  }
  int d(int i, KeyType key)  
  {//返回第 i 次冲突的增量
    switch(type)
    {
    case 0: return i;  //线性探查法（1, 2, 3, ...）
    case 1: return ((i+1) / 2) * ((i+1) / 2) * (int)pow(-1, i-1);
            //二次探查法（1, -1, 4, -4, 9, -9, ...）
    case 2: return i * Hash2(key);  //双散列探查法
    case 3: return rando[i];  //随机探查法
    default: return i;  //默认线性探查法
    }
  }
  void collision(KeyType key, int &p, int i)
  {//开地址法求得关键字为 key 的第 i 次冲突的地址 p
    p = (Hash(key) + d(i, key)) % length;  //哈希函数加增量后在求余
    if (p < 0)  //求余得到负数（二次探查可能会出现）
      p = p + length;  //保证 p 为非负数
  }
  void RecreateHashTable()
  {//重建哈希表
    int i, len = length;
    D *p = elem;
    sizeindex++;  //增大存储容量为下一个序列数
    if (sizeindex < N)
    {
      length = hashsize[sizeindex];
      elem = new D[length];
      assert(elem != NULL);
      for(i = 0; i < length; i++)
        elem[i].key = EMPTY;  //未填数据的标志
      for(i = 0; i < len; i++)
        if (p[i].key != EMPTY && p[i].key != TOMB)  //在原哈希表[i]有数据
          InsertHash(p[i]);
      delete[] p;
      if (type == 3)
        Random();
    }
  }
public:
  int type;  //探查法类型
  HashTable()
  {//构造函数，构造一个空的哈希表
    count = 0;  //当前数据元素个数
    sizeindex = 0;  //初始存储容量
    length = hashsize[sizeindex];  //当前哈希表容量
    elem = new D[length];  
    assert(elem != NULL);
    for(int i = 0; i < length; i++)
      elem[i].key = EMPTY;
    cout << "请输入探查法类型（0：线性；1：二次；2：双散列；3：随机）：" ;
    cin >> type;
    if (type == 3)
      Random();
    else
      Random = NULL;
  }
  ~HashTable()
  {//析构函数，销毁哈希表
    if (elem != NULL)
      delete[] elem;
    if (type == 3)
      delete[] rando;
  }
  bool SearchHash(KeyType key, int &p, int &c)
  {//在开放定址哈希表中查找关键字为key的元素，以 p 指示待查元素位置，并返回SUCCESS
   //否则以 p 指示插入位置，并返回UNSUCCESS，用 c 记冲突次数，供建表插入时参考
    int c1, tomb = -1;
    p = Hash(key);
    while(elem[p].key == TOMB || elem[p].key != EMPTY && !EQ(key,elem[p].key))
    {//该位置元素已被删除或该位置中填有数据，并且与待查找的关键字不相等
      if (elem[p].key == TOMB && tomb == -1)
      {
        tomb = p;
        c1 = c;
      }
      c++;
      if (c <= hashsize[sizeindex] / 2)
        collision(key, p, c);
      else
        break;
    }
    if EQ(key, elem[p].key)
      return true;
    else
    {
      if (tomb != -1)
      {
        p = tomb;
        c = c1;
      }
      return false;
    }
  }
  int InsertHash(D e)
  {//查找不成功时将数据元素 e 插入到开放定址哈希表中，并返回SUCCESS；查找成功时返回
   //DUPLICATE，不插入元素；若冲突次数过大，则不插入，并重建哈希表，返回UNSUCCESS
    int p, c = 0;
    if (SearchHash(e.key, p, c))
      return DUPLICATE;
    else if (c < hashsize[sizeindex] / 2)
    {
      elem[p] = e;
      ++count;
      return SUCCESS;
    }
    else
    {
      cout << "按哈希地址的顺序遍历重建前的哈希表：" << endl;
      TraverseHash(visit);
      cout << "重建哈希表" << endl;
      RecreateHashTable();
      return UNSUCCESS;
    }
  }
  bool DeleteHash(KeyType key, D &e)
  {//删除关键字等于key的元素，成功返回true，并将该位置关键字设为TOMB；否则返回false
    int p, c;
    if (SearchHash(key, p, c))
    {
      e = elem[p];
      elem[p].key = TOMB;
      --count;
      return true;
    }
    elem
      return false;
  }
  D GetElem(int i)const
  {//返回元素[i]的值
    return elem[i];
  }
  void TraverseHash(void(*visit) (int, D*))const
  {//按哈希地址的顺序遍历哈希表
    int i;
    cout << "哈希地址 0 ~ " << length - 1 << endl;
    for(i = 0; i < length; i++)
      if (elem[i].key != EMPTY && elem[i].key != TOMB)
        visit(i, &elem[i]);
  }
};

增加了哈希表的删除算法，就要考虑删除数据给插入和查找带来的影响。设置被删除结点的关键字为 TOMB ，在查找过程中找到 TOMB ，并不说明要查找的关键字不存在，还要继续往后查找，否则不能确定哈希表中不存在该关键字；在插入过程中找到 TOMB ，要记下该位置，以便最后将数据插入到此处。

4. 动态查找表

动态查找表在查找过程中可改变表中数据，即可插入或删除数据，故一般采用链式存储结构。它适用于数据经常变动的表。之前介绍的二叉排序树、平衡二叉树、伸展树及红黑树都是动态查找表。

4.1 B 树

B 树是平衡的 m 路查找树， “B” 表示平衡。

平衡二叉树的查找效率很高，但在数据量非常大，以至于内存空间不够容纳平衡二叉树所有结点的情况下，就得另辟蹊径。B 树是解决这个问题的一种很好的结构。

实现：

//B 树的 3 种模板结构
template<typename D>struct Record
{//B 树数据结构
  KeyType key;
  D others;
};

template<typename D>struct BTNode
{//B 树结点结构
  int keynum;  //关键字个数
  BTNode<D> *parent;
  BTNode<D> *children[m + 1];
  KeyType key[m + 1];  //关键字数组，[0] 未用
  Record<D> *recptr[m + 1];  //数据指针数组，[0] 未用
};

template<typename D>struct Result
{//查找结构结构
  BTNode<D> *pt;  //指向关键字所在的 B 树结点
  int i;  //i = 0 - m - 1 ，在 B 树结点中的关键字序号
  bool tag;  //true：查找成功；false：查找失败
};

B 树的结点结构和前面介绍过的结点结构有一个重要的区别：它不是把整个数据都存放在结点中，而是仅在结点中存放数据的关键字和数据的地址两项。而在结点查找到关键字后，再根据其地址找到数据。当数据所占的存储空间非常大时，这样做的好处是减小了结点所占用的存储空间，也减小了整个 B 树占用的存储空间。

B 树是 m 路查找树，它的每个结点最多可以有 m-1 个关键字，m 棵子树（m = 2 时即为二叉树，有一个关键字，两颗子树）。子树总比关键字的数量多 1 ,故 key[0] 和 recptr[0] 单元不用，而 children[0] 要用。[m] 单元在正常情况下是不用的，只是在结点的 keynum = m-1 ，又向该结点插入关键字时，临时占用 [m] 单元。然后就要把该结点尽量平均地分裂成两个结点。

实现：

//B 树类
template<typename D>class BTree
{//带模板的 B 树类
private:
  BTNode<D> *root;
  int s;  //s 为分裂结点的中值，与 B 树的阶 m 有关
  int MinEmpt;  //存 record[] 中具有最小序号的空位置
  Record<D> record[N];  //存放数据的数组
  void DestroyBTree(BTNode<D>* t)
  {//递归销毁 t 为根的 B 树
    if (t != NULL)
    {
      for(int i = 0; i <= t->keynum; i++)
        DestroyBTree(t->children[i]);
      delete t;
      t = NULL;
    }
  }
  int Search(BTNode<D>* p, KeyType k)const
  {//在 p->key[1 - keynum] 中顺序查找 i 使得 p->key[i] <= k <= p->key[i + 1]
    int i = 0, j;
    for(int j = 1; j <= p->keynum; j++)
      if LQ(p->key[j], k)
        i = j;
      else
        break;
      retun i;
  }
  void MoveItim2(BTNode<D>* p, int i, BTNode<D>* q, int j)
  {//将结点 q[j] 中的 key 和 recptr  2项移动到结点 p[i]
    p->key[i] = q->key[j]; 
    p->recptr[i] = q->recptr[j];
  }
  void MoveItim3(BTNode<D>* p, int i, BTNode<D>* q, int j)
  {//将结点 q[j] 中的 3 项移动到结点 p[i]
    p->key[i] = q->key[j]; 
    p->recptr[i] = q->recptr[j];
    p->children[i] = q->children[j];
  }
  void Copy(BTNode<D>* q, int i, Record<D>* r)
  {//将数据地址 r 和关键字 r->key 分别赋给 q->recptr[i] 和 q->key[i]
    q->key[i] = r->key;
    q->recptr[i] = r;
  }
  void Insert(BTNode<D>* q, int i, Record<D>* r, BTNode<D>* ap)
  {//将数据地址 r 和 r->key 分别赋给 q->recptr[i+1] 和 q->key[i+1]
   //q->children[i+1] 指向结点 *ap 
    for(int j = q->keynum; j > i; j--)  //空出 *q[i+1]
      MoveItim3(q, j+1, q, j);
    Copy(q, i+1, r);
    q->children[i + 1] = ap;
    if (ap != NULL)
      ap->parent = q;
    q->keynum++;
  }
  void split(BTNode<D>* q, BTNode<D>* &ap)
  {//将结点 *q 分裂成两个结点，前一半保留在 *q ，后一半移入新生结点 *ap
    ap = new BTNode<D>;
    ap->children[0] = q->children[s];  //结点 *q 的后一半移入结点 *ap
    if (ap->children[0] != NULL)
      ap->children[0]->parent = ap;
    for(int i = s+1; i <= m; i++)
    {
      MoveItim3(ap, i-s, q, i);
      if (ap->children[i-s] != NULL)
        ap->children[i-s]->parent = ap;
    }
    ap->keynum = m - s;
    q->keynum = s - 1;  //前一半保留，修改 *q 的关键字个数
  }
  void NewRoot(Record<D>* r, BTNode<D>* ap)
  {//生成含信息（r, ap）的新的根结点，原根结点 root 和 ap 为其子树指针
    BTNode<D> *p = new BTNode<D>;
    p->parent = NULL;
    p->keynum = 1;
    Copy(p, 1, r);
    p->children[0] = root;
    if (root != NULL)
      root->parent = p;
    p->children[1] = ap;
    if (ap != NULL)
      ap->parent = p;
    root = p;
  }
  void InsertBTree(Record<D>* r, BTNode<D>* q, int i)
  {//在结点 *q 的 key[i] 与 key[i+1] 之间插入关键字 r->k 和地址 r 
   //若引起结点过大，则沿双亲链进行必要的结点分裂，使得仍是 B 树
    BTNode<D> *ap = NULL;
    bool finished = false;
    while(q && !finished)
    {
      Insert(q, i, r, ap);
      if (q->keynum)  //关键字未超出容量
        finished = true;
      else  //超出容量，分裂结点 *q
      {
        r = q->recptr[s];
        split(q, ap);
        q = q->parent;
        if (q != NULL)
          i = Search(q, r->key);
      }
    }
    if (!finished)  //是空树或根结点已分裂为结点 *q 和 *ap
      NewRoot(r, ap);
  }
  bool Move(BTNode<D>* &p)
  {//p 指向删除关键字后关键字的个数不足的结点，如果其左或右兄弟有多余的关键字，
   //则移给 p ，返回 true ；否则返回 false
    BTNode<D> *a, *f = p->parent;
    int i, j;
    for(i = 0; f->children[i] != p; i++)
    if (i > 0 && f->children[i-1]->keynum > (m-1)/2)
    {//情况一：有左兄弟且其有多个关键字
      a = f->children[i-1];
      for(j = p->keynum; j > 0; j--)
        MoveItim3(p, j+1, p, j);
      p->children[1] = p->children[0];
      MoveItim2(p, 1, f, i);
      p->keynum++;
      MoveItim2(f, i, a, a->keynum);
      p->children[0] = a->children[a->keynum];
      if (a->children[a->keynum] != NULL)
        a->children[a->keynum]->parent = p;
      a->keynum--;
      return true;
    }
    else if (i < f->keynum && f->children[i+1]->keynum > (m-1)/2)
    {//情况二：有右兄弟且其关键字数目大于 (m-1)/2
      a = f->children[i+1];
      MoveItim2(p, p->keynum+1, f, i+1);
      MoveItim2(f, i+1, a, 1);
      p->children[p->keynum + 1] = a->children[0];
      p->keynum++;
      if (a->children[0] != NULL)
        a->children[0]->parent = p;
      for(int j = 1; j < a->keynum; j++)
      {
        MoveItim2(a, j, a, j+1);
        a->children[j-1] = a->children[j]; 
      }
      a->children[a->keynum - 1] = a->children[a->keynum];
      a->keynum--;
      return true;
    }
    return false;
  }
  BTNode<D>* Merge(BTNode<D>* &p)
  {//合并结点
    BTNode<D> *b, *f = p->parent;
    int i, j;
    for(i = 0; f->children[i] != p; i++)
    if (i > 0)
    {//*p 有左邻兄弟
      b = f->children[i-1];
      for(j = 0; j <= p->keynum; j++)
        if (p->children[j] != NULL)
          p->children[j]->parent = b;
      ++b->keynum;
      MoveItim2(b, b->keynum, f, i);
      b->children[b->keynum] = p->children[0];
      for(j = 1; j <= p->keynum; j++)
      {
        ++b->keynum;
        MoveItim3(b, b->keynum, p, j);
      }
      delete p;
      for(j = i+1; j <= f->keynum; j++)
        MoveItim3(f, j-1, f, j);
      f->keynum--;
    }
    else
    {//这样 b 还是 p 的左兄弟，合并到左兄弟，则是在左兄弟后面加关键字
      b = p;
      p = f->children[i+1];
      for(j = 0; j <= p->keynum; j++)
        if (p->children[j] != NULL)
          p->children[j]->parent = b;
      ++b->keynum;
      MoveItim2(b, b->keynum, f, i+1);
      b->children[b->keynum] = p->children[0];
      for(j = 1; j <= p->keynum; j++)
      {
        ++b->keynum;
        MoveItim3(b, b->keynum, p ,j);
      }
      delete p;
      for(j = i+1; j < f->keynum; j++)
      MoveItim3(f, j, f, j+1);
      f->keynum--;
    }
    return b;
  }
public:
  BTree()
  {//构造函数
    root = NULL;
    for(int i = 0; i < N; i++)
      record[i].key = EMPTY;
    MinEmpt = 0;
    s = (m+1) / 2;
  }
  ~BTree()
  {//析构函数
    DestroyBTree(root);
  }
  BTNode<D>* Root()const
  {//返回 B 树根结点指针
    return root;
  }
  void TraverseBTree(BTNode<D>* t, void(*visit) (Record<D>))const
  {//按关键字顺序遍历
    if (t != NULL)
      for(int i = 0; i <= t->keynum; i++)
      {
        if (i > 0)
          visit(*(t->recptr[i]));
        if (t->children[i] != NULL)
          TraverseBTree(t->children[i], visit);
      }  
  }
  Rusult<D> SearchBTree(KeyType k)const
  {//在 B 树中查找关键字 k ，返回结果（pt, i, tag），若成功，则 tag = true
   //pt 所指结点的第 i 个关键字等于 k ，否则 tag = false，等于 k 的关键字应
   //插在 pt 所指结点的第 i 和第 i+1 个关键字之间
    BTNode<D> *p = root, *q = NULL;
    bool found = false;
    int i = 0;
    Result<D> r;
    while(p != NULL && !found)
    {
      i = Search(p, k);
      if (i > 0 && p->key[i] == k)
        found = true;
      else
      {
        q = p;
        p = p->children[i];
      }
    }
    if (found)
    {
      r.pt = p;
      r.tag = true;
    }
    else
    {
      r.pt = q;
      r.tag = false;
    }
    r.i = i;
    return r;
  }
  bool InsertRecord(Record<D> re)
  {//B 树中不存在 re.key ，且 record[] 中有空位置，将数据 re 插入到 record[] 和 
   //B 树中，成功返回 true，否则返回 false
    Result<D> u = SearchBTree(re.key);
    if (u.tag)
      return false;
    if (MinEmpt < N)
    {
      record[MinEmpt] = re;
      InsertBTree(&record[MinEmpt], u.pt, u.i);
      for(int k = MinEmpt+1; k < N; k++)
        if (record[k].key == EMPTY)
        {
          MinEmpt = k;
          break;
        }
      if (k == N)
        MinEmpt = N;
      return true;
    }
    else
      return false;
  }
  bool DeleteBTree(Record<D> &re, KeyType k)
  {//在 B 树中删除关键字为 k 的数据，用 re 返回该数据
    int i, j;
    BTNode<D> *p, *q;
    Result<D> u = SearchBTree(k);
    if (u.tag == 0)
      return false;
    i = u.i;
    p = u.pt;
    re = *(p->recptr[i]);
    p->recptr[i]->key = EMPTY;
    if (p->recptr[i] - record < MinEmpt)
      MinEmpt = p->recptr[i] - record;
    if (p->children[i-1] != NULL)
    {
      q = p->children[i-1];
      while(q->children[q->keynum] != NULL)
        q = q->children[q->keynum];
      if (q->keynum > (m-1)/2)
      {
        MoveItim2(p, i, q, q->keynum);
        p = q;
        i = q->keynum;
      }
      else
      {
        q = p->children[i];
        while(q->children[0] != NULL)
          q = q->children[0];
        MoveItim2(p, i, q, 1);
        p = q;
        i = 0;
      }
    }
    for(j = i+1; j <= p->keynum; j++)
      MoveItim2(p, j-1, p, j);
    p->keynum--;
    while(p->keynum < (m-1)/2 && (p != root))
    {
      if (!Move(p))
        p = Merge(p);
      p = p->parent;
    }
    if (p == root && root->keynum == 0)
    {
      root = root->children[0];
      if (root != NULL)
        root->parent = NULL;
      delete p;
    }
    return true;
  }
};

与二叉排序树和平衡二叉树一样， B 树中每个关键字是唯一的。所以在插入数据时，先要查找 B 树中是否存在该关键字。如果存在，则不能插入。新数据总是要插在最底层的非叶子结点中，这就保证了所有叶子结点都出现在同一层次。当结点的关键字由于插入超出了最大限度，就要进行分裂。一个结点分成 3 部分，中间关键字并入原来的父结点中，左右两部分分别是中间关键字的左右孩子。如果原来的父结点由于中间关键字的并入超出了最大限度，则继续分裂，直至生成新的根结点。

在 B 树删除关键字，如果在最底层的非叶子结点，则直接删除；否则，类似于二叉排序树和平衡二叉树，删除其前驱或后继关键字（它们一定在最底层的非叶子结点中），再将其前驱或后继关键字和指针复制到删除的关键字和指针处。删除关键字导致结点的关键字少于最低限度，就要进行合并。如果合并导致父结点的关键字少于最低限度，则继续合并，直至根结点中没有关键字。这时删除根结点，B 树的层数减 1 。

B 树是用于处理大数据量的查找操作。其中数据量大到不能存放在内存数组 record[] 中，要将数据存放在外存的多个文件中。甚至内存也放不下整个 B 树，内存中只能存放 B 树的一个结点。所以，B 树的每个结点都存于外存的文件中，结点中的指针内容是文件名和偏移量（数据在文件中的位置）。查找过程是首先将 B 树的根结点文件放入内存中，依据关键字进行查找。随时关闭查找过的 B 树结点，再在内存中随时打开新的 B 树结点，直至查找结束。为了提高速度，就要尽量减少打开、关闭文件的次数，并尽量增大 B 树每个结点可容纳的关键字数，从而降低 B 树的层数。

由于真正的 B 树每个结点的关键字非常多，即 keynum 很大，Search() 函数在 1 ~ keynum 中查找 i 应采用折半查找法而不是顺序查找法。

4.2 键树

键树用于关键字为字符串的情况，故键树也称为 “词典查找树” 。可以用孩子-兄弟二叉链表表示键树，称为 “双链键树” ；也可以用树的多重链表示键树，称为 “Trie 树” 。

推荐阅读：
查找算法（V）键树——双链树和Trie树
键树 B树 B+树（注意，该文中有些许错误，请注意甄别）