数据结构之查找

目录

7.1 线性结构的查找

7.1.1 顺序查找

7.1.2 折半查找（二分）

7.1.3 分块查找（索引）

7.2 树表

7.2.1 二叉排序树BST

7.2.2 二叉平衡树BBT/AVL

7.2.3 B树及基本操作 

7.2.4 B+树的基本概念

7.3 散列表

7.3.1散列表的基本概念

7.3.2散列函数的构造方法

7.3.3处理冲突的方法

7.3.4散列查找

---

（掌握散列查找的特征和性能分析，散列表的构造和冲突处理方法，查找成功和查找失败的平均查长度；折半查找的过程，构造判定树，分析平均查找长度；掌握B树的插入删除和查找，B+树的概念性质）

7.1 线性结构的查找

7.1.1 顺序查找

用于在静态的线性表（顺序表or链表）中进行查找

·基本思想：从线性表的某一端开始，将表中的元素与关键字逐个比较。对于顺序表，通过数组下标递增的顺序扫描每个元素；对于链表，可通过指针来一次扫描每个元素

·算法实现：

查找表的顺序存储结构
int Search Seq( SSTable ST,int key){
  for(int i=0; ST.elem[i]! key && i< ST.length; i++): 
  if(i ==ST.length) return -1;
  else relurn i;
}

·算法优化：把待查关键字key存入表头(哨兵、监视哨)， 从而避免查找过程中每一次比较后都要判断查找位置是否越界，加快查找速度

int Scarch_Seq(SSTablc ST,int key){
  ST.elem[0] = key;
  for(int im ST.Iength; STR[i]!= key; i--);
  return i;
}

·效率分析：对于有n个元素的表，成功找到表中的第i个元素与关键字相等，需要比较n-i+1次，假设每个元素的查找概率相等，其平均查找长度ASL=ΣPi(n-i+1)=n+1/2，时间复杂度为O(n)；若查找失败则需要比较n+1次，查找不成功的平均查找长度ASL=n+1，时间复杂度还是O(n)。显然顺序查找缺点很明显，当n很大时，其查找效率极低

【问题】：查找概率不相等时如何提高查找效率？

按查找概率的高低存储，查找概率越高的存储在比较次数越少的地方，反之存储在比较次数越多的地方

7.1.2 折半查找（二分）

·基本思想：二分查找仅适用于有序的顺序表。在有序表中，首先取中间位置的元素作为比较对象，将给定key值与其比较，若相等则查找成功，返回元素的存储位置；若key值小于中间位置元素，则在其左半区（大于则在右半区）进行同样查找，如此重复直至成功或失败

·具体算法：

非递归算法

int Binary Search(int a[],int n,int key){
    int low, high, mid;
    low=1;             //定义最低下标为记录首位
    high=n;            //定义最高下标为记录末位
    while (low<=high){
        mid=(low+high)/2;     //折半
        if (key< a[mid] )     //若查找值比中值小
          high=mid-1;        //最高下标调整到中位下标小一位
        else if (key>a[mid])  //若查找值比中值大*/
          low=mid+1;         //最低下标调整到中位下标大一位
        else
          return mid;        //若相等则说明mid即为查找到的位置
    }
   return 0;
}

递归算法

int Bin_Scarch(SSTable ST, int key, int low, int high){
  if(low > high)    return -1;           //查找不到时返回-1
  mid = (low+high)/2;
  if(ST.elem[mid]==key)                  //找到待查元素
     return mid;
  else if (key < ST.elem[mid)            //缩小查找区间
       Bin_Search(ST, key, low, mid-1);   //继续在前半区间进行查找
  else 
       Bin_Search(ST, key, mid+1, high);  //继续在后半区问进行查找
}

·折半查找的判定树：折半查找可以用二叉树来表示，称为判定树。查找成功时的查找长度为根结点到目的结点路径上的结点数或结点的层数；查找失败的长度为根结点到对应失败结点的父结点路径上的结点数

若有序序列有n个元素，则对应判定树有n个非叶结点(白色框）和n+1个叶结点(蓝色框)。显然判定树是平衡二叉树

·算法效率：由以上可以分析用折半查找查找到给定值的比较次数最多不会超过树的的高度，在等概率查找时，查找成功的平均查找长度：

ASL=1/nΣh*2^h-1=1/n(1*1+2*2+..+h*2^h-1)=n+1/n log2(n+1)-1≈log2(n+1)-1

其中h为树的高度，元素个数为n时h=⌈log2(n+1) ⌉，所以其时间复杂度为O(log2n)，平均情况下比顺序查找的效率高。

对于上图判定树，等概率条件下，查找成功（即白色框）的ASL=1/11(1*1+2*2+3*4+4*4)=3；而查找不成功(蓝色框）ASL=1/12(3*4+4*8)=11/3

【注】：因为折半查找需要方便定位查找区域，所以要求线性表必须具有随机存取的特性，所以仅适用于顺序存储结构，不适用于链式存储结构

7.1.3 分块查找（索引）

·基本思想：将查找表分为若干子块，块内元素可以无序，块间一定要有序，且第一个块中的最大关键字要小于第二块中所有的关键字，以此类推。同时再建立一个索引表，表中存放各个块中的最大关键字以及用于指向块首的指针，索引表按关键字有序排列（可通过英文字典查单词过程理解）

·查找过程：①先在索引表中确定待查关键字所在的块，可以顺序or折半查找；②根据块首指针找到块，在块中进行顺序查找

·查找效率：分块查找的评价查找长度为索引查找和块内查找的平均长度之和：ASL=LI+LS

将长度为n的表均匀分为b块，每块中有s个元素，等概率条件下，当索引及块内均使用顺序查找则ASL=LI+LS=b+1/2 + s+1/2

当索引表采用折半查找时ASL=LI+LS=log2(b+1)+ s+1/2

7.2 树表

7.2.1 二叉排序树BST

·Def：或者是一棵空树，或是具有下列特性的二叉树

1)若左子树不为空，则左子树上所有结点的值都小于根结点的值;

2)若右子树不为空，则右子树上所有结点的值都大于根结点的值; 

3)左右子树都分别是二叉排序树

