2009/12/29 数据结构 查找 第九章查找 重点：掌握顺序查找、折半查找、二叉排序 主讲：张昱 树上查找以及散列表上查找的基本思想和算 yuzhang@ustc.edu 法实现。 0551-3603804 难点：二叉排序树的删除算法及B-树上的插 入和副除算法。 1/103 2/10B 第九章查找 9.0一些定义：查找表 9.0二些定义 ■查找表(Search Table) ·定义：由同一类型的数据元素（或记录）构成的 9.1静态查找表 集合。 9.2劲态查找表 “集合”中的数据元素之间存在着完全松散的 关系查找表是一种非常灵便的数据结构 9.3哈希表 ·操作 。查询某个“特定的”数据元素是否在查找表中： ,检索某个“特定的”数据元素的各种属性； 3103 4103 图 生9.0一些定义：查找表及其分类 9.0一些定义-关键字 。操作 ■关键字 。在查找表中插入一个数据元素： ·定义：是数据元素（或记录）中某个数据项 。从查找表中副去某个数据元素。 的值，用以标识（识别）一个数据元素（或 。查找表的分类 记录)。 ,静态查找表：仅作查询和检索操作的查找表。 ·若此关键字可以唯一地标识一个记录，则称 ,动态查找表：在查询过程中同时擂入查找表中不 之为主关键字： 存在的数据元素，或者从查找表中副除已存在的 :若此关键字能识别若干记录，则称之为次关 莱个数据元素。 健字。 5/10 合 610 圄 1
2009/12/29 1 数据结构——查找 1/103 主讲：张昱 yuzhang@ustc.edu 0551-3603804 第九章 查找 2/103 重点：掌握顺序查找、折半查找、二叉排序 树上查找以及散列表上查找的基本思想和算 法实现。 难点：二叉排序树的删除算法及B-树上的插 入和删除算法。 第九章 查找 9.0 一些定义 9.1 静态查找表 3/103 9.2 动态查找表 9.3 哈希表 9.0 一些定义-查找表 查找表(Search Table) 定义：由同一类型的数据元素(或记录)构成的 集合 4/103 。 “集合”中的数据元素之间存在着完全松散的 关系查找表是一种非常灵便的数据结构 操作 查询某个“特定的”数据元素是否在查找表中； 检索某个“特定的”数据元素的各种属性； 9.0 一些定义-查找表及其分类 操作 在查找表中插入一个数据元素； 从查找表中删去某个数据元素。 5/103 查找表的分类 静态查找表：仅作查询和检索操作的查找表。 动态查找表：在查询过程中同时插入查找表中不 存在的数据元素，或者从查找表中删除已存在的 某个数据元素。 9.0 一些定义-关键字 关键字 定义：是数据元素（或记录）中某个数据项 的值，用以标识（识别）一个数据元素（或 6/103 的值，用以标识（识别） 个数据元素（或 记录）。 若此关键字可以唯一地标识一个记录，则称 之为主关键字； 若此关键字能识别若干记录，则称之为次关 键字
2009/12/29 9.0一些定义-查找 9.0一些定义-类型定义 。查找 typedef struct ·定义：根据给定的某个值，在查找表中确定一 KeyType key;关键字域 个其关健字等于给定值的记录或数据元素。 其它域 }ElemType; 若查找表中存在这样一个记录，则称查找 是成功的，此时查找结果为给出整个记录的信 根据具体的关键字类型，定义用于比较的、带参的宏 息，或指示该记录在查找表中的位置： #define EQ(a,b)... #define LT(a,b).… 否则称查找不成功，此时查找结果可给出 #define LQ(a,b)... 一个空记录或空指针。 7103 图 8/10 圄 戴帽时像D:具有相同特性的嫩元素的桌合。 9.1静态查找表 数关暴R:元素同属 一个桌合。 盖本操作P: Create(&ST,n) ▣抽象数据类型定义 操作结果：构造一个含个数拥元素的牌态查找表ST. Destroy(&ST) 。9.1.1顺序查找 初始条件，静态查找表ST存在 ,9.1.2有序表的查找 操作结果：轴服表ST. Search(ST,key) ·折半查控 初始条件静志查找表ST存在，key为和关幢字类型相同的始定值。 ,望波拉奥查找、播值查找 操作结果，若ST中存在其关能李等于key的数婚元来，则图数值为该 元素的值或在妻中的位置，否则为空” ■9.1.3整态树表的查找 Traverse(ST,Visit()) 。9.1.4索引顺序表的查找（分块查找】 初始条件静达查找表ST存在，Vs北是对元求作的应用西 操作结果：按某种洗序对5T的每个元家调用函数Vst)一次且仅一 次。一且Vst)失收，则操作失收 9110g 10/103 9.1.1顺序查找(1) 9.1.1顺序查找(2) 。查找表纳构：以顺序表或线性链表表示 ·对顺序麦的顺序查找 。基本思想：从一增开始向另一增，逐个进行记录的关健字 typedef struct( 和给定值的比较，若某个记录的关键字和给定值比校相等， ElemType*elem;数据元素存情空间蓬址 则查找成功：反之，若直至另一嘴，其关健字和给定值比 int length; 表长度 较都不等，则表明表中没有所查记录，查找不成功。 )SSTable; 查找成功示例： (34,44,4312,53,55,73,6477,kcy=64 查找不成功示例： 34,44,43,12,53,55,73,64,77,key=88 1y103 12/103 图 2
2009/12/29 2 9.0 一些定义-查找 查找 定义：根据给定的某个值，在查找表中确定一 个其关键字等于给定值的记录或数据元素 7/103 。 若查找表中存在这样一个记录，则称查找 是成功的，此时查找结果为给出整个记录的信 息，或指示该记录在查找表中的位置； 否则称查找不成功，此时查找结果可给出 一个空记录或空指针。 9.0 一些定义-类型定义 typedef struct { KeyType key; //关键字域 …… //其它域 8/103 } ElemType; 根据具体的关键字类型, 定义用于比较的、带参的宏 #define EQ(a, b) … #define LT(a, b) … #define LQ(a, b) … 9.1 静态查找表 抽象数据类型定义 9.1.1 顺序查找 912 有序表的查找 9/103 9.1.2 有序表的查找 折半查找 斐波拉契查找、插值查找 9.1.3 静态树表的查找 9.1.4 索引顺序表的查找(分块查找) ADT StaticSearchTable{ 数据对象D:具有相同特性的数据元素的集合。 数据关系R:数据元素同属一个集合。 基本操作P: Create(&ST, n) 操作结果：构造一个含n个数据元素的静态查找表ST. Destroy(&ST) 初始条件：静态查找表ST存在. 操作结果：销毁表ST. 10/103 Search(ST, key) 初始条件：静态查找表ST存在，key为和关键字类型相同的给定值. 操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该 元素的值或在表中的位置，否则为“空”. Traverse(ST,Visit()) 初始条件：静态查找表ST存在,Visit是对元素操作的应用函数. 操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一 次。一旦Visit()失败，则操作失败. } ADT StaticSearchTable 9.1.1 顺序查找(1) 查找表结构：以顺序表或线性链表表示 基本思想：从一端开始向另一端，逐个进行记录的关键字 和给定值的比较，若某个记录的关键字和给定值比较相等， 11/103 则查找成功；反之，若直至另一端，其关键字和给定值比 较都不等，则表明表中没有所查记录，查找不成功。 查找成功示例： (34, 44, 43, 12, 53, 55,73, 64, 77)，key = 64 查找不成功示例： (34, 44, 43, 12, 53, 55,73, 64, 77)，key = 88 9.1.1 顺序查找(2) 对顺序表的顺序查找 typedef struct{ ElemType *elem; //数据元素存储空间基址 12/103 int length; //表长度 }SSTable;
2009/12/29 9.1.1顺序查找(3) 9.1.1顺序查找(4) ■对顺序表的顺序查找 。性能分析 int Search_Seq(SSTable ST,KeyType key){ 。平均查找长度(4SL):为确定记录在查找表中的位置， ∥在序表5T中顺序查找其关铺字等于key的兼拥元素。 需和给定值进行比较的关键字个数的期望值。 ∥着找到，则函数值为该元素在表中的位量，否则为加。 T.elem.key=key:∥-兵” 。查找成功时 W从后往前找 ASLnP+(n-1)P++2P+P:nST.lengch for(i=ST.length;ST.elem[i].key!-key;-i); 假定P=1/n return i访找不到时，i为0 WSearch Sea -2-14-安 2 哨兵的作用：免去查找过程中每一步部要检测整个表是 ,查找不成功时 否查找完单。 ASL n+1 13103 备 14/103 圄 9.1.2有序表的查找-折半查找(1) 9.1.2有序表的查找-折半查找(2) ■折半查找（二分查找） 基本思想：查找区间逐步缩小（折半） ·查找表结构：有序表 查找不成功示例： ,基本思想：查找区间逐步缩小（折半） 123456789 查找成功示例： (12,33,40,45,53,55,64,66,77),key=68 123456789 (12,33,40,45,53,55,64,66,77),ky=64 tow id high ow指示查找区间的下界： high指示查找区间的上界； mid mid=(low+high)/2。 15103 16/103 图 9.1.2有序表的查找-折半查找(3) 9.1.2有序表的查找-折半查找(4) int Search_Bin (SSTable ST,KeyType key ) ow=1;high=sT.length;/置区间初值 。性能分析 while (low <high){ ,判定树：折半查找的查找过程可以用二叉树描述。 mid (low +high)/2; 。=ST.length=l0时，判定树的形态为： if (EQ(key,ST.elem[mid].key)) 查找成功时的4SL=该结点在 return mid;/找到传查元素 else if (LT(key,ST.elem[mid].key)) 2 8 判定树中的层次 high=mid-1;/在前区何进行查找 ASL sLlog2n小+1 ①③6( ⑨ else low=mid+1;/∥缝续在后半区间进行查找 查找不成功时 } AL≤Llog,n+1 return O; /佩序表中不存在种查元素 判定树的形态与m直接相关， }/∥Search_Bin 7/103 合 与关键字的取值无关 18/103 圄 3
2009/12/29 3 9.1.1 顺序查找(3) 对顺序表的顺序查找 int Search_Seq(SSTable ST, KeyType key) { // 在顺序表ST中顺序查找其关键字等于 key的数据元素。 // 若找到 则函数值为该元素在表中的位置 否则为0 13/103 // 若找到，则函数值为该元素在表中的位置，否则为0。 ST.elem[0].key = key; // “哨兵” // 从后往前找 for (i=ST.length; ST.elem[i].key!=key; --i); return i; //找不到时，i为0 } // Search_Seq 哨兵的作用：免去查找过程中每一步都要检测整个表是 否查找完毕。 9.1.1 顺序查找(4) 性能分析 平均查找长度(ASL)：为确定记录在查找表中的位置， 需和给定值进行比较的关键字个数的期望值。 14/103 查找成功时 查找不成功时 ASL = n + 1 2 1 ( 1) 1 1/ ( 1) ... 2 , . 1 1 2 1 n n i n ASL P n ASL nP n P P P n ST length n i i n n 假定 9.1.2 有序表的查找-折半查找(1) 折半查找(二分查找) 查找表结构：有序表 基本思想：查找区间逐步缩小(折半) 15/103 查找成功示例： 1 2 3 4 5 6 7 8 9 (12, 33, 40, 45, 53, 55, 64, 66, 77)，key = 64 low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2。 low high mid low mid 9.1.2 有序表的查找-折半查找(2) 基本思想：查找区间逐步缩小(折半) 查找不成功示例： 1 2 3 4 5 6 7 8 9 16/103 (12, 33, 40, 45, 53, 55, 64, 66, 77)，key = 68 low high mid low midlow mid low mid high high 9.1.2 有序表的查找-折半查找(3) int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; 17/103 if (EQ (key , ST.elem[mid].key) ) return mid; // 找到待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin 9.1.2 有序表的查找-折半查找(4) 性能分析 判定树：折半查找的查找过程可以用二叉树描述。 n=ST.length=10时，判定树的形态为： 18/103 2 ASL n log 1 5 2 8 1 3 6 9 4 7 10 查找成功时的ASL = 该结点在 判定树中的层次 判定树的形态与n直接相关， 与关键字的取值无关 查找不成功时 2 ASL n log 1
2009/12/29 9.1.2有序表的查找-折半查找(5) 9.1.2有序表的查找-斐波拉契查找 假设有序表的长度=21（反之h=og,(a+),则描述折 ·斐波拉契查找 半查找的判定树是深度为的满二叉树。树中层次为1的结 。查找表结构：有序表 点有1个，层次为2的结点有2个，层次为的结点有21个。 。基本思想：根据斐波拉突序列的特征对麦进行分削 假设表中年个记录的查找概率相等，则查找成功时折半查 找的平均查找长度 开始时表中记录个数比斐波拉契数小1，即n=F-1 将给定值key和sT.elemF.ke进行比较， _ntogn+）-l ,若相等，则查找成功： n 在>50时，可得近似结果 .若key<ST.elemF.key ASLlog2(n+1)-1 则壁续在ST.clem1.F1一1川中查找 191103 20/103 圄 9.1.2有序表的查找-斐波拉契查找 9.1.2有序表的查找-插值查找 ■斐波拉奥查找 。插值查找 ,否则，继续在sT.elemF+1F。-中查找 。查找表结构：有序表 前一子表长度是F1,后-于表长度是F1 ,盖本思想：根据给定值key来确定进行比较的关健字 ,平均性能比折半查找好，但最坏情况下的性能 ST.elemlil.key的查找方法 (虽然仍是0logn)却比折半查找差： key-ST.elem(n.key ST.clemSTelemIy() ·分剖时只需进行加、减运算 ST.clem和sT.clem川分别为有序表中具有最小关健 字和最大关键字的记录 2H/103 22/103 图 9.1.2有序表的查找-插值查找 9.1.3静态树表的查找(1) ·插值查找 。问题：描述查找过程的判定刺为何类二叉树时，其查找性 能最佳？ 。插值查找只适于关健字均匀分布的表。 若判定树如左围，当各记录的查找振率 在这种情况下，对表长较大的顺序表，其平均性能比 相等时，查找成功时 折半查找好。 ASL=0.1*(1+2*2+3*4+43)=2.9 若各记录的查找振率不尊时，如0.05， Pw=0.15.其余为0.1， 则4SL-0.12-2+34+M-2+0.05+ 40.15-2.4+0.65-3.05 ⑦ 0若害牧时生和第6个记录的关接字比垫比 教不等时按折半查找，则 23/103 a 4
2009/12/29 4 9.1.2 有序表的查找-折半查找(5) 假设 有序表的长度n=2h-1（反之h=log2(n+1) ），则描述折 半查找的判定树是深度为h的满二叉树。树中层次为1的结 点有1个，层次为2的结点有2个，层次为h的结点有2h-1个。 19/103 log ( 1) 1 1 2 1 1 2 1 1 1 n n n j n C n ASL h j j n i bs i 假设表中每个记录的查找概率相等，则查找成功时折半查 找的平均查找长度 在 n>50 时，可得近似结果 ASLbs log2 (n 1) 1 9.1.2 有序表的查找-斐波拉契查找 斐波拉契查找 查找表结构：有序表 基本思想：根据斐波拉契序列的特征对表进行分割 20/103 开始时表中记录个数比斐波拉契数小1，即n = Fu-1 将给定值key和ST.elem[Fu-1].key进行比较， 若相等，则查找成功； 若key<ST.elem[Fu-1].key， 则继续在ST.elem[1..Fu-1-1]中查找 9.1.2 有序表的查找-斐波拉契查找 斐波拉契查找 否则，继续在ST.elem[Fu-1+1..Fu-1]中查找 前一子表长度是F -1 后一子表长度是F -1 21/103 前 子表长度是Fu-1 1 ，后 子表长度是Fu-2 1 平均性能比折半查找好，但最坏情况下的性能 (虽然仍是O(logn))却比折半查找差； 分割时只需进行加、减运算 9.1.2 有序表的查找-插值查找 插值查找 查找表结构：有序表 基本思想：根据给定值key来确定进行比较的关键字 22/103 基本思想：根据给定值key来确定进行比较的关键字 ST.elem[i].key的查找方法. ST.elem[l]和ST.elem[h]分别为有序表中具有最小关键 字和最大关键字的记录 . [ ]. ( 1) . [ ]. . [ ]. key ST elem l key i hl ST elem h key ST elem l key 9.1.2 有序表的查找-插值查找 插值查找 插值查找只适于关键字均匀分布的表。 在这种情况下 对表长较大的顺序表 其平均性能比 23/103 ， ，其平均性能比 折半查找好。 9.1.3 静态树表的查找(1) 问题：描述查找过程的判定树为何类二叉树时，其查找性 能最佳？ 若判定树如左图，当各记录的查找概率 相等时 查找成功时 24/103 5 2 8 1 3 6 9 4 7 10 相等时，查找成功时 ASL =0.1*(1+2*2+3*4+4*3)=2.9 若各记录的查找概率不等时，如P5=0.05, P10 = 0.15, 其余为0.1， 则ASL =0.1*(2*2+3*4+4*2)+0.05+ 4*0.15 = 2.4+0.65=3.05 若查找时先和第6个记录的关键字比较,比 较不等时再按折半查找，则 ASL = 0.1*(1+2*2+3*4+4)+0.2*4=2.9
2009/12/29 9.1.3静态树表的查找(2) 9.1.3静态树表的查找(3) PH值：定树的带权内略轻长度 次优查找树(Nearly Optimal Search Tree):若某个二又树的PH 如果只考也查找成功的情况， 值在所有具有同样权值的二又树中近似为最小，则称它为次忧查找 引入常量c,令e产p,(-12…n0,为结点的查找源率，则称为结 树。 点的权， PH=户为精银内每长度之和 次优查找树的构造 ·限个记影米速提地流能精一区，一-空限最小性 其中：m为二又树（判定前）上的结点个熏（即有序表的长虎：为 。分别对于序洲，4 一4和…构逢可操次忧查找满，并分 第：个结点在二又刺上的是次。 别设为根结赢的左子制和右子州。 ,静志最忧查找树Static Optimal Search Tree) 为便于计算△乃引入累计权值南w,=∑w,,并设4-5m4-0 一PH值取最小的二叉树， 构造静态最优责找树花费的时间代价校高1 =k--(m4-w4 =《4+w）-w-m- 25/103 26/103 圄 9.1.3静态树表的查找(4) 9.1.3静态树表的查找(5) 次优查找树的递归构造算法 例9-1(P223-224) Status SecondOptimal(BiTree &T,Elem Type Rl. fleat swl int low,int high)( 23 4 89 kev i abs(dw-swljl-sm-lmin)【 j:mi-abdw-swsm-l医 28 TBiTree)(izcof(BiTNode))exiOVERFLOW AP. 22 15 15 23 AP 1 6 9 8 7 AP AP, >rchild,B.sm,i+1,highk 271103 28/103 9.1.3静态树表的查找(6) 9.1.4索引顺序表的查找(1) 次优查找树构造算法的不足 在构造中未考察单个关健字的相应权值，则有可能出 ■分块查找（索引顺序查找） 现放选为根的关健字的权值比与它相邻的关健字的权值 小 ,查找表结构：以素引顺序表表示 调墓方法：进取邻近的权值较大的关键字作次优查找树的 ·起因 根结点。 ,顺序查找的不足：T(n)=O() 例9-2（略，P224) 。评价 :折半查找：T(n)=0(Iog2n),但要求查找表必须 ·大重实验表男，改优查找树和最代查找满的查找性能仅为 是有序表 12%,覆少超过3% 。基本思想：分块有序，索引表是有序表，索引 。构造次优查找满的算法的时间复杂度为0(logn) 次优查找树的查找过置类似于折半查找 项是（最大关键字，指针项） 29/108 合 30/103 圄 5
2009/12/29 5 9.1.3 静态树表的查找(2) PH值：判定树的带权内路径长度 如果只考虑查找成功的情况， 引入常量 c，令wi =cpi (i=1,2,…,n),(pi 为结点的查找概率)，则称wi 为结 点的权 称 25/103 ， 为带权内路径长度之和。 其中：n 为二叉树（判定树）上的结点个数(即有序表的长度)；hi 为 第 i 个结点在二叉树上的层次。 静态最优查找树(Static Optimal Search Tree) ——PH值取最小的二叉树． 构造静态最优查找树花费的时间代价较高！ 1 n i i i PH w h 9.1.3 静态树表的查找(3) 次优查找树(Nearly Optimal Search Tree)：若某个二叉树的PH 值在所有具有同样权值的二叉树中近似为最小，则称它为次优查找 树。 次优查找树的构造 26/103 取第i个记录ri 构造根结点，使得 取最小值 (l≤i ≤h) 分别对子序列{rl , rl+1 , …, ri-1}和{ri+1 , …, rh}构造两棵次优查找树，并分 别设为根结点ri 的左子树和右子树． 为便于计算 ，引入累计权值和 ，并设wl-1 = swl-1 =0 1 1 h i i jj ji jl P w w P i i j j l sw w 1 1 1 1 ( )( ) ( ) i hi i l hl ii P sw sw sw sw sw sw sw sw 9.1.3 静态树表的查找(4) 次优查找树的递归构造算法 Status SecondOptimal(BiTree &T, ElemType R[], float sw[], int low, int high) { i=low; min = abs(sw[high]-sw[low]); dw = sw[high]+sw[low-1]; f (j l 1 j hi h j) 27/103 for (j=low+1; j<=high; ++j) if(abs(dw-sw[j]-sw[j-1])<min) { i=j; min=abs(dw-sw[j]-sw[j-1]); } if ( !(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = R[i]; if (i==low) T->lchild = NULL; else SecondOptimal(T->lchild, R, sw, low, i-1); if (i==high) T->rchild = NULL; else SecondOptimal(T->rchild, R, sw, i+1, high); return OK; } 9.1.3 静态树表的查找(5) 例9-1 (P223-224) j0123456789 keyj ABCDE FGH I 28/103 wj 0112534435 swj 0 1 2 4 9 12 16 20 23 28 ΔPj 27 25 22 15 7 0 8 15 23 ΔPj 11 9 6 1 9 8 1 7 ΔPj 312 0 0 0 ΔPj 0 0 9.1.3 静态树表的查找(6) 次优查找树构造算法的不足 在构造中未考察单个关键字的相应权值，则有可能出 现被选为根的关键字的权值比与它相邻的关键字的权值 小． 29/103 调整方法：选取邻近的权值较大的关键字作次优查找树的 根结点． 例9-2 (略，P224) 评价 大量实验表明，次优查找树和最优查找树的查找性能仅为 1%~2%，很少超过3% 构造次优查找树的算法的时间复杂度为O(nlogn) 次优查找树的查找过程类似于折半查找 9.1.4 索引顺序表的查找(1) 分块查找(索引顺序查找) 查找表结构：以索引顺序表表示 起因 30/103 顺序查找的不足：T(n) = O(n) 折半查找：T(n) = O(log2n)，但要求查找表必须 是有序表 基本思想：分块有序，索引表是有序表，索引 项是(最大关键字, 指针项)