第九章. 查找 （Chapter 9. Searching)

Presentation on theme: "第九章. 查找 （Chapter 9. Searching)"— Presentation transcript:

1 第九章. 查找 （Chapter 9. Searching)
查找运算是计算机中最常用的操作之一。有人统计过，计算机大约有40%的运算是与查找相关的。 关键字（key） 数据元素（或记录）的某个数据项，能用来标识一个数据元素。若能唯一的标识一个数据元素， 则称为主关键字（primary key），反之则为次关键字（secondary key）。 查找表（search table）

2 由同一类型的数据元素（或记录）构成的集合。表中的元素基本上是固定的，这类查找表称为静态查找表（static search table）；若在查找过程中将不存在的元素插入查找表中，则称这类查找表为动态查找表（dynamic search table）。 查找（searching） 根据某个给定的值，在查找表中找寻关键字等于给定值的数据元素（或记录）。若表中存在这样的数据元素，则称查找是成功的，查找结果即为查找到的数据元素；反之则称查找是不成功的，此时查找结果为空。 §9.1 静态表的查找

3 查找表中的各元素（或记录）的关键字的值是无序的。
一、无序表的查找： 查找表中的各元素（或记录）的关键字的值是无序的。 实际查找时，通常将给定值放在第 0 个记录处，然后从后向前查找，直到找到所查记录为止，找不到则返回结果 0。因为记录 0 像哨兵一样看守着查找表下界，所以不会越界。 typedef struct { keytype key; } elemtype; typedef struct { elemtype * elem; int length; } sstable;

4 平均查找长度（average search length）
int seqsearch ( sstable R, keytype K ) { R.elem[0].key := K; for ( i = R.length ; R.elem[i].key != K ; i -- ) ; return i; } 查找性能分析： 平均查找长度（average search length） 为了确定记录在查找表中的位置，需与给定值比较的关键字的个数的期望值称为平均查找长度。

5 对含有 n 个记录的查找表，查找成功时的平均查找长度为： ASL = ∑PiCi ，其中Pi为查找第i个记录的概率，且∑Pi = 1。
在等概率情况下，顺序查找无序表的平均查找长度为： ASL成功 = （n+1) / 和 ASL不成功 = n+1 。 二、有序表的查找： 查找表中的各元素（或记录）的关键字的值是有序的。 这类有序表的查找仍可以用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。

6 在等概率情况下，顺序查找有序表的平均查找长度为： ASL成功 = （n+1) / 2 和 ASL不成功 = （n+2) / 2 。
int seqsearch ( sstable R, keytype K ) { R.elem[0].key := K; for ( i = R.length ; R.elem[i].key > K ; i -- ) ; if (R.elem[i].key=K) return i; else return 0; } 在等概率情况下，顺序查找有序表的平均查找长度为： ASL成功 = （n+1) / 和 ASL不成功 = （n+2) / 2 。 有序表的查找比较好的方法是折半查找（binary search）： 将给定值与中间的记录进行比较，若找到则查找成功；否则若给定值比中间记录小，则对前一半子表进行折半查找，反之则对后一半子表进行折半查找。若在查找过程中，遇到查找子表的上界小于下界，则表示查找失败。

7 int binsearch ( sstable R , keytype K )
{ low = 1; high = R.length; while ( low <= high ) mid = ( low+high ) / 2; if ( R.elem[mid]==K ) return mid; else if ( R.elem[mid] > K ) high = mid-1; else low = mid+1; } return 0;

8 int binsearch ( sstable R , int low, int high, keytype K )
{ if ( low > high ) return 0; mid = ( low+high ) / 2; if ( R.elem[mid]==K ) return mid; if ( R.elem[mid] > K ) return binsearch ( R, low, mid-1, K ); return binsearch ( R, mid+1, high, K ); }

9 查找性能分析： 折半查找每次只查表的一半，其所有记录的查找路径构成一棵二叉树，称为折半查找树（或判定树），每次查找只走了该树的一条分支，故平均查找长度不超过 log2n + 1。 有一组记录的关键字为{1，2，3，4，5，6，7，8}，求其在等概率情况下查找成功的平均查找长度： 例： 4 2 5 1 6 3 7 8 其查找树如左图所示： ASL成功 = = 21 / 8 。 1*1+2*2+3*4+4*1 8