对非空的二叉排序树进行中序遍历的到一个递增的有序序列

·查找算法：先将给定的K值与二叉排序树的根结点的关键字进行比较:若相等，则查找功;若给定的K值小于BST的根结点的关键字: 继续在该结点的左子树上进行查找;若给定的K值大于BST的根结点的关键字:继续在该结点的右子树上进行查找。

非递归实现

BSTNode *BST_Serach(BSTree *T，int key){
  while(T!= NULL && key!= T->key){
      if(key < T->key)
         T= T->lchild;
      else 
         T=T->rchild; 
     }
     return T;
}

递归实现

BSTNode *BST_Serach(BSTree *T，int key){ 
  if(!T||key == T->key)
    return T;
  else if (key < T->key)
    return BST_Serach(T->Lchild, key); /*左子树上递归查找*/
  else
    return BST_Serach(T->Rchild, key) ;/*右子树上递归查找*/
}

·查找效率：二叉排序树关键字的比较次数=该结点所在的层次数，最大为树的深度；其查找效率取与树的形态有关，在最好的情况下，树的深度为⌈log2(n+1) ⌉，ASL=log2(n+1)-1，与折半查找的判定树相同O(log2n);最坏的情况下，插入的n个元素从一开始就有序，变成单支树，树的深度为n，ASL=n+1/2，查找效率与顺序查找情况相同O(n)

【问】：如何提高形态不均衡的二叉排序树的查找效率？

对二叉排序树做平衡化处理，让二叉树的形态均匀，处理过后的二叉树便为平衡二叉树

·插入：在BST树中插入一个新结点时，若BST树为空，则令新结点为插入后BST树的根结点;否则，将新结点的关键字与根结点T的关键字进行比较：若相等，则不需要插入; 若新节点的keykey: 该结点插入到T的左子树中; 若新节点的ky>T->key:该结点插入到T的右子树中（新插入的结点一定是一个新添加的叶子结点）

int BST_Insert(BSTree *T,int k){ 
    if(T==NULL){
       T = (BSTree)nalloc(sizeof(BS TNode));
       T-> key= k;
       T->lchild= T->rchild = NULL; 
       return 1;
    }
    else if(k==T->key)
       return 0;
    if(key < T->key)
       return BST_Insert(T->lchild, key);
    else
       return BST_Insert(T->rchild, key);
}

·构造：按照插入的过程，从一棵空树出发，依次输入元素，将它们插入二叉排序树中合适的位置。一个无序序列通过构造二叉排序树变成一个有序序列，即构造树的过程就是对无序序列进行排序的过程（插入的节点均为叶子节点，故无需移动其他节点，相当于在有序序列上插入记录而无需移动其他节点）

【注】：不同的关键字序列可能构造出不同的二叉排序树

·删除：删除结点后仍要保持二叉排序树的性质，所以删除过程中要考虑如何将因删除而断开的二叉链表重新连接以及防止重连后树的高度增加，我们按三种情况处理：

1）删除结点为叶子结点，直接删除

2）被删除结点只有一棵左子树或右子树，让其子树代替它的位置

3）被删除结点有左子树也有右子树，让其直接前驱或后继代替它的位置，然后再删去这个直接前驱或后继，转换为1）或2）的过程

7.2.2 二叉平衡树BBT/AVL

