查 找

1. 前言

    由于查找运算的使用频率很高，几乎在任何一个计算机系统软件和应用软件中都会涉及到，所以当问题所涉及的数据量相当大时，查找方法的效率就显得格外重要。在一些实时查询系统中尤其如此。因此，本章将系统地讨论各种查找方法，并通过对它们的效率分析来比较各种查找方法的优劣。

2. 查找的基本概念

（1）查找表和查找

    一般，假定被查找的对象是由一组结点组成的表(Table)或文件，而每个结点则由若干个数据项组成。并假设每个结点都有一个能惟一标识该结点的关键字。    查找(Searching)的定义是：给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。

（2）查找表的数据结构表示

<1> 动态查找表和静态查找表

    若在查找的同时对表做修改操作(如插入和删除)，则相应的表称之为动态查找表。否则称之为静态查找表。

<2> 内查找和外查找

    和排序类似，查找也有内查找和外查找之分。若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。

（3）平均查找长度ASL

    查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的 平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。    平均查找长度 ASL(Average Search Length)定义为：

 其中：

①n是结点的个数；

②Pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即

p1=p2…=pn=1/n

③ci是找到第i个结点所需进行的比较次数。

注意：

为了简单起见，假定表中关键字的类型为整数：

    typedef int KeyType； //KeyType应由用户定义

3. 线性表的查找

    在表的组织方式中，线性表是最简单的一种。顺序查找是一种最简单的查找方法。（1）顺序查找

<1> 顺序查找的基本思想

    基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。

<2> 顺序查找的存储结构要求

    顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。

<3> 基于顺序结构的顺序查找算法

类型说明:

typedef struct{
    KeyType key；
    InfoType otherinfo； //此类型依赖于应用
   }NodeType；
  typedef NodeType SeqList[n+1]； //0号单元用作哨兵

具体算法:

int SeqSearch(Seqlist R，KeyType K)
    { //在顺序表R[1..n]中顺序查找关键字为K的结点，
      //成功时返回找到的结点位置，失败时返回0
      int i；
      R[0].key=K； //设置哨兵
      for(i=n；R[i].key!=K;i--)； //从表后往前找
      return i； //若i为0，表示查找失败，否则R[i]是要找的结点
    } //SeqSearch

算法分析：

① 算法中监视哨R[0]的作用    为了在for循环中省去判定防止下标越界的条件i≥1，从而节省比较的时间。

②成功时的顺序查找的平均查找长度：

    在等概率情况下，pi=1/n(1≤i≤n)，故成功的平均查找长度为 (n+…+2+1)/n=(n+1)/2    即查找成功时的平均比较次数约为表长的一半。若K值不在表中，则须进行n+1次比较之后才能确定查找失败。

（2）二分查找

    二分查找又称折半查找，它是一种效率较高的查找方法。    二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。

<1> 基本思想

二分查找的基本思想是：（设R[low..high]是当前的查找区间）

（1）首先确定该区间的中点位置：

（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：

①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。

②类似地，若R[mid].key<K，则要查找的K必在mid的右子表R[mid+1..n]中，即新的查找区间是右子表[mid+1..n]。下一次查找是针对新的查找区间进行的。

    因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。

<2> 二分查找算法

int BinSearch(SeqList R，KeyType K)
      { //在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零
        int low=1，high=n，mid； //置当前查找区间上、下界的初值
        while(low<=high){ //当前查找区间R[low..high]非空
          mid=(low+high)/2；
          if(R[mid].key==K) return mid； //查找成功返回
          if(R[mid].kdy>K)
             high=mid-1; //继续在R[low..mid-1]中查找
          else
             low=mid+1； //继续在R[mid+1..high]中查找
         }
        return 0； //当low>high时表示查找区间为空，查找失败
       } //BinSeareh

<3> 二分查找的平均查找长度

    设内部结点的总数为n=2h-1，则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为：

ASL_bn≈lg(n+1)-1

    二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：

二分查找的最坏性能和平均性能相当接近。

<4> 二分查找的优点和缺点

虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。

二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。

    对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。

（3）分块查找

    分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。

 <1> 分块查找表存储结构

    二分查找表由"分块有序"的线性表和索引表组成。

① "分块有序"的线性表

    表R[1..n]均分为b块，前b-1块中结点个数为，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的。

