宋文摘

template <class _InputIter, class _Tp>

inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val,

                       input_iterator_tag)

{

  while (__first != __last && !(*__first == __val))

    ++__first;

  return __first;

}

这个应该能代表我们曾经写过的所有顺序查找代码，关于为什么写成了这个样子，《C++沉思录》第17章有详细的说明。或许VC6的STL代码更容易理解些：

template<class _II, class _Ty> inline

       _II find(_II _F, _II _L, const _Ty& _V)

       {for (; _F != _L; ++_F)

              if (*_F == _V)

                     break;

       return (_F); }

要是这样就完事了该多好，但是，上面的代码只是对于无规则数据的通用查找方法，如果我们想更快，就必须给数据排列添加规则，这样我们就能利用规则来提高查找效率。O(n)和O(logn)毕竟是不能同日而语的，更不要提O(1)了。

正是人们对于速度的追求才导致了这一部分由上面的3行代码变成了庞大无比的一大系算法（其实这也是不得以的事情，5分钟的等待就足以令一个人发狂了）。对于速度的明显提高是建立在n很大的基础上的，这样就不得不涉及到外存，你可以看到，下面的很多演化是因为外存的介入，如果不注意这点，常常会对我们所做的努力感到疑惑。

回忆一下查英汉字典的过程，将有助于我们发现一些查找策略——理论来自于实践，好像不会再有人对这句话有异议了吧？

首先，字典的正文是字典有序的（这个提法有些古怪，和字典的排序方法一样的称作字典有序，然后我又说字典是字典有序的——反正查字典的人都明白字典是怎么排序的，我就不解释了），因此，有些英汉字典没有目录——只要前言和附录不是太多，一般都不会有目录——实际上我们查字典也通常不用目录。具体怎么查呢？

大体上翻一下——a打头就少翻点，p打头就多翻点——如果当前页的末单词（一般来说在页的右上角的单词）排在所查单词的前面，就往后翻——翻多少页自己估量——如果当前页的首单词排在所查单词的后面，就往前翻——翻多少页自己估量。重复这个过程，直到所查单词位于当前页的首末单词之间，然后在当前页查找——这个过程也可以前后比较，但通常都是从前向后搜索一遍。

回忆这个过程，我们能得到很多启示，首先就是“折半查找”思想。

折半查找

当前值大于所查值就往前搜索，小于就往后搜索，这是折半查找的基本思想。想当年曾经为这个算法花费了不少脑细胞，看来还是我太笨的缘故：

int binfind(int a[], int N, int x)

{

       int low = 0, high = N - 1, mid;

       while (low <= high)

       {

              mid = (low + high) / 2;

              if (a[mid] == x) return mid;

           if (a[mid] < x) low = mid + 1;

              else high = mid - 1;

       }

       return N;

}

没有写成模板形式的，是因为支持折半查找的限制比较多，上面的虽然适用范围很小，但是很容易理解。注意到“查字典”的向前（向后）翻的页数是自己估量的，一个查字典熟练的人和一个生手的差别就常常体现在这里。在计算机里，这个“估量”就是插值。这很容易理解——一本书1000页，怎样快速翻到第300页？很显然，翻到书厚度3/10的地方，当然，这不会很准确，但离第300页已经很近了。这个例子的启示是，在均匀序列里，插值应该是有效的。

int insfind(int a[], int N, int x)

{

       int low = 0, high = N - 1, mid;

       if (x > a[high]) return N;//防止越界

       while (low < high)

       {

              mid = low + (x - a[low])*(high - low)/(a[high] - a[low]);

              if (a[mid] == x) return mid;

              if (a[mid] < x) low = mid + 1;

           else high = mid - 1;

       }

       return N;

}

测试程序

#include <cstdio>

#include <cstdlib>

#include <ctime>

#include "find.h"

#define N 30000

int a[N];

class timer//单位ms

{

public:

       void start() { start_t = clock(); }

       clock_t time() { return (clock() - start_t); }

private:

       clock_t start_t;

};

int main()