·Def：平衡二叉树或是空树，或是满足下列性质的二叉排序树

1)左子树和右子树高度之差的绝对值不大于1;（结点的平衡因子=左子树高-右子树高）

2)左子树和右子树也都是平衡的二叉排序树

·插入：在二叉排序树中插入新的结点后导致了二叉排序树的失衡，要使之重新平衡，先找到插入路径上离插入结点最近的平衡因绝对值大于1的结点，对以它根的子树，调整各结点的位置，使之重新平衡，调整的规律主要有以下四种：

调整以上四种情况可总结为两点：

①降低高度

②将四种型状的中序遍历输出，按照中序遍历输出的结果进行重新链接

1）在结点的左孩子L的左子树L插入新结点

 2）在结点的右孩子R的右子树R插入新结点

3）在结点的左孩子L的右子树R插入新结点

4）在结点的右孩子R的左子树L插入新结点

 ·查找：平衡二叉树上查找与二叉排序树相同，查找过程中，与给定值进行比较的关键字个数不超过树的深度。以N(h)表示深度为h的平衡树中含有的最少结点数，则N(h)=N(h-1)+N(h-2)+1

因此可以证明含有n个结点的平衡二叉树的最大深度h≈log2(N(h)+1),即平衡二叉树的平均查找长度为O(log2n).

7.2.3 B树及基本操作 

  随着数据的插入越来越多，树的深度也越来越深，意味着IO次数越多影响读取的效率，此时引入B树，一个有序的多路查询树

·Def：一棵m阶的B树或为空树，或为满足下列特性的m叉树：

1. 树中每个结点至多有m棵子树，即每个结点至多有m-1个关键字
2. 除根节点外，所有非叶结点至少有⌈m/2⌉棵子树
3. 若根节点不是叶子结点，则根结点至少有两棵子树
4. 所有叶子结点都在同一层上，并且不带信息，即B树是所有结点的平衡因子均等于0的多路查找树

·非叶结点的结构：

 其中，ki为结点的关键字，且满足k1

【例】5阶B树：

·B树的高度

对任意一棵包含n个关键字(n≥1)、高度为h、阶数为m的B树:

1）因为B树中每个结点最多有m棵子树，m-1个关键字，所以在高度为h的m阶B树中关键字个数应满足n≤(m-1)(1 +m+m2 +..+mh-1)=mh-1,则有    h≥logm (n+1)

2）若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。

根据B树第一层至少有1个结点；第二层至少有2个结点；除根结点外的每个非终端结点至少有⌈m/2⌉棵子树，则第三层至少有2⌈m/2⌉个结点...第h+ 1层至少有2(⌈m/2⌉)h-1个结点，这里第h+ 1层是不包含任何信息的叶结点。对于关键字个数为n的B树，叶结点即查找不成功的结点为n+1,由此有n+ 1≥2(⌈m/2⌉)h-1个，即     h≤log⌈m/2⌉((n+ 1)/2)+ 1

【例】：假设一棵3阶B树共有8个关键字，则其高度范围为2≤h≤3.17

·B树的查找：B树的查找与二叉查找树类似，只是在每个结点上做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定，基本步骤为：①在B树中找结点；②在结点内找关键字；

  在B树上查找到某个结点后，在有序表中查找，若找到则查找成功，否则按照对应指针信息到所指的子树中查找，查找到叶结点时对应指针为空了，说明树中没有关键字，查找失败

·B树的插入：

1）定位。利用B树查找算法，找出插入该关键字的最低层中的某个非叶结点（当找到表示失败的叶结点，这样就确定了最底层非叶结点的插入位置）

2）插入。若插入后结点的关键字个数小于m便直接插入；大于m-1时必须对结点进行分裂

【分裂示例】：对于m=3的B树，结点最多有2个关键字

·B树的删除：

B树删除在插入的基础上，为保证结点中关键字数>=⌈m/2⌉-1，增加了结点合并的问题

1）当被删关键字a不在最低层非叶结点，可以用a的前驱或后继来代替a，再删除a的前驱或后继

 2）当被删关键字a在终端结点 

①若结点有富余（删除一个key,结点剩余的key数量仍>=⌈m/2⌉-1），则直接删除关键字

②若结点不富余（删除一个key,结点剩余的key数量<⌈m/2⌉-1）,且该结点的兄弟结点关键字数富余，则调整该结点与其兄弟结点和双亲结点（父子换位）达到新的平衡；若兄弟节点也不富余，则将关键字删除后与其兄弟左或右的兄弟结点和双亲结点中的关键字合并

 【注】：合并过程若双亲结点关键字会减1，若双亲结点是根结点且关键字数减少为0，则直接将根结点删除，将合并后的新结点成为根

7.2.4 B+树的基本概念