② 索引表

    抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：

ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。

    【例】下图就是满足上述要求的存储结构，其中R只有18个结点，被分成3块，每块中有6个结点，第一块中最大关键字22小于第二块中最小关键字24，第二块中最大关键字48小于第三块中最小关键字49。

 <2> 分块查找的基本思想

 分块查找的基本思想是：

①首先查找索引表

　　索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

    ② 然后在已确定的块中进行顺序查找 　　由于块内无序，只能用顺序查找。

    各块可放在不同的向量中，也可将每一块存放在一个单链表中。

在实际应用中，分块查找不一定要将线性表分成大小相等的若干块，可根据表的特征进行分块。

• 分块查找的优点是：

  ->在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。

  　　-> 因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。
• 分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。

 <3> 算法分析

    分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。

①以二分查找来确定块，分块查找成功时的平均查找长度

ASL_blk=ASL_bn+ASL_sq≈lg(b+1)-1+(s+1)/2≈lg(n/s+1)+s/2

②以顺序查找确定块，分块查找成功时的平均查找长度

ASL'_blk=(b+1)/2+(s+1)/2=(s²+2s+n)/(2s)

【例】若表中有10000个结点，则应把它分成100个块，每块中含100个结点。用顺序查找确定块，分块查找平均需要做100次比较，而顺序查找平均需做5000次比较，二分查找最多需14次比较。

注意：

　　分块查找算法的效率介于顺序查找和二分查找之间。

4. 树的查找

    当用线性表作为表的组织形式时，可以有三种查找法。其中以二分查找效率最高。但由于二分查找要求表中结点按关键字有序，且不能用链表作存储结构，因此，当表的插入或删除操作频繁时，为维护表的有序性，势必要移动表中很多结点。这种由移动结点引起的额外时间开销，就会抵消二分查找的优点。也就是说，二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。不妨将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。

（1）二叉排序树

<1> 二叉排序树的定义

    二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：

①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

③左、右子树本身又各是一棵二叉排序树。

    上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。 

<2> 二叉排序树的特点

    由BST性质可得：

（1）二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。

（2）二叉排序树中，各结点关键字是惟一的。

注意：

实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的"小于"改为"大于等于"，或将BST性质(2)里的"大于"改为"小于等于"，甚至可同时修改这两个性质。

（3）按中序遍历该树所得到的中序序列是一个递增有序序列。

　　【例】下图所示的两棵树均是二叉排序树，它们的中序序列均为有序序列：2，3，4，5，7，8。

<3> 二叉排序树的存储结构

typedef int KeyType； //假定关键字类型为整数
typedef struct node { //结点类型
  KeyType key； //关键字项
  InfoType otherinfo； //其它数据域，InfoType视应用情况而定，下面不处理它
  struct node *lchild，*rchild； //左右孩子指针
} BSTNode；
typedef BSTNode *BSTree； //BSTree是二叉排序树的类型

<4> 二叉排序树上的运算

    在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。    递归的查找算法：

BSTNode *SearchBST(BSTree T，KeyType key)
  { //在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NUll
    if(T==NULL||key==T->key) //递归的终结条件
      return T； //T为空，查找失败；否则成功，返回找到的结点位置
    if(key<T->key)
      return SearchBST(T->lchild，key)；
    else
      return SearchBST(T->rchild，key)；//继续在右子树中查找
   } //SearchBST

    在二叉排序树上进行查找时，若查找成功，则是从根结点出发走了一条从根到待查结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。    二叉排序树查找成功的平均查找长度:

    在等概率假设下，下面(a)图中二叉排序树查找成功的平均查找长度为:

    在等概率假设下，(b)图所示的树在查找成功时的平均查找长度为：

           ASL_b=(1+2+3+4+5+6+7+8+9+10)/10=5.5

 

    注意：与二分查找类似，和关键字比较的次数不超过树的深度。

<5> 二叉排序树和二分查找的比较

    就平均时间性能而言，二叉排序树上的查找和二分查找差不多。    就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O(lgn)，因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表，则应选择二叉排序树作为其存储结构。