10 有序表的查找也可用其它的查找方法，如费波拉契查找（Fibonacci search）。
设查找表记录数为某个费波拉契数减一，即 n=Fu-1，则可将给定值与第Fu -1个记录比较，若比其小，则在1~ Fu -1-1 记录间查找，否则在Fu -1+1~ Fu-1记录间查找 。如下图所示： 若有序表的关键字是均匀分布的，则还可用插值查找方法，其平均性能在记录数较多时比折半查找好：将给定值先与第 i 个记录比较，则 i = n。 K- r[L].key r[H].key- r[L].key 4 2 5 1 6 3 7

11 作 业 25. 查找序列以带头结点的单链表表示，各结点中设一个访问频度，初始值为 0，每次查找成功后该结点频度值增加 1。试给出算法，在每次查找后查找序列均按访问频度从大到小排列。

12 三、静态树表的查找： 前面介绍的有序表查找都是在“等概率”情况下的，若在非等概率情况下应该怎样查找才能使查找效率更高了？ 查找效率最高即平均查找长度最小，根据前面所学知识，我们可以给出有序表在非等概率情况下应遵循的两个原则： 1、最先访问的结点应是访问概率最大的结点； 2、每次访问应使结点两边尚未访问的结点的被访概 率之和尽可能相等。

13 这两个原则可用一句话来表示，即判定树为带权内路径长度之和最小的二叉树，亦即：
PH = ∑wihi 最小，其中 n 为有序表长度，hi 为第 i 个 结点在判定树上的层次数，wi = cpi，c 为某个常数，pi i =1 n 为第 i 个结点的查找概率。 这样的树称为静态最优查找树（static optimal search tree），构造这样一棵树的时间代价太大，亦即时间复杂度很大，因此我们通常是构造次优查找树（nearly optimal search tree），构造它的时间代价远远低于构造最优查找树，但查找性能只比最优查找树差1%~2%，很少差3%以上。