{

       timer TIMER; int i, t;

       for (i = 0; i < N; i++) a[i] = 2*i+1;

       TIMER.start();

//     for (i = 0; i < N; i++) seqfind(a, N, rand()%N);

       t = TIMER.time();

       printf("N=%d %dseqfind TimeSpared: %dms\n", N, N, t);

//     printf("%d", a[seqfind(a, N, 2763)]);

       TIMER.start();

       for (i = 0; i < N; i++) binfind(a, N, rand()%N);

       t = TIMER.time();

       printf("N=%d %dbinfind TimeSpared: %dms\n", N, N, t);

//     printf("%d", a[binfind(a, N, 2763)]);

       TIMER.start();

       for (i = 0; i < N; i++) insfind(a, N, rand()%N);

       t = TIMER.time();

       printf("N=%d %dinsfind TimeSpared: %dms\n", N, N, t);

//     printf("%d", a[insfind(a, N, 2763)]);

       return 0;

}

测试结果

N=30000 30000seqfind TimeSpared: 12107ms

N=30000 30000binfind TimeSpared: 40ms

N=30000 30000insfind TimeSpared: 10ms

注意，这个测试里面包含了查找失败的情况，否则简单的顺序查找的性能不会那么差。

树型查找

折半查找所需要的，有序的、可以随机存取的、顺序结构的限制，导致了排序的额外负担（如果是逐个添加，主要的负担是移动数据，此时是折半插入排序）。通过观察折半查找的过程，发现实际上mid是从判定树的根走到了叶子节点，而这棵判定树和有相同节点的完全二叉树的高度是相同的。链式结构的好处就是不用大量移动数据，自然的用链树来做查找结构应该是个好选择。

在前面我们曾经写过一个BSTree类，这个类大致上能满足我们的要求。而为了在不同的输入情况下，使得树的高度尽可能的小，平衡树的概念被提出来了，例如前面的AVLTree类。所谓的平衡，现在更多意义上是指和完全m叉树高度的比值是小于某个常数的树，也就是高度≤klog_mn的树，k为一个定常数。注意到AVL树的定义实际上太苛刻，就很容易理解为什么要放宽要求。而实际能应用的平衡树，都是为了满足这个要求而自己定一套规则，比如B－树，这个后面会讲到。

索引

有些字典会提供一个目录，大部分情况是这样的A……xx；B……xx；……。这样就能迅速翻到开头字母对应的页数（实际上也知道了开头字母结束的地方），并且每个页的左右上角的单词也说明了本页的单词范围（可以判断所查单词在不在此页）。这些就是索引。

使用索引能够快速的定位查找范围，从我们查字典的经验看来，这也应该是能提高查找效率的方法。注意到目录的作用，它使得我们所需的字典空间分布，在一页（或者几页）的空间上迅速的被我们得到——类比来看，如果数据太多以至内存装不下，我们也可以弄个“目录”，使得可以将数据分块的读入内存查找。

B－树

当数据膨胀到一个可怕的程度时，连索引都不能被全部装入内存——见过印刷版的EI检索都有这个感觉，光一个检索目录都比我们用的字典厚。我们的办法就是索引再索引，显而易见的，每个索引块都应该尽可能的大，以帮助我们获得尽可能多的信息，而避免再次的查索引（此时一般都会涉及外存的存取）。AVL树此时便力不从心了，我们需要一种新的结构。

相信每个学到这里的人都对B－树的定义深恶痛绝，这个的责任应该由写书的人来负，虽然定义、概念是人认知的重要工具和途径，但在这里是适得其反的。原因就是B－树根本不存在概念意义上的“概念”，它只是一个描述型的“概念”，是B－树能够运行从而表现出来的一种现象。不管怎么说，先看一下现有的书上的定义（省略了“或者为空树”这句话）：

严蔚敏、吴伟民《数据结构（C语言版）》

1.         每个节点至多有m棵子树

2.         若根不是叶子节点，至少有两棵子树

3.         除根以外的所有非终端节点至少有ém/2ù棵子树

4.         所有非终端节点包含下列信息数据（n，A₀，K₁，A₁，K₂，A₂……，K_n，A_n），其中，K_i为关键字，且K_i<K_i+1（i＝1，2，……，n－1）；A_i（i＝0，……，n）为指向子树根节点的指针，且指针A_i-1所指子树中所有节点的关键字均小于K_i（i＝1，……，n），A_n所指子树中所有的节点的关键字均大于K_n，n（ém/2ù-1£ n £ m-1）为关键字的个数（或n+1为子树个数）。