<6> 平衡二叉树

    为了保证二叉排序树的高度为lgn，从而保证然二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(lgn)，在往树中插入或删除结点时，要调整树的形态来保持树的"平衡。使之既保持BST性质不变又保证树的高度在任何情况下均为O(lgn)，从而确保树上的基本操作在最坏情况下的时间均为O(lgn)。

注意：

　①平衡二叉树(BalancedBinaryTree)是指树中任一结点的左右子树的高度大致相同。

　②任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。

　③平衡的二叉排序树指满足BST性质的平衡二叉树。

    　④AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树度高约为lgn，AVL树是接近最优的。

（2）B-树

    当查找的文件较大，且存放在磁盘等直接存取设备中时，为了减少查找过程中对磁盘的读写次数，提高查找效率，基于直接存取设备的读写操作以"页"为单位的特征。    1972年R.Bayer和E.M.McCreight提出了一种称之为B-树的多路平衡查找树。它适合在磁盘等直接存取设备上组织动态的查找表。

<1> B-树的定义

    一棵m(m≥3)阶的B-树是满足如下性质的m叉树：

(1)每个结点至少包含下列数据域：

(j，P₀，K_l，P₁，K₂，…，K_i，P_i)

其中：

j为关键字总数

K_i(1≤i≤j)是关键字，关键字序列递增有序：K₁<K₂<…<K_i。

P_i(0≤i≤j)是孩子指针。对于叶结点，每个P_i为空指针。

注意：

①实用中为节省空间，叶结点中可省去指针域P_i，但必须在每个结点中增加一个标志域leaf，其值为真时表示叶结点，否则为内部结点。

　②在每个内部结点中，假设用keys(Pi)来表示子树Pi中的所有关键字，则有：

　　　　　keys(P₀)<K₁<keys(P₁)<K₂<…<K_i<keys(P_i)

即关键字是分界点，任一关键字Ki左边子树中的所有关键字均小于K_i，右边子树中的所有关键字均大于K_i。

(2)所有叶子是在同一层上，叶子的层数为树的高度h。

(3)每个非根结点中所包含的关键字个数j满足：

　即每个非根结点至少应有个关键字，至多有m-1个关键字。

　因为每个内部结点的度数正好是关键字总数加1，故每个非根的内部结点至少有子树，至多有m棵子树。

(4)若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树。根至多有m-1个关键字，故至多有m棵子树。

<2> B-树的结点规模

    在大多数系统中，B-树上的算法执行时间主要由读、写磁盘的次数来决定，每次读写尽可能多的信息可提高算法得执行速度。

B-树中的结点的规模一般是一个磁盘页，而结点中所包含的关键字及其孩子的数目取决于磁盘页的大小。

注意：

　①对于磁盘上一棵较大的B-树，通常每个结点拥有的孩子数目(即结点的度数)m为50至2000不等

　②一棵度为m的B-树称为m阶B-树。

　③选取较大的结点度数可降低树的高度，以及减少查找任意关键字所需的磁盘访问次数。

【例】下图给出了一棵高度为3的1001阶B-树。

                 

说明：

①每个结点包含1000个关键字，故在第三层上有100多万个叶结点，这些叶节点可容纳10亿多个关键字。

②图中各结点内的数字表示关键字的数目。

　　③通常根结点可始终置于主存中，因此在这棵B-树中查找任一关键字至多只需二次访问外存。

<3> B-树的存储结构

#define Max l000 //结点中关键字的最大数目：Max=m-1，m是B-树的阶
#define Min 500 //非根结点中关键字的最小数目：Min=┌m/2┐-1
typedef int KeyType； //KeyType应由用户定义
typedef struct node{ //结点定义中省略了指向关键字代表的记录的指针
  　int keynum； //结点中当前拥有的关键字的个数，keynum《Max
  　KeyType key[Max+1]； //关键字向量为key[1..keynum]，key[0]不用。
  　struct node *parent； //指向双亲结点
  　struct node *son[Max+1]；//孩子指针向量为son[0..keynum]
 }BTreeNode；
typedef BTreeNode *BTree；

    注意：为简单起见，以上说明省略了辅助信息域。在实用中，与每个关键字存储在一起的不是相关的辅助信息域，而是一个指向另一磁盘页的指针。磁盘页中包含有该关键字所代表的记录，而相关的辅助信息正是存储在此记录中。    有的B-树(如第10章介绍的B+树)是将所有辅助信息都存于叶结点中，而内部结点(不妨将根亦看作是内部结点)中只存放关键字和指向孩子结点的指针，无须存储指向辅助信息的指针，这样使内部结点的度数尽可能最大化。