14 { 次优查找树的构造： 设有序表每个记录的权值为 wl,wl+1,…,wh，第一个应访问的结点号为 i ，则有：
Δpi = ∑wj - ∑wj 最小，即 Δpi = Min {Δpj } 再分别对 {rl,rl+1,…,ri-1} 和 {ri+1,ri+2,…,rh} 分别构造次优查找树。 j =i +1 j =l h i - l l≤j≤h 为便于计算，引入累计权值swi=∑wj，并设wl-1=swl-1=0，则： j=l i ∑wj j =i +1 h j =l i -1 swi-1 - swl-1 = swh - swi = { Δpi = | swh + swl-1 - swi - swi-1 |

15 由于在构造次优查找树时没有考虑前面说的原则一，因此被选为根的结点的权值可能比其邻近结点的权值小，此时应对查找树作适当的调整，将相邻权值大的结点作为根结点。
次优查找树的查找方法与折半查找类似，其平均查找长度与 log n 成正比。 四、索引顺序表的查找： 有一些顺序表是带索引表的，这类表通常称为索引顺序表。一般的，索引顺序表的索引部分一定是有序的，故这部分可用折半查找等方法；但顺序表本身则不一定有序，因此，可根据顺序表是否有序而选用相应的查找方法。这种将索引部分和表体部分分开查找的方法称为分块查找（blocking search）。索引表如下图所示，其平均查找长度为两部分查找之和。

16 35 68 93 1 10 13 最大关键字 起始地址 索引表 23 16 11 6 28 31 25 19 41 57 75 88 69 3 2 4 5 7 8 9 12 14 15 顺序表 §9.2 动态表的查找 一、二叉排序树： 二叉排序树（binary sort tree）或者为空树，或者为这样一棵树：根结点的左子树的所有结点的关键字值均比根结点的关键字值小；根结点的右子树的所有结点的关键字值均比根结点的关键字值大；根结点的左右子树也是二叉排序树。

17 例： 二叉排序树是动态查找树，即在查找时将未找到的给定值的记录插入到查找树中，查找树是动态生成的。
有查找请求 {54、32、54、25、73、25、94、68、32、73、9}，查找结果如下： 例： 54 查找失败 查找失败 查找成功 32 73 查找失败 查找失败 查找成功 25 94 68 查找失败 查找失败 查找成功 查找成功 查找失败 9

18 作 业 26. 试给出判别一棵给定的二叉树是否是排序二叉树的算法，设二叉树以二叉链表表示。

19 二叉排序树的查找：若当前结点指针为空或当前结点为所找结点则返回当前指针；若当前结点关键字值比给定值大则继续查找当前结点的左子树；否则就继续查找当前结点的右子树。
二叉排序树的插入：先用给定值查找二叉排序树，查找成功则返回所找结点指针；否则在找不到时的叶结点的左子树或右子树处插入给定值记录。（新插入的结点一定是叶子结点） 二叉排序树的删除：若将删除的结点是叶子结点，直接删除即可；若将删除的结点只有左子树或只有右子树，则可用左孩子或右孩子直接替换将要删除结点位置；若将删除的结点左、右子树均存在，则可用将要删除结点左子树的最右结点（关键字值最大的结点）替换将要删除结点，用替换结点的左子树（若存在）替换“替换结点”。

20 二叉排序树的查找分析：ASL与二叉排序树的高度有关。由于二叉排序树是根据查找请求序列建立的，因此很可能退化成为线性表（什么情况下？），如何解决这一问题呢？
二、平衡二叉树： 平衡二叉树（balanced binary tree) 又称 AVL树(G. M. Adelson-Velskii & Y. M. Landis. An algorithm for the organization of information. Soviet Math. Dokl., 3: , 1962.) ，它具有如下性质：或者为空树，或者根结点的左、右子树也均为平衡二叉树，且左、右子树的树高之差的绝对值不超过1。 平衡因子（balance factor）：结点的左子树高度减去右子树高度的值称为该结点的平衡因子。因此平衡二叉树也可以这样定义：平衡二叉树是所有结点的平衡因子的绝对值均小于2的二叉树。

21 我们谈论的平衡二叉树其实是平衡二叉排序树。
平衡二叉树的插入： 平衡二叉树插入时分为四种类型：LL型、LR型、RL型和RR型。 1、将新的结点插入在平衡二叉树中，沿着刚插入的结点到根结点的路径修改所经过结点的平衡因子，直到找到某结点A 的 平衡因子为 2 或修改完根结点的平衡因子后仍为平衡二叉树。 2、若结点A 的平衡因子为2 ，则需进行调整，设 A 的儿子和孙子（刚经过的结点）分别为 B 和 C，则有：

22 A B C LR -1 2 RL 1 -2 LL RR #

23 有一组关键字序列{JAN、FEB、MAR、APR、MAY、JUN、JUL、AUG、SEP、OCT、NOV、DEC}，以此建立 AVL 树。
例： JAN FEB 2 FEB MAR APR -1 APR JUN MAY JAN FEB MAR APR MAY JUN JUL AUG AUG AUG JUL MAY -2 LR SEP 1 SEP OCT OCT

24 -2 SEP OCT FEB MAR APR MAY JUN JUL AUG MAR -1 RL OCT 1 NOV NOV SEP OCT
JAN -2 SEP OCT JAN FEB MAR APR MAY JUN JUL AUG MAR -1 RL OCT 1 NOV NOV SEP OCT JAN FEB MAR APR MAY JUN JUL AUG RR DEC

25 第 五 次 上 机 作 业 输入一组关键字序列，并以此顺序建立一棵平衡二叉树（提示：为简化运算，可采用含有左、右子树高度和指向父母的指针的三叉链表表示），并在建树过程中用逆中序法输出每次插入新结点后的平衡二叉树形状。

26 平衡二叉树的查找分析： 含有 n 个关键字的平衡二叉树的最大深度为多少？ 用 Nh 表示深度为 h 的平衡二叉树含有的最少结点数，则：N0 = 0、N1 = 1、N2 = 2、…、Nh = Nh -1 + Nh = φh+2/√5-1，其中φ = （1 +√5 ）/ 2，则含有 n 个结点的平衡二叉树的最大深度为 logφ(√5 ( n + 1)) - 2，因此，平衡二叉树查找的时间复杂度为 O ( log n )。 三、B 树 B 树是一种平衡的多路查找树，主要应用在文件系统中。一棵 m 阶的 B 树，或为空树，或为满足下列特性的 m 叉树： 、树中每个结点最多有 m 棵子树； 、若根结点不是叶子结点，则最少有两棵子树；

27 3、除根之外的所有非终端结点最少有 m / 2 棵子树；4、所有非终端结点包含 （n,A0,K1,A1,K2,…,Kn,An）信息数据； 5、所有叶子结点在同一层上，且不带信息。
其中n为结点中关键字个数，Ai为指向子树的指针，Ki为关键字。 B 的查找： B 树是一棵平衡的多路排序树，只是每个结点的关键字不只一个，因此整棵树的查找方法与二叉排序树的查找相似，只需对每个结点内部实行顺序查找。 具有 N 个关键字的 B 树深度不超过 ( log m / 2 ( N+1 ) / 2 ) + 1。

28 B 的插入和删除： B 树的插入也是从空树开始，每次关键字插在最靠近叶子的非终端结点中，若该结点插入后关键字个数不超过 m-1 ，则插入完毕；否则需将该结点从中间分裂为两个结点，将居中关键字送往上一层（父母结点）中；再对上一层结点做同样处理，直至每个结点的关键字数均不超过 m-1 为止。 B 树的删除比较复杂，有时还需进行结点合并，分三种情况： 1、被删关键字所在结点的关键字个数≥ m / 2 ，则直接从该结点中删除该关键字即可；

29 2、被删关键字所在结点的关键字个数 = m / ，而与该结点相邻的兄弟结点的关键字个数 ≥ m / 2 ，则需将其兄弟结点中靠近该结点的关键字上移至父母结点中，再从父母结点中下移一个紧挨刚才上移关键字的关键字到该结点中，然后从该结点中删去该关键字即可； 3、被删关键字所在结点及其相邻的兄弟结点的关键字个数均等于 m / ，设其父母结点指向其兄弟结点的指针为 Ai ，则从该结点中删除该关键字后，将该结点中剩余的关键字和父母结点中的 Ki 关键字一起合并到其右兄弟（无右兄弟则为左兄弟）结点中即可。 四、B + 树： B+ 树是B 树的变形，广泛应用在文件系统中，特别是数据库的 VSAM 文件系统中。

30 一棵 m 阶 B+ 树与一棵 m 阶 B 树的不同之处在：
1、有 n 棵子树的结点中有 n 个关键字； 2、所有叶子结点中包含了全部关键字的信息及指向这些关键字记录的指针，且叶子结点以关键字大小自小至大顺序链接； 3、所有非终端结点可以看成是索引部分，其中只含有其子树中最大（或最小）关键字。 其实 B+ 树已不是一棵真正意义上的树型结构了，其终端结点已连成了线性有序表。

31 五、键树： 键树（key tree）又称数字查找树（digital search tree），它的每个结点只包含组成关键字的字符或数字。键树主要用来存储一些关键字表或标识符表，有利于这些关键字的查找。 键树的常用存储方式有两种： 、孩子兄弟的二叉树表示法（双链树）； 、多重链表表示法（Trie 树）。

32 作 业 27. 试从空树开始，按以下顺序向2-3树中插入关键字建树：20，30，50，52，60，68，70。如果此后再删去50和68，画出每一步执行后的状态。

33 §9.3 散列表查找 前面所介绍的查找方法的查找效率各不相同，且相适应的查找表也不一样，但都有一个共性，即平均查找长度不会为 1。那么有没有办法使平均查找长度等于 1，即一次查找成功呢？ 散列表（Hash table）的查找就是为了解决这个问题而提出的。 散列表是如此构造的：给定一个线性表空间，选取一 个自变量为关键字的映射函数，其函数值为关键字在线性表空间中的存储位置，关键字经该函数映射后即可存储到线性表空间中；查找时也用相同的方法即可找到该记录。

34 该线性表空间即称为散列表（也叫哈稀表），所选取的函数称为散列函数（Hash function），得到的函数值称为散列地址，得到散列地址的过程称为哈稀造表或散列。
理论上散列表查找成功的平均查找长度 ASL成功 = 1。 但实际上经常会遇见这样的情况：不同的两个关键字经过散列函数运算后所得到的散列地址相同，这种现象称为冲突（collision），而产生冲突的两个关键字对该散列函数而言称为同义词（synonym）。 我们应尽可能选取冲突少的散列函数，但不能完全避免冲突的产生，而有了冲突就需要找相应的解决办法。

35 散列函数的构造方法： 构造散列函数的方法很多，原则是希望构造的散列函数是均匀的（uniform），亦即经散列函数映象到地址集合中的任何一个地址的概率是相等的，这样做能尽可能减少冲突。 最常用的散列函数构造方法有以下几种： 1、直接定址法：H( key ) = a * key + b， a、b为常数； 2、数字分析法：分析关键字，找出其中几位数字作散列地址； 3、平方取中法：关键字平方后中间几位数字与所有数字相关，可选取来作为散列地址；

36 4、折叠法：将关键字分割成位数相同的几部分相叠加作为散列地址；
5、除留余数法：H( key ) = key MOD p， p≤m，m 为比散列表长度小的数； 6、伪随机数法：选取一个用关键字作为种子的伪随机数发生器生成散列地址。 解决冲突的方法： 与构造散列函数一样，解决冲突的方法也很多，原则是尽可能避免产生二次聚集的情况——不同散列地址的记录间因解决冲突而产生新的冲突的现象。 最常用的解决冲突方法有以下几种：

37 1、开放定址法：Hi =(H(key) + di) MOD m, i = 1,2,…, k (k<m)；其中 H(key) 为散列函数，m 为散列表长，di 为增量序列，取值为：①、 di =1,2,…,m-1，称为线性探测（linear probing）再散列； ②、 di = 12, -12,22, -22,…,k2 ( k≤m/2 )，称为二次探测（quadratic probing）再散列； ③、 di = 伪随机数，称为伪随机探测（random probing）再散列； 2、再散列法：Hi =RHi(key), i =1,2,…,k，RHi为不同的散列函数； 3、链地址法：散列表设立指针，将所有散列地址为此位置的关键字记录用单链表形式存储起来； 4、公共溢出区法：建立公共溢出区，将所有发生冲突的关键字记录存储到公共溢出区中去。

38 散列函数的查找及分析： 散列表的查找过程与散列表的建立过程相同：利用建表时的散列函数和解决冲突的方法，逐步去进行查找，直到找到该记录或找不到该记录（该单元为空或空指针）为止。 因此，在删除记录时，不是将该位置置为空，而是将其置为“被删除”，否则查找链就会断。 一般的，关键字数目一定，散列表空间越大，冲突相对越少。 装填因子（load factor）： α = ———————— 表中填入的记录数 散列表长度

39 即α越小，发生冲突的可能性就越小； α越大，发生冲突的可能性就越大。
理论上查找成功的平均查找长度为： 线性探测再散列： ASL ≈ ( / ( 1 - α)) / 2 二次探测、伪随机再散列、再散列： ASL ≈ - ln ( 1 - α) / α 链地址： ASL ≈ 1 + α/ 2 理论上查找不成功的平均查找长度为： 线性探测再散列： ASL ≈ ( / ( 1 - α) 2 ) / 2 二次探测、伪随机再散列、再散列： ASL ≈ 1 / ( 1 - α) 链地址： ASL ≈ α + e -α

40 有一组关键字序列（38、59、125、168、216、719、455、20），用函数 H(key) = key MOD 10 将其按顺序散列到散列表 HT(0:9) 中，分别用三种方法解决冲突：线性再探测法、链地址法、公共溢出区法，画出这三种方法建立的散列表，并分别求在等概率情况下查找成功和不成功的平均查找长度。 例： 1、 1 2 3 4 5 6 7 8 9 168 719 20 125 216 455 38 59 719 20 20 455 455 168 168 719 ASL成功 = ————————— = —— = 2 8 16 ASL不成功 = —————————— = —— = 4.6 10 46

41 2、 ∧ 1 2 3 4 5 6 7 8 9 20 ∧ 125 ∧ 216 ∧ 38 ∧ 59 ∧ 455 ∧ 168 ∧ 719 ∧ ASL成功 = ————————— = —— 8 11 ASL不成功 = —————————— = —— = 1.8 10 18

42 3、 1 2 3 4 5 6 7 8 9 20 125 216 38 59 455 168 719 1 2 3 4 5 公共溢出区： 168 719 455 719 455 455 ASL成功 = ————————— = —— 8 14 ASL不成功 = —————————— = —— = 3 10 30

43 作 业 28. 在地址空间为0~16的散列区中，对关键字序列（Jan、Feb、…、Dec）造两个哈稀表：H(x) = i div 2 ，其中 i 为关键字中第一个字母在字母表中的序号，分别用线性探测法和链地址法处理冲突，并分别求这两个哈稀表在等概率情况下查找成功、不成功时的平均查找长度。