六、查找

1. 靜態(tài)查找表

靜態(tài)查找表在查找過程中不改變表中數(shù)據(jù)——不插不刪抚恒，故采用順序存儲(chǔ)結(jié)構(gòu)塔橡。它適用于數(shù)據(jù)不變動(dòng)或不常變動(dòng)的表惕味。根據(jù)靜態(tài)查找表中數(shù)據(jù)是否按關(guān)鍵字有序扇调，又可分為順序查找（無序）和折半查找（有序）。

實(shí)現(xiàn)：

//靜態(tài)查找表類
template<typename D>class SqTable
{//帶模板的靜態(tài)查找表類
protected:
  D *elem;  //存儲(chǔ)基址在讶，0 好單元留空
  int length;
public:
  SqTable()
  {//構(gòu)造函數(shù)
    elem = NULL;
    length = 0;
  }
  ~SqTable()
  {//析構(gòu)函數(shù)
    if (elem != NULL)
      delete[] elem;
  }
  void CreateSeqFromFile(char* FileName)
  {//由數(shù)據(jù)文件構(gòu)造靜態(tài)查找表
    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
  {//向數(shù)據(jù)文件輸出靜態(tài)查找表中的所有數(shù)據(jù)元素
    ofstream fout(FileName);
    if (elem != NULL)
      for(int i = 1; i <= length; i++)
        OutputToFile(fout, elem[i]);
    fout.close();
  }
  int SearchSeq(KeyType k)const
  {//在無序的靜態(tài)查找表中順序查找主關(guān)鍵字等于k的數(shù)據(jù)元素煞抬，若找到返回位置，否則返回0
    int i;
    elem[0].key = k;
    for(i = length; !EQ(k, elem[i].key); i--)
    return i;  //找不到時(shí)构哺，i 為 0
  }
  int SearchBin(KeyType k)const
  {//在有序的靜態(tài)查找表中折半查找主關(guān)鍵字等于k的數(shù)據(jù)元素革答，若找到返回位置，否則返回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 返回靜態(tài)查找表中第 i 個(gè)元素的值
    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]);
  }
};

折半查找在大數(shù)據(jù)量時(shí)很有效曙强。利用 STL 可以對(duì)無序數(shù)據(jù)進(jìn)行查找蝗碎。

2. 靜態(tài)樹表

如果有序數(shù)據(jù)的查找概率已知且差別很大，則折半查找并不是最佳的旗扑。這種情況可采用靜態(tài)樹表算法：把有序的靜態(tài)查找表根據(jù)被查找的概率生成一棵二叉樹蹦骑，使查找二叉樹每個(gè)結(jié)點(diǎn)的左右子樹的概率盡量相等，以此縮短平均查找長(zhǎng)度臀防。這棵二叉樹稱為 “次優(yōu)查找樹” 眠菇，可以證明它不是最優(yōu)的，但是近似最優(yōu)袱衷。

實(shí)現(xiàn)：

//結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
struct S
{
  KeyType key;  //關(guān)鍵字
  int weight;  //權(quán)值
  int sw;  //累計(jì)權(quán)值
};