5.         所有的叶子节点都出现在同一层次上，并不带信息（可以看作是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空）。

殷人昆等《数据结构（用面向对象方法与C++描述）》

1.         m路搜索树（实际上是上面第1、4条的内容）

2.         根节点至少有两个子女

3.         除根节点以外的所有节点（不包括失败节点）至少有ém/2ù个子女

4.         所有的失败节点都位于同一层。事实上，这些节点都是作为外部节点存在，不是树上的节点。

非常莫名其妙的定义——凭什么根至少有两个子女，而其他的至少ém/2ù个子女？跟AVL树的定义比较一下就能看出这个定义的不合理处——AVL树只是给出了平衡的定义“左右子树高度差不超过1”，至于什么平衡因子、旋转，根本就没有提及，那只是为了保证平衡的手段。显然，现在的B－树的定义，把为了保证平衡而采取措施的结果包括在定义之中了，而这必将导致人的认知上的迷惑，因此这样的定义是不合格的。或许，一个不和现在定义矛盾的合理的定义应该是这样：采用如下办法达到“平衡”的m路搜索树……，当然，我们首先要解决什么叫“平衡”，而这个直觉上的定义前面已经提到了。

接下来，让我们看看保持平衡的“如下办法”是什么。回忆一下AVL树，那时的旋转确实是很精妙的方法——保持中序有序的情况下改变子树高度差，我也耗费了不少脑细胞把AVL树的讲解从书上的莫名其妙变成了按部就班，这是本人到目前为止最为得意的一件事情，到大家能看到这篇文字的时候，应该也能看见我写的AVL树的讲解了。

两个叉的AVL树能旋转，m个叉的树怎么转？看来得换个思路，前人已经为我们做到了，就是节点的分裂和合并。

分裂

节点装不下的时候就分裂，也就是说对于一个节点，当第m个元素进来的时候，就要分裂。怎么分裂？以中间元素为轴，左右两部分各形成一个节点，作为中间元素的左右孩子——这里还是借用了二叉树的概念，而事实上，m叉搜索树就是多个二叉搜索树拼合的产物——这样还是中序有序的（或许不该说“中序”，大家结合二叉树自己理解吧），中间元素带着这两个孩子插入到原来节点的父节点，当然，父节点满的时候同样要分裂，这样一层层直到根节点（或者不用分裂）。

纵观分裂的过程，我们才能明白前面的定义是怎么回事。如果采用如上的分裂方法，对于根节点来说，要么没有子女，要么一分裂就两个子女。而对于非根节点，只有当节点满的时候才会分裂，那自然最少有ém/2ù个子女。

而“所有的失败节点都位于同一层”是B－树的“平衡准则”，很容易就能看出这样的树是“平衡”的。

所以，关于B－树的定义实际上是B－树维持平衡的外在表现，它不应该作为B－树的定义，而只能是一种描述。

合并

和二叉搜索树一样，删除都归结成在叶子节点的删除，如果不在叶子节点，就拿叶子节点中的覆盖掉，转化成在叶子节点的删除。同样的，当不平衡出现时（即不满足上面B－树的描述），需要平衡化。

我们看到，父节点中的元素和左右两个孩子原来可能是一个节点的，或者可以说他们可以合并成一个节点。这样一来，如果他们的元素总和大于m－1，那么就从多的向少的拨一个元素——想想电视里老和尚手里的念珠，元素的移动过程是这样的：元素多的节点——父节点（手里的珠子）——元素少的节点。如果他们的元素总和小于等于m－1，那么就把他们合并成一个节点，这样一来，父节点就会少一个元素，如果也出现了不平衡，也同样处理。

观看分裂合并的过程，就会发现插入删除的起点都在叶子节点，出现不平衡后，无论分裂还是合并，都会把多了（或者少了）一个元素的变化传递到父节点，从而导致对父节点的再度平衡化。和AVL树的调整简直是如出一辙，不同的是，AVL树不可能分裂合并，因此采取的是旋转的办法；或者可以说B－树不能旋转，因此采取了分裂合并。而两种调整方法都是在保持有序的情况下，使树高（差）发生了变化。

