Chapter 7 Search

所谓搜索，就是在数据集合中寻找满足某种条件的数据对象 1.搜索成功 即找到满足条件的数据 对象这时, 作为结果, 可报告该对 象在结构中的位置, 还可给出该对 象中的具体信息 2.搜索不成功 或搜索失败。作为结 果, 应报告一些信息, 如失败标 志、位置等

通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成 在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不唯一

实施搜索时有两种不同的环境 静态环境 搜索结构不用插入和删除操作  静态搜索表 静态环境 搜索结构不用插入和删除操作  静态搜索表 动态环境 为保持较高的搜索效率, 搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化  动态搜索表

查找算法的评价指标 查找成功:最少比较次数 最多比较次数 平均比较次数 查找失败:最少比较次数

顺序查找 以顺序表或线性链表表示静态查找表

顺序查找过程 k k ST.elem 假设给定值 e=64, 要求 ST.elem[k] = e, 问: k = ?

i i ST.elem 64 key=64 i i ST.elem 60 key=60

int Search_Seq( TB ST, TYPE key ) { ST.elem[0].key = key; // “哨兵” for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时，i为0 }

分析顺序查找的 时间性能

(Average Search Length) 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需 和给定值进行比较的关键字个数的期望 值

其中: n 为表长，Pi 为查找表中第i个记录的概率，且 　 ， Ci为找到该记录时，曾和给定值比较过的关键字的个数

在等概率情形　pi = 1/n, i = 1, 2, , n 在搜索不成功情形，ASLunsucc = n+1

　查找成功:最少比较次数　 1 最多比较次数　 n　 平均比较次数 (n+1)/2 查找失败:最少比较次数 n+1 最多比较次数 n+1 平均比较次数 n+1

Key Denition in C++ To select existing types as records and keys, a client could use type denition statements such as: typedef int Key; typedef int Record; A client can design new classes that display appropriate behavior based on the following skeletons:

// Definition of a Key class: class Key{ public: // Add any constructors and methods for key data. private: // Add declaration of key data members here. }; // Declare overloaded comparison operators for keys. bool operator ==(const Key &x, const Key &y); bool operator > (const Key &x, const Key &y); bool operator < (const Key &x, const Key &y); bool operator >=(const Key &x, const Key &y); bool operator <=(const Key &x, const Key &y); bool operator !=(const Key &x, const Key &y); // Definition of a Record class: class Record{ Key Key(); // implicit conversion from Record to Key. // Add any constructors and methods for Record objects. // Add data components.

Sequential Search and Analysis Begin at one end of the list and scan down it until the desired key is found or the other end is reached: Error_code sequential_search(const List<Record> &the_list, const Key &target, int &position) /* Post: If an entry in the_list has key equal to target, then return success and the output parameter position locates such an entry within the list. Otherwise return not_present and position becomes invalid. */ { int s = the_list.size(); for (position = 0; position < s; position++) { Record data; the_list.retrieve(position, data); if (data == target) return success; } return not_present;

折半查找 若以有序表表示静态查找表， 适用于表长较大的查找表 则查找过程可以基于“折半”进行 上述顺序查找表的查找算法简单，但平均查找长度较大，特别不 适用于表长较大的查找表 若以有序表表示静态查找表， 则查找过程可以基于“折半”进行

基于有序顺序表的折半搜索 设n个对象存放在一个有序顺序表中，并按其关键码从小到大排好了序 折半搜索时, 先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较

1.Element[mid].key==x 搜索成功 如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败

例如: key=64 的查找过程如下 mid = (low+high)/2 Low 指示查找区间的下界 high 指示查找区间的上界 ST.length ST.elem low low high high mid mid mid mid = (low+high)/2 Low 指示查找区间的下界 high 指示查找区间的上界

搜索成功的例子 -1 0 1 3 4 6 8 10 12 6 0 1 2 3 4 5 6 7 8 搜索 low mid high 6 8 10 12 5 6 7 8 5

搜索失败的例子 -1 0 1 3 4 6 8 10 12 5 0 1 2 3 4 5 6 7 8 搜索 low mid high 6 8 10 12 5 6 7 8 6

int Search_Bin(TB ST, TYPE key) { low = 1; high = ST.length; while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key)return mid; if(key<ST.elem[mid].key)high=mid-1; if(key>ST.elem[mid].key)low=mid+1; } return 0;

有序顺序表的折半搜索的判定树 ( 10, 20, 30, 40, 50, 60 ) 10 50 = 30 < > 20 40

索引顺序查找 1）由索引确定记录所在区间 2）在顺序表的某个区间内进行查找 可见: 索引顺序查找的过程也是一个 “缩小区间”的查找过程 注意：索引可以根据查找表的特点来构造

索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度 对于按顺序索引表的平均查找长度:

二叉排序树 （二叉查找树）

二叉排序树或者是一棵空树；或者 是具有如下特性的二叉树 （1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值 （2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值 （3）它的左、右子树也都分别是二叉 排序树

50 30 80 20 40 90 10 25 35 85 66 23 88 不 是二叉排序树

二叉排序树的 查找算法

若二叉排序树为空，则查找不成功 否则: 1）若给定值等于根结点的关键字， 则查找成功 2）若给定值小于根结点的关键字， 则继续在左子树上进行查找 3）若给定值大于根结点的关键字， 则继续在右子树上进行查找

50 50 50 50 50 50 30 30 80 80 20 40 40 90 90 35 35 85 32 88 查找关键字 == 50 , 35 , 90 , 95

n 个结点的二叉搜索树的数目 3 个结点的二叉搜索树 {123} {132} {213} {312} {321} 1 2 3

如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树

在查找过程中，生成了一条查找路径 ——查找成功 或者 ——查找不成功 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止 ——查找不成功

f f T key = 48 22 f T f f T f T p 30 T 20 40 T f 10 25 35 p T f 23 T

搜索28 搜索失败 搜索45 搜索成功 35 15 45 10 25 40 50 20 30

查找性能的分析 均可按照平均查找长度的定义来求它 的 ASL 值，显然，由值相同的 n个关 键字，构造所得的不同形态的各棵二 对于每一棵特定的二叉排序树， 均可按照平均查找长度的定义来求它 的 ASL 值，显然，由值相同的 n个关 键字，构造所得的不同形态的各棵二 叉排序树的平均查找长 度的值不同， 甚至可能差别很大

由关键字序列 1，2，3，4，5构造而得的二叉排序树 ASL =（1+2+3+4+5）/ 5 = 3 3 4 5 由关键字序列 3，1，2，5，4构造而得的二叉排序树 3 ASL =（1+2+3+2+3）/ 5 = 2.2 1 5 2 4

输入数据，建立二叉搜索树的过程 输入数据 { 53, 78, 65, 17, 87, 09, 81, 15 } 53 78 65 17 87

如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大 同样 3 个数据{ 1, 2, 3 }，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能 如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大

{1,2,3} {1,3,2} {2,1,3} {3,1,2} {3,2,1} 1 2 3

二叉平衡树 （AVL树）

一棵AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1 不平衡 平衡 A C B A D C B E D E

结点的平衡因子 (balance factor) 每个结点附加一个数字, 给出该结点左子树的高度减去右子树的高度所得的高度差, 这个数字即为结点的平衡因子 AVL树任一结点平衡因子只能取 -1, 0, 1

如果一个结点的平衡因子的绝对值大于1, 则这棵二叉搜索树就失去了平衡, 不再是AVL树 如果一棵二叉搜索树是平衡的, 且有 n个结点，其高度可保持在 O(log2n),平均搜索长度也可保持在O(log2n)

5 5 4 8 4 8 2 2 是平衡树 不是平衡树 1

平衡化旋转 如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化 平衡化旋转有两类： 单旋转 (左旋和右旋) 双旋转 (左旋加右旋和右旋加左旋)

右单旋转 LL型 左单旋转 RR型

左右双旋转 LR型 右左双旋转 RL型

构造二叉平衡（查找）树的方法 在插入过程中，采用平衡旋转技术 依次插入的关键字为5, 4, 2, 8, 6, 9 向右旋转 一次 先向右旋转 再向左旋转 6

向左旋转一次 4 2 6 5 8 6 9 4 8 继续插入关键字 9 2 9 5

B - 树

B-树是一种 平衡 的 多路 查找 树

n 个关键字 Ki（1≤ i≤n） n<m n 个指向记录的指针 Di（1≤i≤n） n+1 个指向子树的指针 Ai（0≤i≤n） 在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字 Ki（1≤ i≤n） n<m n 个指向记录的指针 Di（1≤i≤n） n+1 个指向子树的指针 Ai（0≤i≤n） 多叉树的特性

非叶结点中的多个关键字均自小至大有序排列，即：K1< K2 < … < Kn Ai-1 所指子树上所有关键字均小于Ki Ai 所指子树上所有关键字均大于Ki 查找树的特性

树中所有叶子结点均不带信息，且在树中的同一层次上 根结点或为叶子结点，或至少含有两棵子树 其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树 平衡树的特性

查找过程 从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程交叉进行

若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置 若查找不成功，则返回插入位置

B+树 是B-树的一种变型

※ 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点

※ 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值 ※ 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间

查找过程 ※ 在 B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找 ※ 在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束 ※若在结点内查找时， Ki-1 ＜给定值≤Ki，则应继续在 Ai 所指子树中进行查找

root 50 96 15 50 62 78 96 sq 20 26 43 50 56 62 3 8 15 71 78 84 89 96

哈 希 查 找 (Hash)

以上讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系

查找的过程为给定值依次和关 键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数

用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同

对于频繁使用的查找表，希望 ASL = 0 只有一个办法：预先知道所查关键字在表中的位置 即，要求：记录在表中位置和其关键字之间存在一种确定的关系

在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 H(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 H(key) 为哈希函数

※哈希函数是一个映象，即：将关键 字的集合映射到某个地址集合上，它 的设置很灵活，只要这个地址集合的 大小不超出允许范围即可

※由于哈希函数是一个压缩映象，因 此，在一般情况下，很容易产生 “ 冲 突 ” 现象，即： key1 key2，而 H(key1) = H(key2)

※很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生

因此，在构造这种特殊的“查 找表”时，除了需要选择一个好” ( 尽可能少产生冲突 )的哈希函数 之外；还需要找到一种“处理冲突” 的方法

哈希表的定义 根据设定的哈希函数 H( key ) 和所选处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 ( 区间) 上，并以关键字在地址集中的“映象”作为相应记录在表中的存储位置，如此构造所得的查找表称为“哈希表”

构造哈希函数的方法 对数字的关键字可有下列构造方法 数字分析法 直接定址法 平方取中法 除留余数法 折叠法 随机数法 若是非数字关键字，则需先对其进行数字化处理

数字分析法

此方法适合于： 能预先估计出全体关键字的每一位 上各种数字出现的频度 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址 此方法适合于： 能预先估计出全体关键字的每一位 上各种数字出现的频度

平方取中法

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响 此方法适合于: 关键字中的每一位都有某些数字重 复出现频度很高的现象

折叠法

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加 此方法适合于: 关键字的数字位数特别多

直接定址法

哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a  key + b 此法适合于： 地址集合的大小 = = 关键字集合的大小

除留余数法

H(key) = key MOD p 其中， p≤m (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子 设定哈希函数为: H(key) = key MOD p 其中， p≤m (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子

随机数法

设定哈希函数为: H(key) = Random(key) 其中，Random 为伪随机函数 的关键字构造哈希函数 通常，此方法用于对长度不等 的关键字构造哈希函数

实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小

处理冲突的方法 “处理冲突” 的实际含义是 为产生冲突的地址寻找下一个哈希地址 1. 开放定址法 2. 链地址法

开放定址法(闭域法) 为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤ s≤m-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, …, s

增量 di 的三种取法

1)线性探测再散列 di = c i 最简单的情况 c=1 di=i×H2(key) (又称双散列函数探测)

{ 19, 01, 23, 14, 55, 68, 11, 82, 36 } H(key) = key MOD 11 采用线性探测再散列处理冲突 55 01 23 14 68 11 82 36 19 1 1 2 1 3 6 2 5 1

链地址法(开域法) 将所有哈希地址相同的记录都链接在同一链表中

{ 19, 01, 23, 14, 55, 68, 11, 82, 36 } H(key) = key MOD 7 1 2 3 4 5 6  14  01 36  23   11  19 68 82  55

哈希表的查找

对于给定值 K， 计算哈希地址 i = H(K) 若 r[i] = NULL 则查找不成功 若 r[i].key = K 则查找成功 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为： 对于给定值 K， 计算哈希地址 i = H(K) 若 r[i] = NULL 则查找不成功 若 r[i].key = K 则查找成功 否则 “求下一地址 Hi” ，直至 r[Hi] = NULL (查找不成功) 或 r[Hi].key = K (查找成功) 为止

//--- 开放定址哈希表的存储结构 --- Template <class ElemType > class HashTable{ public: Error_Code SearchHash (KeyType K,int &p, int &c); //其它公有函数成员 private: ElemType *elem; int count; // 当前数据元素个数 //如下加函数函数成员 };

while (elem[p].key != NULLKEY && !EQ(K, elem[p].key)） Template <class ElemType > Status HashTable ::SearchHash (KeyType K, int &p, int &c) { // 在开放定址哈希表H中查找关键码为K的记录 } p = Hash(K); // 求得哈希地址 while (elem[p].key != NULLKEY && !EQ(K, elem[p].key)） collision(p, ++c); // 求得下一探查地址 p if (EQ(K, elem[p].key)) return SUCCESS; // 查找成功，返回待查数据元素位置 p else return UNSUCCESS; // 查找不成功

哈希表查找的分析 从查找过程得知，哈希表查找的平均查找长度实际上并不等于零

决定哈希表查找的ASL的因素 1) 选用的哈希函数； 2) 选用的处理冲突的方法； 1) 选用的哈希函数； 2) 选用的处理冲突的方法； 3) 哈希表饱和的程度，装载因子 α=n/m 值的大小（n—记录数， m—表的长度）

一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素

可以证明：查找成功时平均查找长度有下列结果: 线性探测再散列 随机探测再散列 链地址法

从以上结果可见： —— 这是哈希表所特有的特点 哈希表的平均查找长度是  的函数，而不是 n 的函数 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子  ，使得平均查找长度限定在某个范围内 —— 这是哈希表所特有的特点

哈希表也可以用来构造静态查找表 并且，对静态查找表，有时可以找到不发生冲突的哈希函数。即，此时的哈希表的 ASL=0, 称此类哈希函数为理想（perfect）的哈希函数