·Def：一棵 m阶的B+树:

1)每个分支结点最多有m棵子树，结点的子树个数与关键字个数相等。

2)非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2⌉棵子树。

4)所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。

5)所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块) 中关键字的最大值及指向其子结点的指针。

·m阶的B+树与m阶的B树:

1）B+树中具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；

     B树中具有n个关键字的结点含有n+ 1棵子树

2) B+树中每个结点(非根内部结点)的关键字个数n的范围是「m/2⌉≤n≤m (根结点:1≤n≤m);

   B树中，每个结点(非根内部结点)的关键字个数n的范围是「m/2⌉-1≤n≤m-1 (根结点: 1≤n≤m- 1)

3)B+树中叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址

4)B+树中叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；

   B树中叶结点(最外层内部结点)包含的关键字和其他结点包含的关键字是不重复的 

7.3 散列表

7.3.1散列表的基本概念

·散列函数：把查找表中的关键字映射成该关键字对于的地址的函数，记Hash(key)=addr(这里地址可以是数组下标，索引或者内存地址)

·冲突与同义词：散列函数可能会把两个或两个以上的不同关键字映射到同一地址，这种情况称为冲突；这些发生冲突的关键字称为同义词

·散列表：根据关键字直接进行访问的数据结构，散列表中建立了关键字和存储地址之间的一种直接映射关系

7.3.2散列函数的构造方法

·直接定制法

直接取关键字的某个线性函数值为散列地址，散列函数H(key)=key or H(key)=a*key+b

这种方法计算最简单，且不会产生冲突，适用于关键字的分布基本连续的情况，若关键字分布不连续，空位多则容易造成存储空间的浪费

·除留余数法

  假设散列表长为m，取一个不大于m但最接近或等于m的质数p，利用除余的方式将关键字转换为散列地址，散列函数为H(key)=key%p

这种方法的关键是选好p，使得每个关键字通过该函数能等概率的映射到散列空间上的任一地址

7.3.3处理冲突的方法

·开放定址法：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入           Hi=(H(key)+di)%m       i=0,1..k(k<=m-1)

其中，H(key)为散列函数；m表示散列表表长；di为增量序列，增量序列通常有四种取法：

1）线性探测法  d为1，2, ...m-1线性序列,冲突发生时，顺序查看下一个单元，直到找到一个空闲单元或查遍全表

2）平方探测法  d为12-12 22-22, ..-k2二次序列，其中k<=m/2，散列表长度m必须是一个表示成4k+3的素数；这是处理冲突的较好方法，可以避免堆积，但不能探测到表中所有单元

3）再散列法    di=Hash2(key)时，需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用Hash2(key)计算该关键字的地址增量Hi=(H(key)+i*di)%m，其中i是冲突的次数，初始为0，该方法最多经过m-1次探测就会遍历表中所有位置

4）伪随机序列法  d为伪随机数

·拉链法：将相同的Hash地址的记录链成一个单链表，即把所有的同义词存储在一个线性链表中，该方法使适用于经常进行插入和删除的情况

Step1：取数据元素的关键字key,计算其哈希地址，若该地址对应的链表为空,则插入此链表，否则执行Step2解决冲突

Step2:计算关键字key的下一个存储地址，若该地址对应的链表不为空，则利用链表的前插法或后插法将该元素插入此链表

7.3.4散列查找

·查找步骤：

初始化: Addr=Hash (key) ;

1)检测查找表中地址为Addr的位置上是否有记录，若无记录，返回查找失败;若有记录，

比较它与key的值，若相等，则返回查找成功标志，否则执行步骤2;

2)用给定的处理冲突方法计算“下一个散列地址”，并把Addr置为此地址，转入步骤1

·查找效率：

【例】：  现有长度为11 且初始为空的散列表HT，散列函数H(key) = key % 7，采用线性探查法解决冲突。将关键字序列87，40，30，6，11，22，98，20 依次插入HT后，HT的查找失败的平均长度是多少呢？ 查找成功的平均查找长度又是多少呢？

【解】：记录每个字冲突的次数，后面在计算查找成功的平均长度会用到；
    查找失败计算每个查找失败对应地址的查找次数，即从所查位置开始往后直至查到空位置

ASL 查找失败= （9 + 8 + 7 + 6 + 5 + 4 + 3 ）/ 7 = 6

ASL 查找成功= （1 + 1 + 1 + 1 + 1 + 1 + 1 + 2）/ 8 = 9 / 8
 ·影响因素：  散列表的查找效率取决于散列函数，处理冲突的方法和装填因子，其中装填因子=表中的记录数n/散列表长度m，散列表的平均查找长度依赖于装填因子，散列因子越大，表越慢，发生冲突的可能性越大，反之越小