当树的叉多起来的时候，操作起来都会觉得不便，因此B－树更应该是为了减少内外存交换开销而提出来的，和外排一样，对一般的应用意义不大，不做系统级别的应用（或者是为了考试）很少会用到，就不再具体讲解了。

而如果仅是在内存中，叉的数目少一点会比较好，比如3叉（因为这样的树每个节点有2或3个叉，又叫2－3树），而实际上，AVL树（或者红黑树）已经做得很好了，没必要费心在多叉搜索树上。

B+树

想想人们还真烦，B－树都有人认为是Binary树了，又来一个B＋树，看来老外还真是该打，Binary和Balance缩写也不多保留几个字母，都是B。

B＋树更是为了外存而提出来的，同样的，一般用途不大，一般人不必费心了（考试的例外）。注意的是和B－树的几点差别：B＋树的非叶子节点都是索引，因此当删除关键码的时候，有些情况不必改动索引，查到了关键字也要一直走到叶子节点；另外所有的叶子节点都是链接在一起的，从头到尾可以顺序遍历——和线索二叉树很像不是吗？

严版的和殷版的在B＋树的定义（更准确的说是描述）上有一个很大的分歧（节点中几个元素几个子树），从教学的目的上，我同意殷版的描述，因为这样的描述能更直接的表达B＋树是如何从B－树演化来的，严版的引入了额外的区分，分散了读者的注意力。

散列（哈希表）

我更觉得哈希表是因为目前的储存结构而诞生的。想想我们的储存器（RAM），每个单元对应一个地址，对于数组来说，当知道首地址后，可以马上计算出第N个元素的地址，因此可以马上读取。反过来说，却不能由内容来确定元素的地址，想知道含某个内容的单元的地址，就必须挨个查看，或者在有序的情况下折半查找。

而当我们的储存器能够支持按内容存取的话，那我们前面介绍的一切查找方法都会变得黯淡无光——想找15，马上就能定位到15的位置，这样O(1)的方法简直是人们梦寐以求的。不知是幸运（前面查找的方法还是大有用武之地）还是不幸（直接的O(1)查找不可能容易的实现），我们想要的那种类型的储存器（相联存储器）贵的要命（也可能容量根本做不大）。

既然硬件不支持，就从软件下手吧，前面费了点口舌，是为了使大家明白现有的方法是建立在现有的结构上的，而当现有体系发生改变的时候，方法也会跟着改变。

显然，只要我们能在内容和序号之间建立一种函数关系，在现有储存结构上就能实现按内容存取了——内容→函数变换→序号。

实际上，任何可列的内容都是可以和整数一一对应的（我们总能找到这样的法则），但是，一一对应的代价很可能是整数的范围很广，结果使得空间的浪费很大。打个比方，一张1901～2000年事件索引表，只需要一个100大小的数组，0元素代表1901，99元素代表2000——这里也回答了很多人疑惑的问题，2000年究竟是不是21世纪，这么一对照就会发现这是个历史遗留问题，公元元年是公元1年而不是公元0年才会导致这样的问题，历法几千年来修订了好几回，我们也不要对这个问题太较真了，一句话，随大流。然而我们如果做一个人类历史的索引表，上下五千年（把古代人算上就是多少万年了），但却不是每年都有事发生（应该说是值得我们注意的事），更有甚者是确切的年份都不知道，显然前面的做法就不太合理了，绝大多数空间都是空闲的。

因此，实际上采用的函数变换都是带有压缩性质的，即输出的值域都是有限的一个范围，典型的就是0～表长。就像我们的日常经验一样，一压缩，就会有些元素被挤到一起，“你我不分”了。因此，还必须有合理处理“冲突”的办法。函数变换加上“冲突”处理方法，就构成了散列这种查找方法。

具体的散列函数和冲突处理，请阅读教科书，我不再详细说明了。

键树（Trie树）与基数排序

这其实都是建立在散列的思想上的，在他们身上，很容易就能发现链散列的影子，而Trie树更像是静态的基数排序。Trie树用来组织内存中的数据也是很好用的，并非是只适用于外存。那么一本厚书也仅仅是一两页，我这几十页的有这么一段也差不多了，^_^。具体请阅读教科书，一般读者可跳过。