第九章 查找 2018/12/9

基本概念 查找(search) 关键字(key) 查找表(search table) 根据给定的某个值，确定一个关键字等于给定值的元素在表中的位置 关键字(key) 元素中的某个数据项，其值可以标识该元素 不同元素的关键字互不相同 查找表(search table) 同一数据类型的元素的集合 2018/12/9

基本概念 查找结果 查找表类型 成功：找到关键字值等于给定值的元素 失败：未找到关键字值等于给定值的元素 静态(static)：表元素的个数固定 只执行查找 动态(dynamic)：表元素的个数可变 可执行查找、插入、删除 2018/12/9

基本概念 影响查找速度的因素 时间复杂度函数 T( n, k ) 规模：查找表的元素个数 n 特征：待查关键字在查找表中的位置 k 平均查找长度 ASL (Average Search Length) 2018/12/9

基本概念 平均查找长度 ASL (Average Search Length) 为确定元素在表中的位置，与给定值进行比较的关键字平均个数 (期望值) n：查找表的元素个数 pi：查找第 i 个元素的概率 (与算法无关，只与问题相关) ci：查找第 i 个元素所需的关键字比较次数 (由算法决定) 2018/12/9

9.1 静态查找表 查找表可以有多种(人为决定的)表示方法 静态(static)：表元素个数固定 相同的查找元素，表示方法可以不同 9.1 静态查找表 查找表可以有多种(人为决定的)表示方法 相同的查找元素，表示方法可以不同 相同的表示方法，存储结构可以不同 相同的表示方法，查找方法可以不同 静态(static)：表元素个数固定 9.1.1 顺序表的查找：线性查找 查找方法：从表的一端开始，逐个进行关键字与给定值的比较 2018/12/9

9.1 静态查找表 9.1.1 顺序表的查找：线性查找 i i i i i 查找过程：从表的一端开始，逐个进行关键字与给定值的比较 9.1 静态查找表 9.1.1 顺序表的查找：线性查找 查找过程：从表的一端开始，逐个进行关键字与给定值的比较 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找 64 数组 r 64 i i i i i 监视哨 比较次数＝5 从后往前 2018/12/9

