第9章 查找

1 第九章查找 9 1基本概念与术语9 2静态查找表9 3动态查找表9 4哈希表 2 查找表是由同一类型的数据元素 或记录 构成的集合 由于 集合 中的数据元素之间存在着松散的关系 因此查找表是一种应用灵便的数据结构 对查找表的操作 查询某个 特定的 数据元素是否在查找表中 检索某个 特定的 数据元素的各种属性 在查找表中插入一个数据元素 从查找表中删去某个数据元素 9 1基本概念与术语 3 动态查找表在查找过程中同时插入查找表中不存在的数据元素 或者从查找表中删除已存在的某个数据元素 此类表为动态查找表 查找表的分类 静态查找表仅作查询和检索操作的查找表 4 关键字是数据元素 或记录 中某个数据项或组合项的值 用以标识 识别 一个数据元素 或记录 若此关键字可以识别唯一的一个记录 则称之为 主关键字 若此关键字能识别若干记录 则称之为 次关键字 5 根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素 或记录 若查找表中存在这样一个记录 则称 查找成功 查找结果 给出整个记录的信息 或指示该记录在查找表中的位置 否则称 查找不成功 查找结果 给出 空记录 或 空指针 查找 6 如何进行查找 查找的方法取决于查找表的结构 由于查找表中的数据元素之间不存在明显的组织规律 因此不便于查找 为了提高查找的效率 需要在查找表中的元素之间人为地附加某种确定的关系 换句话说 用另外一种结构来表示查找表 7 查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL AverageSearchLength 为确定记录在表中的位置 需和给定值进行比较的关键字的个数的期望值叫查找算法的 8 抽象数据类型静态查找表的定义 ADTStaticSearchTable D是具有相同特性的数据元素的集合 每个数据元素含有类型相同的关键字 可唯一标识数据元素 数据关系R 数据元素同属一个集合 9 2静态查找表 数据对象D 9 Create 按某种次序对ST的每个元素调用函数Visit 一次且仅一次 ADTStaticSearchTable 基本操作P 10 9 2 1顺序表的查找 以顺序表表示静态查找表 则Search函数可用顺序查找来实现 其顺序存储结构如下 11 01234567891011 513192137566475808892 找64 64 监视哨 比较次数 5 比较次数 查找第n个元素 1查找第n 1个元素 2 查找第1个元素 n查找第i个元素 n 1 i查找失败 n 1 查找过程 从表的一端开始逐个进行记录的关键字和给定值的比较 例如 12 intSearch Seq SSTableST KeyTypekey 在顺序表ST中顺序查找其关键字等于 key的数据元素 若找到 则函数值为 该元素在表中的位置 否则为0 ST elem 0 key key 设置 哨兵 for i ST length ST elem i key key i 从后往前找returni 找不到时 i为0 Search Seq 算法描述 13 顺序查找性能分析 查找算法的平均查找长度 AverageSearchLength 为确定记录在查找表中的位置 需和给定值进行比较的关键字个数的期望值 其中 n为表长Pi为查找表中第i个记录的概率Ci为找到该记录时 曾和给定值比较过的关键字的个数 14 顺序表查找的平均查找长度为 对顺序表而言 Ci n i 1 在等概率查找的情况下 15 顺序表的查找算法简单 但平均查找长度较大 不适用于表长较大的查找表 若以有序表表示静态查找表 则查找过程可以基于 折半 进行 9 2 2有序表的查找 折半查找查找过程 每次将待查记录所在区间缩小一半 适用条件 采用顺序存储结构的有序表 16 1 设表长为n low high和mid分别指向待查元素所在区间的下界 上界和中点 key为给定值 折半查找算法实现 2 初始时 令low 1 high n mid low high 2 让key与mid指向的记录比较若key r mid key 查找成功若keyr mid key 则low mid 1 3 重复上述操作 直至low high时 查找失败 17 low high low high mid 1234567891011 513192137566475808892 low high mid 例如key 21的查找过程 low指示查找区间的下界 high指示查找区间的上界 mid low high 2 18 例key 70的查找过程 1234567891011 513192137566475808892 low high mid 找70 1234567891011 513192137566475808892 low high mid 1234567891011 513192137566475808892 low high mid 1234567891011 513192137566475808892 low high mid 19 1234567891011 513192137566475808892 low high 当下界low大于上界high时 则说明表中没有关键字等于Key的元素 查找不成功 20 intSearch Bin SSTableST KeyTypekey low 1 high ST length 置区间初值while low high mid low high 2 if key ST elem mid key returnmid 找到待查元素elseif key ST elem mid key high mid 1 继续在前半区间进行查找elselow mid 1 继续在后半区间进行查找 return0 顺序表中不存在待查元素 Search Bin 折半查找算法 21 先看一个有11个元素的表的例子 n 11 6 3 9 1 4 2 5 7 8 10 11 折半查找的性能分析 判定树 描述查找过程的二叉树 有n个结点的判定树的深度为 log2n 1折半查找法在查找过程中进行的比较次数最多不超过 log2n 1 22 假设有序表的长度n 2h 1 反之h log2 n 1 则描述折半查找的判定树是深度为h的满二叉树 树中层次为1的结点有1个 层次为2的结点有2个 层次为h的结点有2h 1个 假设表中每个记录的查找概率相等则查找成功时折半查找的平均查找长度 23 在n 50时 可得近似结果 可见 折半查找的效率比顺序查找高 折半查找只能适用于有序表 并且以顺序存储结构存储 24 9 2 3索引顺序表 在建立顺序表的同时 建立一个索引项 包括两项 关键字项和指针项 索引表按关键字有序 表则为分块有序 索引顺序表 索引 顺序表 顺序表 索引表 25 索引顺序查找又称分块查找查找过程 将表分成几块 块内无序 块间有序 先确定待查记录所在块 再在块内查找适用条件 分块有序表算法实现 用数组存放待查记录 每个数据元素至少含有关键字域建立索引表 每个索引表结点含有最大关键字域和指向本块第一个结点的指针 26 123456789101112131415161718 2212138920334244382448605874578653 224886 1713 索引表 查38 例如 27 分块查找方法评价 28 9 3动态查找表 动态查找表的特点 表结构本身是在查找过程中动态生成 若表中存在其关键字等于给定值key的记录 表明查找成功 否则插入关键字等于key的记录 29 InitDSTable 按某种次序对DT的每个结点调用函数Visit 一次且至多一次 基本操作 ADTDynamicSearchTable 30 一 二叉排序树 二叉查找树 定义二叉排序树或者是一棵空树 或者是具有如下特性的二叉树 若它的左子树不空 则左子树上所有结点的值均小于根结点的值 若它的右子树不空 则右子树上所有结点的值均大于根结点的值 它的左 右子树也都分别是二叉排序树 31 66 不是二叉排序树 32 以二叉链表形式存储 typedefstructBiTNode 结点结构TElemTypedata structBiTNode lchild rchild 左右指针 BiTNode BiTree 二叉排序树的存储结构 33 1 二叉排序树的查找算法 若二叉排序树为空 则查找不成功 否则1 若给定值等于根结点的关键字 则查找成功 2 若给定值小于根结点的关键字 则继续在左子树上进行查找 3 若给定值大于根结点的关键字 则继续在右子树上进行查找 34 在二叉排序树中查找关键字值等于50 35 90 95 35 if T p f returnFALSE 查找不成功elseif key T data key p T returnTRUE 查找成功elseif keydata key returnSearchBST T lchild key T p 在左子树中继续查找elsereturnSearchBST T rchild key T p 在右子树中继续查找 StatusSearchBST BiTreeT KeyTypekey BiTreef BiTree p SearchBST 36 根据动态查找表的定义 插入 操作在查找不成功时才进行 若二叉排序树为空树 则新插入的结点为新的根结点 否则 新插入的结点必为一个新的叶子结点 其插入位置由查找过程得到 2 二叉排序树的插入算法 37 StatusInsertBST BiTree InsertBST 38 3 二叉排序树的构造过程 从空树出发 经过一系列的插入操作之后 可生成一颗二叉排序树 其根结点为第一个插入的结点 数据元素的输入顺序不同 则得到的二叉排序树形态也不同 对二叉排序树进行中序遍历 可得到按关键字有序递增的线性序列 39 45 如果关键字序列输入顺序为 24 53 45 45 12 24 90 24 二叉排序树的构造过程 则生成二叉排序树的过程为 例 输入的关键字序列 45 24 53 45 12 24 90 则生成的二叉排序树形态不同 中序序列 12 24 45 53 90 40 1 被删除的结点是叶子 2 被删除的结点只有左子树或者只有右子树 3 被删除的结点既有左子树 也有右子树 4 二叉排序树的删除算法 可分三种情况讨论 和插入相反 删除在查找成功之后进行 并且要求在删除二叉排序树上某个结点之后 仍然保持二叉排序树的特性 41 50 30 80 20 90 85 40 35 88 32 1 被删除的结点是叶子结点 例如 被删关键字 20 88 其双亲结点中相应指针域的值改为 空 42 50 30 80 20 90 85 40 35 88 32 2 被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 指向被删除结点的左子树或右子树 被删关键字 40 80 43 分析 设删除前的中序遍历序列为 spPR 显然p的直接前驱是s希望删除p后 其它元素的相对位置不变有两种解决方法 法1 令 p的左子树为 F的左子树 p的右子树为 s的右子树 即FL PL SR PR 法2 令 s代替 p s为 p左子树最右下的结点 3 被删除的结点既有左子树 也有右子树 如何进行删除操作 注意 法2也可以用 P的直接后继代替 P 44 法2 法1 例 请从下面的二叉排序树中删除结点P S 45 8 4 12 6 5 7 10 14 11 16 13 练习 依次删除13 12 4 8 46 5 二叉排序树查找性能的分析 对于每一棵特定的二叉排序树 均可按照平均查找长度的定义来求它的ASL值 显然 由值相同的n个关键字 构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同 甚至可能差别很大 47 由关键字序列3 1 2 5 4构造而得的二叉排序树 由关键字序列1 2 3 4 5构造而得的二叉排序树 例如 2 1 3 4 5 3 5 4 1 2 ASL 1 2 3 4 5 5 3 ASL 1 2 3 2 3 5 2 2 48 平衡二叉树是二叉查找树的另一种形式 其特点为 树中每个结点的左 右子树深度之差的绝对值不大于1平衡因子 hL hR 例如 是平衡树 不是平衡树 二 平衡二叉树 49 构造平衡二叉 查找 树的方法是 从空的AVL树开始 逐步插入一系列结点而构成 如果在一棵AVL树中插入一个新结点 就有可能造成失衡 此时必须重新调整树的结构 使之恢复平衡 我们称调整平衡过程为平衡旋转 设a为失去平衡的最小不平衡子树 平衡旋转可以归纳为四类 LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转 如何构造 平衡二叉树 50 A B h 2 1 h 1 h 1 BL BR AR 1 LL平衡旋转 单向右旋 LL 51 A B h 1 2 1 h h 1 BL AL 2 RR平衡旋转 单向左旋 RR 52 A B h 1 2 1 h 2 h 1 CL CR AR 3 LR平衡旋转 先左后右 双向旋转 LR C BL h 1 1 53 A B h 1 2 1 h 2 h 1 CL CR AL 4 RL平衡旋转 先右后左 双向旋转 RL C BR h 1 1 54 例如 依次插入的关键字为5 4 2 8 6 9 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋转一次 先向右旋转再向左旋转 55 9 5 向左旋转一次 继续插入关键字9 56 B 树和B 树1 为什么采用B 树和B 树 大量数据存放在外存中 通常存放在硬盘中 由于是海量数据 不可能一次调入内存 因此 要多次访问外存 但硬盘的驱动受机械运动的制约 速度慢 所以 主要矛盾变为减少访外次数 在1970年由Rbayer和Emacreight提出用B 树作为索引组织文件 提高访问速度 减少时间 内存 E G 用二叉树组织文件 当文件的记录个数为100 000时 要找到给定关键字的记录 需访问外存17次 log100 000 太长了 50 25 10 75 15 35 60 90 20 30 40 55 70 80 95 索引文件 数据文件 文件头 可常驻内存 文件访问示意图 索引文件 数据文件存在盘上 三 B 树 57 2 B 树 B 树是一种平衡的多路查找树 首先介绍m阶B 树 定义 m阶B 树满足或空 或 A 根结点要么是叶子 要么至少有两个儿子B 除根结点和叶子结点之外 每个结点的儿子个数为 m 2K1且Kn的结点的地址 指在该B 树中 注意 K1 K2 KnD 所有的叶子结点都出现在同一层上 不带信息 可认为外部结点或失败结点 58 2 动态查找表 7 B 树和B 树例如 m 4阶B 树 除根结点和叶子结点之外 每个结点的儿子个数至少为m 2 2个 结点的关键字个数至少为1 该B 树的深度为4 叶子结点都在第4层上 1 99 3 47 58 64 1 39 1 27 1 11 2 43 78 1 18 1 35 第1层 第2层 第3层 L层 第4层 L 1层 59 2 动态查找表 7 B 树和B 树3 B 树的查找代价分析 查找过程 类似于二叉树的查找 如查找关键字为KEY的记录 从根开始查找 如果Ki KEY则查找成功 Ri为关键字为KEY的记录的地址 若KiKn 查找An指向的结点若找到叶子 则查找失败 注意 每次查找将去掉 s 1 s个分支 比二分查找快得多 设关键字的总数为N 求m阶B 树的最大层次L 层次结点数关键字的个数 最少 111222 m 2 1 32 m 2 2 m 2 m 2 1 42 m 2 22 m 2 2 m 2 1 L2 m 2 L 22 m 2 L 2 m 2 1 L 12 m 2 L 1所以 N 1 2 m 2 1 2 m 2 L 2 m 2 1 2m 2L 1 1故 L log N 1 2 1 60 2 动态查找表 7 B 树和B 树3 B 树的查找代价分析 设关键字的总数为N 求m阶B 树的最大层次L 故 L logm 2 N 1 2 1设N 1000 000且m 256 则L 3 最多3次访问外存可找到所有的记录 4 B 树的插入操作1 确定插入位置 将结点插入到第L层 注意 第L 1层为叶子结点 2 找到插入位置 将关键字和其它信息按序插入 3 若被插入结点的关键字个数 m 1 则该结点满 必须分裂成两个结点 否则不满结束 如结点原为 m 1 A0 K1 A1 K2 A2 Km 1 Am 1 插入一个关键字之后变为 m A0 K1 A1 K2 A2 Km Am 该结点将进行分裂 Km 2 p m 2 1 A0 K1 A1 Km 2 Am 2 m m 2 Am 2 Km Am 生成新结点p 将原结点的后半部分复制过去 若分裂一直进行到根结点 树可能长高一层 P P Km 2 p 数据项插入上层结点之中 61 2 动态查找表 7 B 树和B 树 例如 3阶B 树的插入操作 m 3 m 2 1 1 至少1个关键字 二个儿子结点 3 12 72430 24 30 45 70 53 90 26 100 39 50 61 85 3 45 70 53 90 26 100 39 50 61 85 12 30 3 244570 53 90 26 100 39 50 61 85 12 7 30 3 24 53 90 26 100 39 50 61 85 12 7 45 70 7插入 62 2 动态查找表 7 B 树和B 树 5 B 树的删除操作1 查找具有给定键值的关键字Ki2 如果在第L层 可直接删除 注意 第L 1层为叶子结点 转4 3 否则 则首先生成 替身 用的右子树中的最左面的结点的关键字值 即处于第L层上的最小关键字值取代 然后 删除第L层上的该关键字 4 从第L层开始进行删除 A 不动 若删除关键字值的那个结点的关键字的个数仍处于m 2 1和m 1之间 则结束 B 借 若删除关键字值的那个结点的关键字的个数原为m 2 1 而它们的左或右邻居结点的关键字的个数 m 2 1 则借一个关键字过来 处理结束 C 并 若该结点的左或右邻居结点的关键字的个数为m 2 1 则执行合并结点的操作 如结点原为 Ki Ai Ki 1 Ai 1 A0 K1 A1 A0 K1 A1 K1L 第L层 找到了被删结点的替身 63 2 动态查找表 7 B 树和B 树 例如 3阶B 树的删除操作 m 3 m 2 1 1 至少1个关键字 二个儿子结点 3 24 45 5390 37 100 50 61 70 被删关键字 3 24 45 6190 37 100 53 70 借 向被删结点方向旋转 假定再删除该关键字 3 24 45 90 37 100 61 70 假定再删除该关键字 3 24 45 90 100 61 70 3 24 4590 100 61 70 并 并 并 并 和父结点的一个关键字 及邻居合并 有可能进行到根 使B 树的深度降低一层 64 哈希表的相关定义哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的插入哈希查找分析 9 4哈希表 65 哈希查找又叫散列查找 利用哈希函数进行查找的过程 基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系 这样 不经过比较 一次存取就能得到所查元素的查找方法 一 哈希表的相关定义 哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系 哈希函数是一种映象 是从关键字到存储地址的一种映象 可写成 addr ai H ki 其中 ai是表中的一个元素addr ai 是ai的存储地址ki是ai的关键字 66 哈希表根据设定的哈希函数H key 和所选中的处理冲突的方法 将一组关键字映象到一个有限的 地址连续的地址集 区间 上 并以关键字在地址集中的 象 作为相应记录在表中的存储位置 如此构造所得的查找表称之为 哈希表 67 例30个地区的各民族人口统计表 编号地区名总人口汉族回族 1北京 2上海 以编号作关键字 构造哈希函数 H key keyH 1 1H 2 2 以地区名作关键字 取地区名称第一个拼音字母的序号作哈希函数 H Beijing 2H Shanghai 19H Shenyang 19 68 从例子可见 哈希函数只是一种映象 所以哈希函数的设定很灵活 只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突 key1 key2 但H key1 H key2 的现象 解决两个问题 构造好的哈希函数制定解决冲突的方案 69 二 哈希函数构造的方法 直接定址法数字分析法平方取中法折叠法除留余数法随机数法 70 哈希函数为关键字的线性函数H key a key b a b为常数 此法仅适合于 地址集合的大小 关键字集合的大小 1 直接定址法 例 100 300 500 700 800 900 可选取哈希函数为H key key 100 0123456789 71 2 数字分析法 假设关键字集合中的每个关键字都是由s位数字组成 u1 u2 us 分析关键字集中的全体 并从中提取分布均匀的若干位或它们的组合作为地址 此法适于能预先估计出全体关键字的每一位上各种数字出现的频度 72 以关键字的平方值的中间几位作为存储地址 求 关键字的平方值 的目的是 扩大差别 同时平方值的中间各位又能受到整个关键字中各位的影响 此方法适合于 关键字中的每一位都有某些数字重复出现频度很高的现象 3 平方取中法 73 将关键字分割成若干部分 然后取它们的叠加和为哈希地址 两种叠加处理的方法 移位叠加 将分割后的几部分低位对齐相加间界叠加 从一端沿分割界来回折叠 然后对齐相加此法适于关键字的数字位数特别多 4 折叠法 74 5 除留余数法 设定哈希函数为 H key keyMODp p m 其中 m为表长p为不大于m的素数或是不含20以下的质因子 75 给定一组关键字为 12 39 18 24 33 21 若取p 9 则他们对应的哈希函数值将为 3 3 0 6 6 3可见 若p中含质因子3 则所有含质因子3的关键字均映射到 3的倍数 的地址上 从而增加了 冲突 的可能 例如 为什么要对p加限制 76 6 随机数法 设定哈希函数为 H key Random key 其中 Random为伪随机函数此法用于对长度不等的关键字构造哈希函数 选取哈希函数考虑的因素 计算哈希函数所需时间关键字长度哈希表长度 哈希地址范围 关键字分布情况记录的查找频率 77 三 处理冲突的方法 处理冲突 的实际含义是 为产生冲突的地址寻找下一个哈希地址 开放定址法链地址法再哈希法建立公共的溢出区 78 为产生冲突的地址H key 求得一个地址序列 Hi H key di MODm其中 i 1 2 k k m 1 H key 为哈希函数 m为哈希表长 di为增量序列 有下列三种取法 开放定址法 79 对增量di的三种取法 1 线性探测再散列di 1 2 3 m 12 二次探测再散列di 12 12 22 22 k2 k m 2 3 伪随机探测再散列di是一组伪随机数列 80 例表长为11的哈希表中已填有关键字为17 60 29的记录 H key keyMOD11 现有第4个记录 其关键字为38 按三种处理冲突的方法 将它填入表中 1 H 38 38MOD11 5冲突H1 5 1 MOD11 6冲突H2 5 2 MOD11 7冲突H3 5 3 MOD11 8不冲突 38 2 H 38 38MOD11 5冲突H1 5 1 MOD11 6冲突H2 5 1 MOD11 4不冲突 38 3 H 38 38MOD11 5冲突设伪随机数序列为9 则 H1 5 9 MOD11 3不冲突 38 81 例如 给定关键字集合构造哈希表 19 01 23 14 55 68 11 82 36 设定哈希函数H key keyMOD11 表长 11 19 01 23 14 55 68 19 01 23 14 68 若采用线性探测再散列处理冲突 若采用二次探测再散列处理冲突 11 82 36 55 11 82 36 1 1 2 1 1 3 6 2 5 1 1 2 1 1 4 3 1 4 ASL 4 2 2 3 5 6 9 22 9 82 将所有哈希地址相同的记录都链接在同一链表中 例 给定关键字 19 01 23 14 55 68 11 82 36 哈希函数为H key keyMOD7 链地址法 83 例已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key keyMOD13 用链地址法处理冲突 0123456789101112 ASL 6 4 2 3