<4> B-树的查找

    在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。

对结点内的存放有序关键字序列的向量key[l..keynum]用顺序查找或折半查找方法查找。若在某结点内找到待查的关键字K，则返回该结点的地址及K在key[1..keynum]中的位置；否则，确定K在某个key[i]和key[i+1]之间结点后，从磁盘中读son[i]所指的结点继续查找……。直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。

    【例】下图中左边的虚线表示查找关键字1的过程，它失败于叶结点的H和K之间空指针上；右边的虚线表示查找关键字S的过程，并成功地返回S所在结点的地址和S在key[1..keynum]中的位置2。

 

    B-树的查找算法：

BTreeNode *SearchBTree(BTree T，KeyType K，int *pos)
 { //在B-树T中查找关键字K，成功时返回找到的结点的地址及K在其中的位置*pos
//失败则返回NULL，且*pos无定义
  int i；
  T→key[0]=k; //设哨兵．下面用顺序查找key[1..keynum]
  for(i=T->keynum；K<t->key[i];i--)； //从后向前找第1个小于等于K的关键字
  if(i>0 && T->key[i]==1){ //查找成功，返回T及i
    *pos=i；
    return T；
   } //结点内查找失败，但T->key[i]<K<T->key[i+1]，下一个查找的结点应为
     //son[i]
  if(!T->son[i]) //*T为叶子，在叶子中仍未找到K，则整个查找过程失败
    return NULL；
    //查找插入关键字的位置，则应令*pos=i，并返回T，见后面的插入操作
  DiskRead(T->son[i])； //在磁盘上读人下一查找的树结点到内存中
  return SearchBTree(T->Son[i]，k，pos)； //递归地继续查找于树T->son[i]
 }

 查找操作的时间开销：

    B-树上的查找有两个基本步骤：

　①在B-树中查找结点，该查找涉及读盘DiskRead操作，属外查找；

　②在结点内查找，该查找属内查找。

查找操作的时间为：

　①外查找的读盘次数不超过树高h，故其时间是O(h)；

　②内查找中，每个结点内的关键字数目keynum<m(m是B-树的阶数)，故其时间为O(nh)。

　注意：

①实际上外查找时间可能远远大于内查找时间。

　　②B-树作为数据库文件时，打开文件之后就必须将根结点读人内存，而直至文件关闭之前，此根一直驻留在内存中，故查找时可以不计读入根结点的时间。

<5> B-树的高度及性能分析

    B-树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成。B-树上大部分基本操作所需访问盘的次数均取决于树高h。关键字总数相同的情况下B-树的高度越小，磁盘I/O所花的时间越少。    与高速的CPU计算相比，磁盘I/O要慢得多，所以有时忽略CPU的计算时间，只分析算法所需的磁盘访问次数（磁盘访问次数乘以一次读写盘的平均时间(每次读写的时间略有差别)就是磁盘I/O的总时间）。

定理  若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B-树，其树高h至多为：

log_t((n+1)/2)+1。

这里t是每个(除根外)内部结点的最小度数，即

    由上述定理可知：B-树的高度为O(logtn)。于是在B-树上查找、插入和删除的读写盘的次数为O(log_tn)，CPU计算时间为O(mlog_tn)。

    性能分析:

    ①n个结点的平衡的二叉排序的高度H（即lgn）比B-树的高度h约大lgt倍。

【例】若m=1024，则lgt=lg512=9。此时若B-树高度为4，则平衡的二叉排序树的高度约为36。显然，若m越大，则B-树高度越小。

②若要作为内存中的查找表，B-树却不一定比平衡的二叉排序树好，尤其当m较大时更是如此。

因为查找等操作的CPU计算时间在B-树上是

O(mlog_tn)=0(lgn·(m/lgt))

    而m/lgt>1，所以m较大时O(mlogtn)比平衡的二叉排序树上相应操作的时间O(lgn)大得多。因此，仅在内存中使用的B-树必须取较小的m。（通常取最小值m=3，此时B-树中每个内部结点可以有2或3个孩子，这种3阶的B-树称为2-3树）。