9.1 静态查找表 9.1.1 顺序表的查找：线性查找 算法9.1 int Search_Seq ( int r[], int n, int key){ //在数组 r 中顺序查找值＝key 的元素 //若找到，则函数值＝该元素在表中的位置，否则为0 r[0] = key; //0 号元素作为监视哨 for ( i=n; r[i] != key; --i ); //从后往前 return i； //找不到时，i＝0 } // Search_Seq 2018/12/9

9.1 静态查找表 顺序查找方法的性能 (ASL) ASL=∑PiCi (9-1) 查找成功情况下的平均查找长度为 9.1 静态查找表 顺序查找方法的性能 (ASL) n ASL=∑PiCi (9-1) i=1 查找成功情况下的平均查找长度为 ASL=nPl+(n-1)P2+…+(n-i+1)Pi+…+Pn (9-2) 假设每个元素的查找概率相等，即 Pi=1/n 则在等概率情况下平均查找长度为 ASL= (n+(n-1)+…(n-i+1)+…+1)/n = (n+1)/2 (9-3) 2018/12/9

9.1 静态查找表 顺序查找方法的性能 (ASL) 等概率情况下平均查找长度 如果是不等概率，如何改进查找性能？ 9.1 静态查找表 顺序查找方法的性能 (ASL) 等概率情况下平均查找长度 ASL=∑PiCi=(n+(n-1)+…+1)/n = (n+1)/2 如果是不等概率，如何改进查找性能？ 预处理：元素按查找概率排序 自适应：实时调整查找频度大的元素的位置 移动查找频度大的元素的位置 调整查找成功的元素的位置 2018/12/9

9.1 静态查找表 顺序查找方法的性能 (ASL) 等概率情况下平均查找长度 如果包含查找不成功的情况，如何评价性能？ 9.1 静态查找表 顺序查找方法的性能 (ASL) 等概率情况下平均查找长度 ASL=∑PiCi=(n+(n-1)+…+1)/n = (n+1)/2 如果包含查找不成功的情况，如何评价性能？ 假设查找不成功与成功的概率各占一半 1/2 查找成功时，每个元素的查找概率相同 1/2n ASL= (1/2n)*n(n+1)/2 +(1/2)*(n+1)= (n+1)/2 (9-4) 2018/12/9

9.1 静态查找表 9.1.2 有序表的查找：折半(二分)查找 原理：每次将待查元素所在区间缩小一半 采用数组存储元素 元素按关键字排序 9.1 静态查找表 9.1.2 有序表的查找：折半(二分)查找 原理：每次将待查元素所在区间缩小一半 采用数组存储元素 元素按关键字排序 2018/12/9

9.1.2 有序表的查找 (折半查找) [初始] 令 low=1, high=n, mid = (low+high)/2 low、high、mid 分别指向待查区间内元素下标的上界、下界和中点 k：给定的查找值 [初始] 令 low=1, high=n, mid = (low+high)/2 [比较] 让 k 与 mid 指向元素的关键字比较 若 k ＝ elem[mid].key，查找成功 若 k ＜ elem[mid].key，则 high = mid-1 若 k ＞ elem[mid].key，则 low = mid+1 重复比较，当 low>high 时查找失败 2018/12/9

P220页算法9.2：工作过程示例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找21 数组 r low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 2018/12/9

1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 2018/12/9

1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high 上下界相互穿越 查找失败！ 2018/12/9

int BinSearch(int r[], int n, int k) {//在有序数组 r 中二分查找 int low, high, mid; low=1; high=n; while ( low<=high ) { mid = (low+high) / 2; //中间元素 if( k>r[mid]) low=mid+1; else if( k<r[mid] ) high=mid-1; else return mid; //查找成功 } return -1;//查找失败 二分查找算法思想简单，但写出正确的算法不简单。 第一个二分查找算法于1946年出现，但第一个完全正确的二分查找算法直到1962才出现 2018/12/9

元素 r[6] 在表中的位置查找范围为 r[1]~r[6] 11 8 5 2 10 7 4 1 9 3 6 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 数组 r 元素 r[10] 在表中的位置 查找范围为 r[10]~r[11] 元素 r[6] 在表中的位置查找范围为 r[1]~r[6] 判定树：描述查找过程的二叉树 n 个结点的判定树深度＝log2n+1 树的形态只与元素个数 n 有关 2018/12/9

二分查找算法时间复杂度评价 n 个结点的判定树深度＝log2n + 1 设元素个数 n=2h-1，则h=log2(n+1) 11 8 5 2 10 7 4 1 9 3 6 设元素个数 n=2h-1，则h=log2(n+1) 设元素查找概率相等，即pi=1/n 故 ASL＝O(log2n)，比顺序查找快 2018/12/9

9.1 静态查找表 二分查找算法的评价 查找效率：高 限制条件 元素必须有序 只能数组存储 (顺序存储结构) 等概率假设 2018/12/9

练习 ① 给出在递增有序数组 A [1..21] 中二分查找的判定树 ② 求出等概率假设下的 ASL 1 11 5 16 2 8 13 19 4 6 9 12 14 17 20 7 10 15 18 21 2018/12/9

9.1 静态查找表 有序表的查找问题再思考 动态规划最优二叉查找树 各记录被查概率不等，二分查找效率还好吗？ 元素 05 13 19 21 9.1 静态查找表 有序表的查找问题再思考 各记录被查概率不等，二分查找效率还好吗？ 元素 05 13 19 21 37 概率 pi 0.1 0.2 0.4 动态规划最优二叉查找树 2018/12/9

9.1.4 索引顺序表的查找(分块查找) 结构：表 ＋ 索引 图 9.6 方法：先查索引后查表 索引：只存储关键字，有序 9.1.4 索引顺序表的查找(分块查找) 结构：表 ＋ 索引 索引：只存储关键字，有序 表：存储数据及其关键字，按索引分区块 块间有序：块i 内关键字＞块i－1 最大关键字 块内无序 方法：先查索引后查表 图 9.6  顺序 / 折半查找  顺序查找 2018/12/9

9.1.4 索引顺序表的查找(分块查找) 结构：表(块间有序，块内无序) ＋ 索引(有序) 方法：先查索引后查表 9.1.4 索引顺序表的查找(分块查找) 结构：表(块间有序，块内无序) ＋ 索引(有序) 方法：先查索引后查表 效率：平均查找长度(ASL) 索引(顺序查找) 索引(折半查找) 2018/12/9

9.2 动态查找表 动态：查找过程中允许插入、删除元素 表示方法、存储方式需考虑插入、删除效率 动态查找表经常采用树结构 表结构动态变化 9.2 动态查找表 动态：查找过程中允许插入、删除元素 表结构动态变化 表示方法、存储方式需考虑插入、删除效率 数组：删除操作代价大 有序数组：插入操作代价大 动态查找表经常采用树结构 2018/12/9

9.2 动态查找表 “左小右大” 9.2.1 二叉排序树和平衡二叉树 二叉排序树 左子树上所有结点的值均小于它的根结点的值 9.2 动态查找表 9.2.1 二叉排序树和平衡二叉树 二叉排序树 左子树上所有结点的值均小于它的根结点的值 右子树上所有结点的值均大于它的根结点的值 45 12 53 3 37 100 24 61 90 78 “左小右大” 2018/12/9

9.2 动态查找表 “左小右大” 二叉排序树 中间元素的顺序如何排？ 最小元素：最靠左的结点 最大元素：最靠右的结点 45 12 53 3 9.2 动态查找表 二叉排序树 最小元素：最靠左的结点 最大元素：最靠右的结点 “左小右大” 45 12 53 3 37 100 24 61 90 78 中间元素的顺序如何排？ 3 100 2018/12/9

9.2 动态查找表 “左小右大” 二叉排序树 中序遍历！ 元素的顺序如何排？ 3 12 24 37 45 53 61 78 90 100 9.2 动态查找表 二叉排序树 元素的顺序如何排？ “左小右大” 中序遍历！ 45 12 53 3 37 100 24 61 90 78 3 12 24 37 45 53 61 78 90 100 2018/12/9

9.2 动态查找表 二叉排序树的查找过程 将给定值和根结点值比较 若无子树，查找失败 若相等：查找成功 若小于：进入左子树查找 “左小右大” 9.2 动态查找表 二叉排序树的查找过程 将给定值和根结点值比较 若相等：查找成功 若小于：进入左子树查找 若大于：进入右子树查找 若无子树，查找失败 “左小右大” 45 12 53 3 37 100 24 61 90 78 2018/12/9

二叉排序树的查找 (递归地)将给定值和根的值比较 Ex1. 查找 100 “左小右大” ＝ 查找成功；＜ 进左子树；＞ 进右子树 100 45 12 53 3 37 100 24 61 90 78 Ex1. 查找 100 100 2018/12/9

二叉排序树的查找 (递归地)将给定值和根的值比较 Ex2. 查找 24 “左小右大” ＝ 查找成功；＜ 进左子树；＞ 进右子树 24 45 12 53 3 37 100 24 61 90 78 Ex2. 查找 24 24 2018/12/9

二叉排序树的查找 (递归地)将给定值和根的值比较 Ex2. 查找 40 “左小右大” ＝ 查找成功；＜ 进左子树；＞ 进右子树 40 45 12 53 3 37 100 24 61 90 78 Ex2. 查找 40 什么情况代表失败？ 发现无子树，则失败 ① 给定值＜根，进左子树 但左子树空 ② 给定值＞根，进右子树 但右子树空 失败 2018/12/9

9.2 动态查找表 二叉排序树(递归)查找的效率分析 效率真的与折半查找类似吗？ 查找与给定值相等的元素(结点)的过程 与给定值比较的次数 9.2 动态查找表 二叉排序树(递归)查找的效率分析 查找与给定值相等的元素(结点)的过程 从根到该结点的路径 与给定值比较的次数 路径长度＋1＝该结点层次 比较次数≤树的深度 类似二分查找，高效！ 45 12 53 3 37 100 24 61 90 78 效率真的与折半查找类似吗？ 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点(动态) 查找失败时：将给定值插入树中 查找路径最后结点的孩子 给定值  新叶子 45 9.2 动态查找表 二叉排序树在查找过程中会增减结点(动态) 查找失败时：将给定值插入树中 查找路径最后结点的孩子 给定值  新叶子 45 12 53 3 37 100 24 61 90 78 40 2018/12/9

9.2 动态查找表 查找失败时：将给定值插入二叉排序树中 定位查找路径的最后(元素)结点 给定值 vs. 最后元素值 若给定值大于最后元素 9.2 动态查找表 查找失败时：将给定值插入二叉排序树中 定位查找路径的最后(元素)结点 给定值 vs. 最后元素值 若给定值大于最后元素 给定值＝最后元素的右孩子 若给定值小于最后元素 给定值＝最后元素的左孩子 45 12 53 3 37 100 24 61 90 78 40 2018/12/9

9.2 动态查找表 若从空树开始 边找边插入元素，最终生成一棵二叉排序树 图 9.8 Ø 45 2018/12/9

9.2 动态查找表 若从空树开始 图 9.8 边找边插入元素，最终生成一棵二叉排序树 “左小右大” 45 24 53 12 90 9.2 动态查找表 若从空树开始 边找边插入元素，最终生成一棵二叉排序树 图 9.8 “左小右大” 45 24 53 12 90 2018/12/9

练习 ① 根据列表 { 45, 24, 53, 12, 37, 93 } 画出对应的二叉排序树 ② 根据列表 { 12, 24, 37, 45, 53, 93 } 画出对应的二叉排序树 2018/12/9

9.2 动态查找表 二叉排序树的查找时间复杂度 比较次数≤树的深度 ASL=(1+2+2+3+3+3)/6=14/6=7/3 9.2 动态查找表 二叉排序树的查找时间复杂度 比较次数≤树的深度 ASL=(1+2+2+3+3+3)/6=14/6=7/3 ASL=(1+2+3+4+5+6)/6=21/6=7/2 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树特性 “左小右大” 情况1：删除叶子 删除 78 45 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树特性 “左小右大” 45 12 53 3 37 100 24 61 90 78 情况1：删除叶子 ① 删除该结点 ② 父结点对应指针=NULL 删除 78 78 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 情况2：被删结点只有右子树 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 45 12 53 3 37 100 24 61 90 78 情况2：被删结点只有右子树 被删结点是个左孩子 ① 删除该结点 ② 该结点的右子树成为该结点 其父亲的左孩子 61 删除 61 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 情况2’：被删结点只有右子树 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 45 12 53 3 37 100 24 61 90 78 情况2’：被删结点只有右子树 被删结点是个右孩子 ① 删除该结点 ② 该结点的右子树成为 其父亲的右孩子 53 删除 53 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 对称的：被删结点只有左子树 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 45 12 53 3 37 100 24 61 90 78 对称的：被删结点只有左子树 被删结点是个右孩子 ① 删除该结点 ② 该结点的左子树成为 其父亲的右孩子 100 删除 100 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 情况 2 小结： 被删结点只有单子树 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 45 12 53 3 37 100 24 61 90 78 情况 2 小结： 被删结点只有单子树 被删结点是个左/右孩子 ① 删除该结点 ② 该结点的单子树成为 其父亲的左/右孩子 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 删除 12 情况 3：被删结点有双子树 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 删除 12 45 12 53 3 37 100 24 61 90 78 情况 3：被删结点有双子树 12 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 3 删除 12 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 删除 12 45 12 53 3 37 100 24 61 90 78 情况 3：被删结点有双子树 12 中序遍历序列： 3 12 24 37 45 53 61 78 90 100 3 其中，3 是 12 的直接前驱 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 24 37 删除 45 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 删除 45 45 12 53 3 37 100 24 61 90 78 45 情况3：被删结点有双子树 中序遍历序列： 3 12 24 37 45 53 61 78 90 100 24 37 其中，37 是 45 的直接前驱 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 还有其它可能吗？ 删除结点后：必须保持二叉排序树 “左小右大” 37 24 删除 45 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 删除 45 45 12 53 3 37 100 24 61 90 78 37 情况3：被删结点有双子树 用中序遍历序列中 被删结点的直接前驱代替它 24 还有其它可能吗？ 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 53 删除 45 45 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 删除 45 45 12 53 3 37 100 24 61 90 78 45 情况3：被删结点有双子树 53 中序遍历序列： 3 12 24 37 45 53 61 78 90 100 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 53 删除 45 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 删除 45 45 12 3 37 100 24 61 90 78 53 情况3：被删结点有双子树 中序遍历序列： 3 12 24 37 45 53 61 78 90 100 其中，53 是 45 的直接后继 2018/12/9

9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 53 删除 45 9.2 动态查找表 二叉排序树在查找过程中会增减结点 删除结点后：必须保持二叉排序树 “左小右大” 删除 45 45 12 3 37 100 24 61 90 78 53 情况3：被删结点有双子树 用中序遍历序列中 被删结点的直接后继代替它 2018/12/9

练习 50 在如下二叉排序树中，依次删除两个元素 50, 60 80 50 120 60 110 150 55 70 53 80 60 在如下二叉排序树中，依次删除两个元素 50, 60 80 50 120 60 110 150 55 70 53 80 60 120 110 150 55 70 53 50 删除 50 2018/12/9

练习 60 在如下二叉排序树中，依次删除两个元素 50, 60 80 120 110 150 55 70 53 直接前驱代替 80 60 在如下二叉排序树中，依次删除两个元素 50, 60 80 120 110 150 55 70 53 直接前驱代替 80 60 120 110 150 55 70 53 60 删除 60 删除 60 80 55 120 110 150 53 70 直接后继代替 2018/12/9

练习 10 在如下二叉排序树中，依次删除两个元素 10, 6 10 4 25 8 13 6 5 13 4 25 8 6 5 直接后继代替 8 在如下二叉排序树中，依次删除两个元素 10, 6 10 4 25 8 13 6 5 10 13 4 25 8 6 5 直接后继代替 删除 10 删除 10 8 4 25 6 13 5 直接前驱代替 2018/12/9

练习 6 6 在如下二叉排序树中，依次删除两个元素 10, 6 13 4 25 8 6 5 直接后继代替 13 4 25 8 5 8 4 在如下二叉排序树中，依次删除两个元素 10, 6 13 4 25 8 6 5 直接后继代替 13 4 25 8 5 删除 6 6 8 4 25 6 13 5 直接前驱代替 8 4 25 5 13 删除 6 6 2018/12/9

9.2 动态查找表 删除结点后必须保持二叉排序树 “左小右大” 情况1：被删结点是叶子 9.2 动态查找表 删除结点后必须保持二叉排序树 “左小右大” 情况1：被删结点是叶子 ① 删除该结点；② 父结点对应指针=NULL 情况 2 ：被删结点只有单子树 (被删结点本身是个左/右孩子) ① 删除该结点；② 该结点的单子树成为其父亲的左/右孩子 情况3：被删结点有双子树 ① 删除该结点；② 用中序遍历序列中被删结点的直接后继代替它 2018/12/9

二叉排序树的查找时间复杂度 比较次数≤树的深度 树的深度树的形态决定 二叉排序树的形态元素插入次序决定 事后调整树的形态可以吗？ 树越扁平，深度越小，比较次数越少 二叉排序树的形态元素插入次序决定 事先确定元素的插入次序是困难的！ 事后调整树的形态可以吗？ 2018/12/9

9.2 动态查找表 平衡二叉树(Balanced Binary Tree) AVL 树：任一结点的平衡因子绝对值≤1 9.2 动态查找表 平衡二叉树(Balanced Binary Tree) 又名 AVL 树(得名于发明者) AVL 树：任一结点的平衡因子绝对值≤1 平衡因子 BF (Balance Factor) 结点左右子树高度差 约定：空树的高度＝ -1 任一结点的平衡因子＝{ -1, 0, 1 } 2018/12/9

9.2 动态查找表 AVL 树：任一结点的平衡因子绝对值≤1 平衡因子 BF (Balance Factor) 结点左右子树高度差 9.2 动态查找表 AVL 树：任一结点的平衡因子绝对值≤1 平衡因子 BF (Balance Factor) 结点左右子树高度差 -1 1 1 结点内的值＝平衡因子 2018/12/9

9.2 动态查找表 AVL 树：任一结点的平衡因子绝对值≤1 平衡因子 BF (Balance Factor) 结点左右子树高度差 9.2 动态查找表 AVL 树：任一结点的平衡因子绝对值≤1 平衡因子 BF (Balance Factor) 结点左右子树高度差 2 -1 1 -1 -2 1 结点内的值＝平衡因子 2018/12/9

9.2 动态查找表 AVL 树：任一结点的平衡因子绝对值≤1 树的深度＝Θ(log n) 树的平均查找长度 ASL = Θ(log n) 9.2 动态查找表 AVL 树：任一结点的平衡因子绝对值≤1 树的深度＝Θ(log n) n＝结点个数 树的平均查找长度 ASL = Θ(log n) 真的类似二分查找，高效！ 1 -1 结点平衡因子绝对值≤1 2018/12/9

9.2 动态查找表 AVL 树：任一结点的平衡因子绝对值≤1 如何保证树的深度＝Θ(log n)？ 事后调整树形态 9.2 动态查找表 AVL 树：任一结点的平衡因子绝对值≤1 如何保证树的深度＝Θ(log n)？ 在构造树、删除结点的过程中调整树的形态(具体参见 P233～P238) 事后调整树形态 1 -1 结点平衡因子绝对值≤1 2018/12/9

9.3 哈希(Hash)查找 查找：定位元素的位置 根据下标定位元素最快：地址= addr(下标) 是否存在类似的快速方法？ 给定值与元素比较 顺序、二分、二叉查找树 根据下标定位元素最快：地址= addr(下标) 但，查找需要有意义的关键字 是否存在类似的快速方法？ 地址= addr(关键字) 2018/12/9

9.3 哈希(Hash)查找 基本思想 映射：{ 元素关键字值 }  { 元素存储地址 } addr(ai)=H(ki) Hash 函数 无需比较，一次计算就得到元素位置 addr(ai)=H(ki) ki：元素关键字值，addr(ai)：元素存储地址 Hash 函数 关键字值 集合 存储地址 2018/12/9

9.3 哈希(Hash)查找 哈希(查找)表 哈希查找：又叫做，散列查找 哈希地址 根据元素关键字值，应用哈希函数，确定元素的表中地址，并将元素放入此地址 哈希查找：又叫做，散列查找 利用哈希函数进行查找的过程 哈希地址 元素关键字值，代入哈希函数计算得到的地址 2018/12/9

9.3 哈希(Hash)查找 示例：30 个地区的各民族人口统计表 编号 地区名 总人口 汉族 回族…... 1 北京 2 上海 …... 编号 地区名 总人口 汉族 回族…... 1 北京 2 上海 …... 以编号作关键字 哈希函数：H(编号)=编号 H(1)=1 H(2)=2 以地区名作关键字 哈希函数：H(地区名)=其首字母的序号 H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 2018/12/9

9.3 哈希(Hash)查找 例: key 集合＝{25，74，36，15，40，29，82，19，65，33，57，47，50}，Hash 函数: H(key)＝key % 13，查找表如下 查找 ①给定关键字值 key 代入 Hash 函数计算出元素地址 ②从该地址取出元素信息（无需进行关键字值的比较） 例如：查找 key=57 的元素，计算得 h(57)=57%13=5 即关键字值＝57的元素的地址是在表中的第 5 个位置 2018/12/9

9.3 哈希(Hash)查找 哈希函数是映射 冲突：key1key2，但 H(key1)=H(key2) 无固定要求，只要使关键字的哈希函数值落在表长允许范围之内即可 冲突：key1key2，但 H(key1)=H(key2) 同义词：具有相同函数值的两个关键字 哈希函数通常是种压缩映象，所以冲突不可避免 只能尽量减少 冲突发生后，需要有处理冲突的方法 2018/12/9

9.3 哈希(Hash)查找 产生散列冲突的主要因素 散列函数 装填因子＝元素个数(n) / 表空间大小(m) 散列函数选择适当，使散列地址尽可能均匀地分布在散列空间中，产生的冲突就少 装填因子＝元素个数(n) / 表空间大小(m) 装填因子越小，产生冲突可能性越小 2018/12/9

哈希函数构造方法 直接定址法：取关键字或关键字的某个线性函数作哈希地址 特点 H(key)=key 或 H(key)=a·key+b 直接定址法所得地址集合与关键字集合大小相等 不会有冲突。若有冲突，说明关键字错误 但，实际中能用这种哈希函数的情况很少 能用于关键字分布基本连续的情况 若不连续，空号较多，将造成存储空间的严重浪费 2018/12/9

哈希函数构造方法 数字分析法：取关键字的若干位或其组合作哈希地址 关键字位数比哈希地址位数大，且关键字事先知道 例： 元素个数=80，关键字是 8 位的十进制数，地址取 2位 分析：  位只取8  位只取1  位只取3、4  位只取2、7、5  位的分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址     8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ….. 2018/12/9

哈希函数构造方法 平方取中法 取关键字平方后中间几位作哈希地址 适用于不知道全部关键字情况 2018/12/9

哈希函数构造方法 折叠法 将关键字分成位数相同的几部分，然后取这几部分的叠加和(舍去进位)做哈希地址 移位叠加：将这几部分低位对齐相加 间界叠加：将这几部分依次反序，对齐相加 适于关键字位数很多，且每位数字分布大致均匀 例、关键字：0442205864，哈希地址位数为4 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位叠加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 间界叠加 2018/12/9

哈希函数构造方法 除留余数法 H(key)=key MOD p，pm(表的长度) 简单、常用，可与上述几种方法结合使用 2018/12/9

哈希函数构造方法 随机数法 取关键字的随机函数值作哈希地址 H(key)=random(key) 适用于关键字长度不等的情况 2018/12/9

哈希函数构造方法 哈希函数选取的因素 计算本身所需时间 关键字长度 哈希表的长度(即哈希地址范围) 关键字分布情况 元素的查找频率 2018/12/9

处理冲突的方法 开放定址法：冲突发生时，计算形成探查序列 沿序列逐个地址探查 当找到空位置(开放地址)时，放入冲突元素 Hi = ( H(key) + di ) MOD m，i=1,2,……k(km-1) 其中：H(key) 哈希函数 　　　m 哈希表表长 　　　di 增量序列 2018/12/9

处理冲突的方法 开放定址法 线性探测再散列：di=1,2,3,……m-1 H1 =H(key) Hj =(Hj-1+1) MOD m j=2,3,… 二次探测再散列：di=1²,-1²,2²,-2²,3²,……±k²(km/2) H1=H(key) H2j=(H1+j2) MOD m H2j+1=(H1-j2) MOD m j=1,2,3,… 伪随机探测再散：ri=伪随机数序列 Hj= (H1+ri) MOD m 2018/12/9

处理冲突的方法 例如：已知哈希表长度＝11，已填有关键字 17，60，29 哈希函数：H(key)=key MOD 11 现需要放入关键字 38，按上述三种开放地址法填表为？ 0 1 2 3 4 5 6 7 8 9 10 60 17 29 2018/12/9

H(key)=key MOD 11，新元素关键字为38 0 1 2 3 4 5 6 7 8 9 10 60 17 29 38 38 38 (1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 (2) H(38)=38 MOD 11=5 冲突 H1=(5+1²) MOD 11=6 冲突 H2=(5-1²) MOD 11=4 不冲突 (3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突 2018/12/9

处理冲突的方法 再哈希法：使用多个哈希函数 链地址法 冲突时，使用另一个哈希函数再次计算地址 将冲突关键字(同义词)存储在单链表中 Hi=Rhi(key) i=1,2,……k 其中：Rhi——另一个哈希函数 特点：计算时间增加 链地址法 将冲突关键字(同义词)存储在单链表中 2018/12/9

链地址法 例：已知一组关键字 (19，14，23，1，68，20，84，27，55，11，10，79) 哈希函数： H(key)=key MOD 13，用链地址法处理冲突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11 2018/12/9

9.3 哈希(Hash)查找 哈希查找的时间复杂度分析 当存在冲突时，仍需要给定值与关键字比较 与给定值进行比较的关键字个数取决于 平均查找长度(ASL) 与给定值进行比较的关键字个数取决于 哈希函数的选取 处理冲突的方法 哈希表装填因子  =表中元素个数 / 表长度 2018/12/9

已知：关键字(19,14,23,1,68,20,84,27,55,11,10,79) 　　　哈希表长为m=16 　　　哈希函数：H(key)=key MOD 13 　每个元素的查找概率相等 (1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

( 19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79 ) H(key)=key MOD 13，每个元素查找概率相等 (1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 1 68 27 55 19 20 84 79 23 11 10 H(19)=6 H(11)=11 H(14)=1 H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12 H(23)=10 H(1)=1 冲突，H1=(1+1) MOD16=2 H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=9 H(68)=3 H(20)=7 H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8 H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 H(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5 ASL=(1*6+2*1+3*3+4*1+1*9)/12=2.5

H(key)=key MOD 13，每个元素查找概率相等 ( 19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79 ) H(key)=key MOD 13，每个元素查找概率相等 (2) 用链地址法处理冲突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11 ASL=(1*6+2*4+1*3+1*4)/12 =1.75 2018/12/9