//靜態(tài)樹表類
template<typename D>class SOSTree: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的靜態(tài)樹表類
private:
  void FindSW()
  {//按照有序表中各數(shù)據(jù)元素的 weight 域累計(jì)權(quán)值 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)
  {//由有序表遞歸構(gòu)造次優(yōu)查找樹 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;  //采用二叉鏈表結(jié)構(gòu)的二叉樹 t 作為次優(yōu)查找樹
  void CreateSOSTree()
  {//由有序表構(gòu)造次優(yōu)查找樹 t 
    if (length > 0)
    {
      FindSW();
      SecondOptimal(t.root, 1, length);
    }
  }
  BiTNode<D>* SearchSOSTree(KeyType k)const
  {//查找關(guān)鍵字等于 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. 哈希表的插入致燥、刪除及查找

哈希表也稱 “散列表” 登疗，它是通過計(jì)算求得關(guān)鍵字的哈希地址的。如果哈希地址沖突小，在數(shù)據(jù)量大的情況下查找效率是很高的辐益。

實(shí)現(xiàn)：

//開地址法哈希表
const int SUCCESS = 1;  //成功
const int UNSUCCESS = 0;  //不成功
const int DUPLICATE = -1;  //副本
const int N = 4;  //hashsize[] 的容量
int hashsize[N] = {11, 19, 37, 73};  //哈希表容量遞增表断傲，一個(gè)合適的素?cái)?shù)序列

template<typename D>class HashTable;
{//帶模板的開地址法哈希表類
private:
  D *elem;  //存儲(chǔ)基址
  int count, length;
  int sizeindex;  //當(dāng)前容量
  int *rando;  //隨機(jī)數(shù)數(shù)組指針
  int Hash(KeyType key)
  {//一個(gè)簡(jiǎn)單的哈希函數(shù)
    return key % length;
  }
  int Hash2(KeyType key)
  {//雙散列探查法的第二個(gè)哈希函數(shù)
    return key % (length-2);
  }
  void Random()
  {//建立偽隨機(jī)數(shù)組（用于隨機(jī)探查法）
    bool *ra = new bool[length];  //[0] 不用
    rando = new int[length];  //[0] 不用
    int i;
    for(i = 1; i < length; i++)  //設(shè)置 ra[i] 初值
      ra[i] = false;  //i 不再隨機(jī)數(shù)數(shù)組的標(biāo)志
//  srand(time(0));  //設(shè)置隨機(jī)數(shù)種子
    for(i = 1; i < length; i++)  //依次給 rando[i] 賦隨機(jī)值
    {
      do
      {
        rando[i] = rand() % (length - 1) + 1;  //給rando[i]賦值(1 ~ length-1)
        if (!ra[rando[i]])  //偽隨機(jī)數(shù)數(shù)組中沒有此數(shù)
          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];  //隨機(jī)探查法
    default: return i;  //默認(rèn)線性探查法
    }
  }
  void collision(KeyType key, int &p, int i)
  {//開地址法求得關(guān)鍵字為 key 的第 i 次沖突的地址 p
    p = (Hash(key) + d(i, key)) % length;  //哈希函數(shù)加增量后在求余
    if (p < 0)  //求余得到負(fù)數(shù)（二次探查可能會(huì)出現(xiàn)）
      p = p + length;  //保證 p 為非負(fù)數(shù)
  }
  void RecreateHashTable()
  {//重建哈希表
    int i, len = length;
    D *p = elem;
    sizeindex++;  //增大存儲(chǔ)容量為下一個(gè)序列數(shù)
    if (sizeindex < N)
    {
      length = hashsize[sizeindex];
      elem = new D[length];
      assert(elem != NULL);
      for(i = 0; i < length; i++)
        elem[i].key = EMPTY;  //未填數(shù)據(jù)的標(biāo)志
      for(i = 0; i < len; i++)
        if (p[i].key != EMPTY && p[i].key != TOMB)  //在原哈希表[i]有數(shù)據(jù)
          InsertHash(p[i]);
      delete[] p;
      if (type == 3)
        Random();
    }
  }
public:
  int type;  //探查法類型
  HashTable()
  {//構(gòu)造函數(shù)，構(gòu)造一個(gè)空的哈希表
    count = 0;  //當(dāng)前數(shù)據(jù)元素個(gè)數(shù)
    sizeindex = 0;  //初始存儲(chǔ)容量
    length = hashsize[sizeindex];  //當(dāng)前哈希表容量
    elem = new D[length];  
    assert(elem != NULL);
    for(int i = 0; i < length; i++)
      elem[i].key = EMPTY;
    cout << "請(qǐng)輸入探查法類型（0：線性智政；1：二次认罩；2：雙散列；3：隨機(jī)）：" ;
    cin >> type;
    if (type == 3)
      Random();
    else
      Random = NULL;
  }
  ~HashTable()
  {//析構(gòu)函數(shù)续捂，銷毀哈希表
    if (elem != NULL)
      delete[] elem;
    if (type == 3)
      delete[] rando;
  }
  bool SearchHash(KeyType key, int &p, int &c)
  {//在開放定址哈希表中查找關(guān)鍵字為key的元素垦垂，以 p 指示待查元素位置，并返回SUCCESS
   //否則以 p 指示插入位置牙瓢，并返回UNSUCCESS劫拗，用 c 記沖突次數(shù)，供建表插入時(shí)參考
    int c1, tomb = -1;
    p = Hash(key);
    while(elem[p].key == TOMB || elem[p].key != EMPTY && !EQ(key,elem[p].key))
    {//該位置元素已被刪除或該位置中填有數(shù)據(jù)矾克，并且與待查找的關(guān)鍵字不相等
      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)
  {//查找不成功時(shí)將數(shù)據(jù)元素 e 插入到開放定址哈希表中页慷，并返回SUCCESS；查找成功時(shí)返回
   //DUPLICATE聂渊，不插入元素；若沖突次數(shù)過大四瘫，則不插入汉嗽，并重建哈希表，返回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)
  {//刪除關(guān)鍵字等于key的元素找蜜，成功返回true饼暑，并將該位置關(guān)鍵字設(shè)為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]);
  }
};

增加了哈希表的刪除算法洗做，就要考慮刪除數(shù)據(jù)給插入和查找?guī)淼挠绊懝选ＴO(shè)置被刪除結(jié)點(diǎn)的關(guān)鍵字為 TOMB ，在查找過程中找到 TOMB 诚纸，并不說明要查找的關(guān)鍵字不存在撰筷，還要繼續(xù)往后查找，否則不能確定哈希表中不存在該關(guān)鍵字畦徘；在插入過程中找到 TOMB 毕籽，要記下該位置，以便最后將數(shù)據(jù)插入到此處井辆。

4. 動(dòng)態(tài)查找表

動(dòng)態(tài)查找表在查找過程中可改變表中數(shù)據(jù)关筒，即可插入或刪除數(shù)據(jù)，故一般采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)杯缺。它適用于數(shù)據(jù)經(jīng)常變動(dòng)的表蒸播。之前介紹的二叉排序樹、平衡二叉樹、伸展樹及紅黑樹都是動(dòng)態(tài)查找表袍榆。

4.1 B 樹

B 樹是平衡的 m 路查找樹胀屿， “B” 表示平衡。

平衡二叉樹的查找效率很高蜡塌，但在數(shù)據(jù)量非常大碉纳，以至于內(nèi)存空間不夠容納平衡二叉樹所有結(jié)點(diǎn)的情況下，就得另辟蹊徑馏艾。B 樹是解決這個(gè)問題的一種很好的結(jié)構(gòu)劳曹。

實(shí)現(xiàn)：

//B 樹的 3 種模板結(jié)構(gòu)
template<typename D>struct Record
{//B 樹數(shù)據(jù)結(jié)構(gòu)
  KeyType key;
  D others;
};

template<typename D>struct BTNode
{//B 樹結(jié)點(diǎn)結(jié)構(gòu)
  int keynum;  //關(guān)鍵字個(gè)數(shù)
  BTNode<D> *parent;
  BTNode<D> *children[m + 1];
  KeyType key[m + 1];  //關(guān)鍵字?jǐn)?shù)組，[0] 未用
  Record<D> *recptr[m + 1];  //數(shù)據(jù)指針數(shù)組琅摩，[0] 未用
};

template<typename D>struct Result
{//查找結(jié)構(gòu)結(jié)構(gòu)
  BTNode<D> *pt;  //指向關(guān)鍵字所在的 B 樹結(jié)點(diǎn)
  int i;  //i = 0 - m - 1 铁孵，在 B 樹結(jié)點(diǎn)中的關(guān)鍵字序號(hào)
  bool tag;  //true：查找成功；false：查找失敗
};

B 樹的結(jié)點(diǎn)結(jié)構(gòu)和前面介紹過的結(jié)點(diǎn)結(jié)構(gòu)有一個(gè)重要的區(qū)別：它不是把整個(gè)數(shù)據(jù)都存放在結(jié)點(diǎn)中房资，而是僅在結(jié)點(diǎn)中存放數(shù)據(jù)的關(guān)鍵字和數(shù)據(jù)的地址兩項(xiàng)蜕劝。而在結(jié)點(diǎn)查找到關(guān)鍵字后，再根據(jù)其地址找到數(shù)據(jù)轰异。當(dāng)數(shù)據(jù)所占的存儲(chǔ)空間非常大時(shí)岖沛，這樣做的好處是減小了結(jié)點(diǎn)所占用的存儲(chǔ)空間，也減小了整個(gè) B 樹占用的存儲(chǔ)空間搭独。

B 樹是 m 路查找樹婴削，它的每個(gè)結(jié)點(diǎn)最多可以有 m-1 個(gè)關(guān)鍵字，m 棵子樹（m = 2 時(shí)即為二叉樹牙肝，有一個(gè)關(guān)鍵字唉俗，兩顆子樹）。子樹總比關(guān)鍵字的數(shù)量多 1 ,故 key[0] 和 recptr[0] 單元不用配椭，而 children[0] 要用虫溜。[m] 單元在正常情況下是不用的，只是在結(jié)點(diǎn)的 keynum = m-1 股缸，又向該結(jié)點(diǎn)插入關(guān)鍵字時(shí)衡楞，臨時(shí)占用 [m] 單元。然后就要把該結(jié)點(diǎn)盡量平均地分裂成兩個(gè)結(jié)點(diǎn)敦姻。

實(shí)現(xiàn)：

//B 樹類
template<typename D>class BTree
{//帶模板的 B 樹類
private:
  BTNode<D> *root;
  int s;  //s 為分裂結(jié)點(diǎn)的中值寺酪，與 B 樹的階 m 有關(guān)
  int MinEmpt;  //存 record[] 中具有最小序號(hào)的空位置
  Record<D> record[N];  //存放數(shù)據(jù)的數(shù)組
  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)
  {//將結(jié)點(diǎn) q[j] 中的 key 和 recptr  2項(xiàng)移動(dòng)到結(jié)點(diǎn) 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)
  {//將結(jié)點(diǎn) q[j] 中的 3 項(xiàng)移動(dòng)到結(jié)點(diǎn) 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)
  {//將數(shù)據(jù)地址 r 和關(guān)鍵字 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)
  {//將數(shù)據(jù)地址 r 和 r->key 分別賦給 q->recptr[i+1] 和 q->key[i+1]
   //q->children[i+1] 指向結(jié)點(diǎn) *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)
  {//將結(jié)點(diǎn) *q 分裂成兩個(gè)結(jié)點(diǎn)，前一半保留在 *q 替劈，后一半移入新生結(jié)點(diǎn) *ap
    ap = new BTNode<D>;
    ap->children[0] = q->children[s];  //結(jié)點(diǎn) *q 的后一半移入結(jié)點(diǎn) *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 的關(guān)鍵字個(gè)數(shù)
  }
  void NewRoot(Record<D>* r, BTNode<D>* ap)
  {//生成含信息（r, ap）的新的根結(jié)點(diǎn)，原根結(jié)點(diǎn) 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)
  {//在結(jié)點(diǎn) *q 的 key[i] 與 key[i+1] 之間插入關(guān)鍵字 r->k 和地址 r 
   //若引起結(jié)點(diǎn)過大陨献，則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂盒犹，使得仍是 B 樹
    BTNode<D> *ap = NULL;
    bool finished = false;
    while(q && !finished)
    {
      Insert(q, i, r, ap);
      if (q->keynum)  //關(guān)鍵字未超出容量
        finished = true;
      else  //超出容量，分裂結(jié)點(diǎn) *q
      {
        r = q->recptr[s];
        split(q, ap);
        q = q->parent;
        if (q != NULL)
          i = Search(q, r->key);
      }
    }
    if (!finished)  //是空樹或根結(jié)點(diǎn)已分裂為結(jié)點(diǎn) *q 和 *ap
      NewRoot(r, ap);
  }
  bool Move(BTNode<D>* &p)
  {//p 指向刪除關(guān)鍵字后關(guān)鍵字的個(gè)數(shù)不足的結(jié)點(diǎn)，如果其左或右兄弟有多余的關(guān)鍵字急膀，
   //則移給 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)
    {//情況一：有左兄弟且其有多個(gè)關(guān)鍵字
      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)
    {//情況二：有右兄弟且其關(guān)鍵字?jǐn)?shù)目大于 (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)
  {//合并結(jié)點(diǎn)
    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 的左兄弟卓嫂，合并到左兄弟慷暂，則是在左兄弟后面加關(guān)鍵字
      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()
  {//構(gòu)造函數(shù)
    root = NULL;
    for(int i = 0; i < N; i++)
      record[i].key = EMPTY;
    MinEmpt = 0;
    s = (m+1) / 2;
  }
  ~BTree()
  {//析構(gòu)函數(shù)
    DestroyBTree(root);
  }
  BTNode<D>* Root()const
  {//返回 B 樹根結(jié)點(diǎn)指針
    return root;
  }
  void TraverseBTree(BTNode<D>* t, void(*visit) (Record<D>))const
  {//按關(guān)鍵字順序遍歷
    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 樹中查找關(guān)鍵字 k ，返回結(jié)果（pt, i, tag）晨雳，若成功行瑞，則 tag = true
   //pt 所指結(jié)點(diǎn)的第 i 個(gè)關(guān)鍵字等于 k ，否則 tag = false餐禁，等于 k 的關(guān)鍵字應(yīng)
   //插在 pt 所指結(jié)點(diǎn)的第 i 和第 i+1 個(gè)關(guān)鍵字之間
    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[] 中有空位置，將數(shù)據(jù) 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 樹中刪除關(guān)鍵字為 k 的數(shù)據(jù)，用 re 返回該數(shù)據(jù)
    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 樹中每個(gè)關(guān)鍵字是唯一的筑舅。所以在插入數(shù)據(jù)時(shí)，先要查找 B 樹中是否存在該關(guān)鍵字陨舱。如果存在翠拣，則不能插入。新數(shù)據(jù)總是要插在最底層的非葉子結(jié)點(diǎn)中隅忿，這就保證了所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層次心剥。當(dāng)結(jié)點(diǎn)的關(guān)鍵字由于插入超出了最大限度邦尊，就要進(jìn)行分裂背桐。一個(gè)結(jié)點(diǎn)分成 3 部分，中間關(guān)鍵字并入原來的父結(jié)點(diǎn)中蝉揍，左右兩部分分別是中間關(guān)鍵字的左右孩子链峭。如果原來的父結(jié)點(diǎn)由于中間關(guān)鍵字的并入超出了最大限度，則繼續(xù)分裂又沾，直至生成新的根結(jié)點(diǎn)弊仪。

在 B 樹刪除關(guān)鍵字，如果在最底層的非葉子結(jié)點(diǎn)杖刷，則直接刪除励饵；否則，類似于二叉排序樹和平衡二叉樹滑燃，刪除其前驅(qū)或后繼關(guān)鍵字（它們一定在最底層的非葉子結(jié)點(diǎn)中）役听，再將其前驅(qū)或后繼關(guān)鍵字和指針復(fù)制到刪除的關(guān)鍵字和指針處。刪除關(guān)鍵字導(dǎo)致結(jié)點(diǎn)的關(guān)鍵字少于最低限度，就要進(jìn)行合并典予。如果合并導(dǎo)致父結(jié)點(diǎn)的關(guān)鍵字少于最低限度甜滨，則繼續(xù)合并，直至根結(jié)點(diǎn)中沒有關(guān)鍵字瘤袖。這時(shí)刪除根結(jié)點(diǎn)衣摩，B 樹的層數(shù)減 1 。

B 樹是用于處理大數(shù)據(jù)量的查找操作捂敌。其中數(shù)據(jù)量大到不能存放在內(nèi)存數(shù)組 record[] 中艾扮，要將數(shù)據(jù)存放在外存的多個(gè)文件中。甚至內(nèi)存也放不下整個(gè) B 樹黍匾，內(nèi)存中只能存放 B 樹的一個(gè)結(jié)點(diǎn)栏渺。所以，B 樹的每個(gè)結(jié)點(diǎn)都存于外存的文件中锐涯，結(jié)點(diǎn)中的指針內(nèi)容是文件名和偏移量（數(shù)據(jù)在文件中的位置）磕诊。查找過程是首先將 B 樹的根結(jié)點(diǎn)文件放入內(nèi)存中，依據(jù)關(guān)鍵字進(jìn)行查找纹腌。隨時(shí)關(guān)閉查找過的 B 樹結(jié)點(diǎn)霎终，再在內(nèi)存中隨時(shí)打開新的 B 樹結(jié)點(diǎn)，直至查找結(jié)束升薯。為了提高速度莱褒，就要盡量減少打開、關(guān)閉文件的次數(shù)涎劈，并盡量增大 B 樹每個(gè)結(jié)點(diǎn)可容納的關(guān)鍵字?jǐn)?shù)广凸，從而降低 B 樹的層數(shù)。

由于真正的 B 樹每個(gè)結(jié)點(diǎn)的關(guān)鍵字非常多蛛枚，即 keynum 很大谅海，Search() 函數(shù)在 1 ~ keynum 中查找 i 應(yīng)采用折半查找法而不是順序查找法。

4.2 鍵樹

鍵樹用于關(guān)鍵字為字符串的情況蹦浦，故鍵樹也稱為 “詞典查找樹” 扭吁。可以用孩子-兄弟二叉鏈表表示鍵樹盲镶，稱為 “雙鏈鍵樹” 侥袜；也可以用樹的多重鏈表示鍵樹，稱為 “Trie 樹” 溉贿。

推薦閱讀：
查找算法（V）鍵樹——雙鏈樹和Trie樹
鍵樹 B樹 B+樹（注意枫吧，該文中有些許錯(cuò)誤，請(qǐng)注意甄別）