第九章 查找48635

2020 4 7 1 37 第九章查找 2020 4 7 2 何谓查找表 查找表是由同一类型的数据元素 或记录 构成的集合 2020 4 7 3 对查找表经常进行的操作 1 查询某个 特定的 数据元素是否在查找表中 2 检索某个 特定的 数据元素的各种属性 3 在查找表中插入一个数据元素 4 从查找表中删去某个数据元素 2020 4 7 4 仅作查询和检索操作的查找表 静态查找表 有时在查询之后 还需要将 查询 结果为 不在查找表中 的数据元素插入到查找表中 或者 从查找表中删除其 查询 结果为 在查找表中 的数据元素 动态查找表 查找表可分为两类 2020 4 7 5 是数据元素 或记录 中某个数据项的值 用以标识 识别 一个数据元素 或记录 关键字 若此关键字可以识别唯一的一个记录 则称之谓 主关键字 若此关键字能识别若干记录 则称之谓 次关键字 2020 4 7 6 根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素或 记录 查找 若查找表中存在这样一个记录 则称 查找成功 查找结果给出整个记录的信息 或指示该记录在查找表中的位置 否则称 查找不成功 查找结果给出 空记录 或 空指针 2020 4 7 7 9 1静态查找表 9 2动态查找树表 9 3哈希表 2020 4 7 8 9 1静态查找表 2020 4 7 9 数据对象D 数据关系R D是具有相同特性的数据元素的集合 每个数据元素含有类型相同的关键字 可唯一标识数据元素 数据元素同属一个集合 ADTStaticSearchTable 2020 4 7 10 Create Destroy Search ST key Traverse ST Visit 基本操作P ADTStaticSearchTable 2020 4 7 11 假设静态查找表为顺序存储结构 2020 4 7 12 1 顺序查找 2 二分查找 3 分块查找 基本查找方法 2020 4 7 13 以顺序表或线性链表表示静态查找表 1 顺序查找表 它从表的一段开始 顺序扫描线性表 依次扫描节点关键字 和给定值Key相比 直到找到为止 平均查找长度 n 1 2 2020 4 7 14 ST 回顾顺序表的查找过程 假设给定值key 64 要求ST k key 问 k key 64 k 64 2020 4 7 15 平均查找长度 AverageSearchLength 为查找过程中与给定值比较的关键字个数的数学期望 其中 n为表长 Pi为查找表中第i个记录的概率 Ci为查找第i个记录所需的比较次数 顺序查找的性能分析 2020 4 7 16 在等概率查找的情况下 顺序表查找的平均查找长度为 对顺序表需进行n i 1次比较 即Ci n i 1 2020 4 7 17 上述顺序查找表的查找算法简单 但平均查找长度较大 特别不适用于表长较大的查找表 若以有序表表示静态查找表 则查找过程可以基于 折半 进行 2 有序查找表 折半查找 2020 4 7 18 ST elem ST length 例如 key 64的查找过程如下 low high mid low mid high mid low指示查找区间的下界high指示查找区间的上界mid low high 2 2020 4 7 19 ST elem ST length 例如 key 64的查找过程如下 low high mid low mid high mid 2020 4 7 20 intSearch Bin SSTableST KeyTypekey low 1 high ST length 置区间初值while low high mid low high 2 if EQ key ST elem mid key returnmid 找到待查元素elseif LT key ST elem mid key high mid 1 继续在前半区间进行查找elselow mid 1 继续在后半区间进行查找 return0 顺序表中不存在待查元素 Search Bin 2020 4 7 21 先看一个具体的情况 假设 n 11 6 3 9 1 4 2 5 7 8 10 11 判定树 1 2 2 3 3 3 3 4 4 4 4 折半查找的性能分析平均查找长度 2020 4 7 22 记录在判定树上的层次正好是查找该记录的比较次数 平均查找长度 判定树 折半查找的时间复杂度为 2020 4 7 23 3 分块查找 又称索引查找 分块查找把线性表分成几块 每一块中元素的顺序是任意的 而块与块之间必须按关键字大小有序 另需建一索引表 索引表中的一项对应与表中的一块 且索引表的关键字按升序排列 索引表的结构为 指向本块第一个结点 2020 4 7 24 例 欲查找k 38的结点 2020 4 7 25 9 2动态查找树表 表结构本身是在查找过程中动态产生的 2020 4 7 26 9 2动态查找树表 9 2 1二叉排序树和平衡二叉树9 2 2B 树和B 树9 2 3键树 2020 4 7 27 9 2 1二叉排序树和平衡二叉树 2020 4 7 28 一 二叉排序树 二叉查找树 2020 4 7 29 1 若它的左子树不空 则左子树上所有结点的值均小于根结点的值 二叉排序树或者是一棵空树 或者是具有如下特性的二叉树 3 它的左 右子树也都分别是二叉排序树 2 若它的右子树不空 则右子树上所有结点的值均大于根结点的值 1 什么是二叉排序树 2020 4 7 30 50 30 80 20 90 10 85 40 35 25 23 88 例如 是二叉排序树 66 不 2020 4 7 31 通常 取二叉链表作为二叉排序树的存储结构 typedefstructBiTNode 结点结构structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree TElemTypedata 2020 4 7 32 2 二叉排序树的查找算法 1 若给定值等于根结点的关键字 则查找成功 2 若给定值小于根结点的关键字 则继续在左子树上进行查找 3 若给定值大于根结点的关键字 则继续在右子树上进行查找 否则 若二叉排序树为空 则查找不成功 2020 4 7 33 50 30 80 90 40 35 例如 二叉排序树 查找关键字 50 50 50 35 50 50 90 20 85 88 32 30 40 35 50 80 90 95 2020 4 7 34 从上述查找过程可见 在查找过程中 生成了一条查找路径 从根结点出发 沿着左分支或右分支逐层向下直至关键字等于给定值的结点 或者 从根结点出发 沿着左分支或右分支逐层向下直至指针指向空树为止 查找成功 查找不成功 2020 4 7 35 3 如何构造一棵二叉排序树 二叉排序树的插入算法 例 45 24 53 50 12 40 90 45 注 二叉排序树的中序扫描序列即是升序序列 2020 4 7 36 二叉排序树的插入算法 若二叉排序树为空树 则新插入的结点为新的根结点 否则 新插入的结点必为一个新的叶子结点 其插入位置由查找过程得到 2020 4 7 37 1 被删除的结点是叶子 2 被删除的结点只有左子树或者只有右子树 3 被删除的结点既有左子树 也有右子树 可分三种情况讨论 4 二叉排序树的删除算法 欲删除结点 2020 4 7 38 50 30 80 20 90 85 40 35 88 32 1 被删除结点是叶子结点 例如 被删关键字 20 88 2020 4 7 39 1 被删除结点是叶子结点 2020 4 7 40 50 30 80 20 90 85 40 35 88 32 其双亲结点的相应指针域的值改为 指向被删除结点的左子树或右子树 被删关键字 40 80 2 被删除结点只有左子树或只有右子树 2020 4 7 41 2 被删除结点只有左子树或只有右子树 2020 4 7 42 3 被删除的结点既有左子树 也有右子树 中序序列CLC QLQSLSPPRF P f Lchild p Lchild S Rchild p Rchild 2020 4 7 43 二 平衡二叉树 AVL树 1 何谓 二叉平衡树 它或是一棵空树 或是具有下列性质的树 它的左子树和右子树均是平衡二叉树 且左子树和右子树的深度之差绝对不超过1 2020 4 7 44 2 平衡因子 定义为该结点的左子树深度减去右子树深度 2020 4 7 45 树中每个结点的左 右子树深度之差的绝对值不大于1 例如 5 4 8 2 5 4 8 2 1 是平衡树 不是平衡树 2020 4 7 46 3 如何构造 二叉平衡树 方法 在插入过程中 采用平衡旋转技术 2020 4 7 47 构造二叉平衡 查找 树的方法 在插入过程中 采用平衡旋转技术 例如 依次插入的关键字为5 4 2 8 6 9 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋转一次 先向右旋转再向左旋转 2020 4 7 48 4 2 6 5 8 9 6 4 2 8 9 5 向左旋转一次 继续插入关键字9 2020 4 7 49 将二叉排序树构造成平衡二叉树的方法 从第一个结点开始构造二叉树若此二叉树不是平衡二叉树 就进行 旋转 使之成为平衡二叉树 加入一个结点 构造二叉排序树 反复执行2 3直至全部结点组成一棵平衡二叉树为止 2020 4 7 50 分四种情况讨论 LL型平衡旋转RR型平衡旋转LR型平衡旋转RL型平衡旋转 2020 4 7 51 1 LL型平衡旋转 由于在A的左子树的左子树中插入新结点 使A的平衡因子由1变为2 只需按图顺时针旋转 A 2020 4 7 52 2 RR型平衡旋转 由于在A的右子树的右子树中插入新结点 使A的平衡因子由 1变为 2 只需按图逆时针旋转 3 LR型平衡旋转 由于在A的左子树的右子树中插入新结点 使A的平衡因子由1变为2 只需按图先逆时针旋转 再顺时针旋转 4 RL型平衡旋转 由于在A的右子树的左子树中插入新结点 使A的平衡因子由 1变为 2 只需按图先顺时针旋转 再逆时针旋转 2020 4 7 55 例1 已知关键字序列为 13 24 37 90 53 试构造一棵平衡二叉树 2020 4 7 56 例2 已知关键字序列为 4 5 7 2 1 3 6 试构造一棵平衡二叉树 2020 4 7 57 9 2 2B 树和B 树 2020 4 7 58 一 B 树及查找 2020 4 7 59 1 定义 B 树是一种平衡的多路查找树 一棵m阶B 树 或为空树 或满足一下性质 树中每个结点至多有m棵子树 根结点至少有两棵子树 除非根为树叶 除根以外的所有非终端结点至少有 m 2 棵子树 所有非终端结点中包含有下列信息 n A0 K1 A1 K2 A2 Kn An 所有叶子结点都出现在同一层次上 且不带信息 2020 4 7 60 1 定义 续 n A0 K1 A1 K2 A2 Kn An 中n为关键字个数 或n 1为子树的个数 Ki i 1 2 n 为关键字 且Ki Ki 1Ai i 0 1 2 n 为指向子树根结点的指针 且指针Ai 1所指子树中所有结点的关键字均小于Ki i 1 2 n An所指子树中所有结点的关键字均大于Kn 2020 4 7 61 在m阶的B 树上 每个非终端结点可能含有 n个关键字Ki 1 i n n mn个指向记录的指针Di 1 i n n 1个指向子树的指针Ai 0 i n 多叉树的特性 2020 4 7 62 非叶结点中的多个关键字均自小至大有序排列 即 K1 K2 Kn Ai 1所指子树上所有关键字均小于Ki Ai所指子树上所有关键字均大于Ki 查找树的特性 2020 4 7 63 平衡树的特性 树中所有叶子结点均不带信息 且在树中的同一层次上 根结点或为叶子结点 或至少含有两棵子树 其余所有非叶结点均至少含有 m 2 棵子树 至多含有m棵子树 2020 4 7 64 根结点至少有2棵子树 一棵4阶B 树 其深度为4 非根结点至少有 m 2 棵 至多有m 4棵子树 2020 4 7 65 B 树的存储 一棵4阶B 树 其深度为4 2020 4 7 66 从根结点出发 沿指针搜索结点和在结点内进行顺序 或折半 查找两个过程交叉进行 若查找成功 则返回指向被查关键字所在结点的指针和关键字在结点中的位置 若查找不成功 则返回插入位置 2 B 树的查询 2020 4 7 67 例查询47 47 2020 4 7 68 在查找不成功之后 需进行插入 显然 关键字插入的位置必定在最下层的非叶结点 3 插入 2020 4 7 69 例 在下列3阶B 树中插入关键字 50 20 40 80 插入关键字 60 60 80 90 60 80 90 90 5080 60 30 40 20 305080 80 30 50 2020 4 7 70 1 生成一棵B 树 例关键字序列 32 18 43 78 11 27 39 47 53 64 99 生成一棵3阶B 树 2020 4 7 71 2 在已存在的B 树中插入关键字 在一棵3阶B 树中插入关键字 30 26 85 7 45 24 5390 312 37 50 6170 100 2020 4 7 72 和插入的考虑相反 首先必须找到待删关键字所在结点 并且要求删除之后 结点中关键字的个数不能小于 m 2 1 否则 要从其左 或右 兄弟结点 借调 关键字 若其左和右兄弟结点均无关键字可借 结点中只有最少量的关键字 则必须进行结点的 合并 4 删除 2020 4 7 73 B 树是B 树的一种变型 二 B 树 2020 4 7 74 每个叶子结点中含有n个关键字和n个指向记录的指针 并且 所有叶子结点彼此相链接构成一个有序链表 其头指针指向含最小关键字的结点 1 B 树的结构特点 2020 4 7 75 每个非叶结点中的关键字Ki即为其相应指针Ai所指子树中关键字的最大值 所有叶子结点都处在同一层次上 每个叶子结点中关键字的个数均介于 m 2 和m之间 2020 4 7 76 在B 树上 既可以进行缩小范围的查找 也可以进行顺序查找 在进行缩小范围的查找时 不管成功与否 都必须查到叶子结点才能结束 若在结点内查找时 给定值 Ki 则应继续在Ai所指子树中进行查找 2 查找过程 2020 4 7 77 类似于B 树进行 即必要时 也需要进行结点的 分裂 或 归并 3 插入和删除的操作 2020 4 7 78 5096 1550 627896 7178 848996 5662 20264350 3815 sq root 2020 4 7 79 键树的结构特点 关键字中的各个符号分布在从根结点到叶的路径上 叶结点内的符号为 结束 的标志符 因此 键树的深度和关键字集合的大小无关 键树被约定为是一棵有序树 即同一层中兄弟结点之间依所含符号自左至右有序 并约定结束符 小于任何其它符号 三 键树 2020 4 7 80 H A D S V E E R E I G H S 例如 表示关键字集合 HAD HAS HAVE HE HER HERE HIGH HIS 2020 4 7 81 9 3 1什么是哈希表 9 3 2哈希函数H key 的构造方法 9 3 3处理冲突的方法 9 3哈希表 2020 4 7 82 前面讨论的查找表各种结构的共同特点 查找的过程为给定值依次和关键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数 9 3 1什么是哈希 Hash 表 记录在表中的位置和它的关键字之间不存在一个确定的关系 2020 4 7 83 办法 预先知道所查关键字在表中的位置 对于频繁使用的查找表 希望ASL 0 即要求 记录在表中位置和其关键字之间存在一种确定的关系 2020 4 7 84 若以下标为000 999的顺序表表示之 例如 为每年招收的1000名新生建立一张查找表 其关键字为学号 其值的范围为xx000 xx999 前两位为年份 在这个例子里 学生好比记录 学号则为关键字 对关键字进行的操作则是取其末三位 用以确定记录的位置 2020 4 7 85 对于动态查找表而言 1 表长不确定 2 在设计查找表时 只知道关键字所属范围 而不知道确切的关键字 200011010264 H key 2020 4 7 86 Hash表 如果将关键字与存储地址之间建立一个对应的函数关系 以H key 作为关键字为key的记录在表中的位置 则查找将直接进行 不必与关键字比较 这种函数称为哈希Hash函数 用Hash函数建立的表称为Hash表 2020 4 7 87 1 直接定址法 3 平方取中法 5 除留余数法 4 折叠法 6 随机数法 2 数字分析法 9 3 2哈希函数的构造方法 2020 4 7 88 将H key 均匀地分布在所在地址空间的哈希函数称为一个好的Hash函数 9 3 2哈希函数的构造方法 若对于关键字集合中的任一个关键字 经Hash函数映像到地址集合中任何一个地址的概率是相等的 则称此哈希函数为均匀的哈希函数 亦即 一 一个好的哈希 Hash 函数 2020 4 7 89 二 填装因子a 标志着Hash表的装满程度 表中填入的记录个数a 哈希表的长度 a越接近1则发生冲突的可能性越大 2020 4 7 90 此法仅适合于 地址集合的大小 关键字集合的大小 三 常用的Hash函数构造方法 直接定址法 哈希函数为关键字的线性函数H key key或者H key a key b 2020 4 7 91 将关键字集合中分布均匀的数位作为存储地址 例关键字序列8120581304814078110681708 8120581304814078110681708 将关键字的3 5位作为Hash值2534471678 2 数字分析法 2020 4 7 92 将关键字值平方后取其中分布均匀的几位作为Hash值 此方法适合于 关键字中的每一位都有某些数字重复出现频度很高的现象 目的是 扩大差别 同时平方值的中间各位又能受到整个关键字中各位的影响 3 平方取中法 2020 4 7 93 例关键字key0100110012001160 keykey2H key 哈希地址 01000010000110012100001200144000011601370400 010210440370 2020 4 7 94 将关键字分割成若干部分 然后取它们的叠加和为哈希地址 有两种叠加处理的方法 移位叠加和间界叠加 此方法适合于 关键字的数字位数特别多 4 折叠法 2020 4 7 95 例 国际标准图书编号0 442 20586 4 关键字0442205864 移位叠加 直接折叠相加 5864 4220 04 10088 H key 0088 2020 4 7 96 例 国际标准图书编号0 442 20586 4 关键字0442205864 2 间界叠加 间界来回折叠相加 5864 0224 04 6092 H key 6092 2020 4 7 97 5 除留余数法 H key keymodp其中 p m 表长 设定哈希函数为 2020 4 7 98 例关键字28356377105表长 21 H key keymodpp m 1 P 21 2 P 19 3 P 17 7140140 9166110 1111293 2020 4 7 99 6 随机数法 设定哈希函数为 H key Random key 其中 Random为伪随机函数 通常 此方法用于对长度不等的关键字构造哈希函数 2020 4 7 100 实际造表时 采用何种构造哈希函数的方法取决于建表的关键字集合的情况 包括关键字的范围和形态 总的原则是使产生冲突的可能性降到尽可能地小 2020 4 7 101 1 哈希函数是一个映象 即 将关键字的集合映射到某个地址集合上 它的设置很灵活 只要这个地址集合的大小不超出允许范围即可 从上面例子可见 2 由于哈希函数是一个压缩映象 因此 在一般情况下 很容易产生 冲突 现象 即 key1 key2 而H key1 H key2 2020 4 7 102 3 很难找到一个不产生冲突的哈希函数 一般情况下 只能选择恰当的哈希函数 使冲突尽可能少地产生 因此 在构造这种特殊的 查找表 时 除了需要选择一个 好 尽可能少产生冲突 的哈希函数之外 还需要找到一种 处理冲突 的方法 2020 4 7 103 9 3 3处理冲突的方法 何为冲突 当不同的关键字取相同的Hash函数值时 称为冲突 若H key1 H key2 当key1 key2时 称为冲突 2020 4 7 104 处理冲突 的实际含义是 为产生冲突的地址寻找下一个哈希地址 1 开放地址法 2 再哈希法 2 处理冲突的方法 3种 3 链表地址法 2020 4 7 105 当发生冲突时 形成一个探查序列 并沿这个序列逐个探查 直到找到一个未使用的单元为止 这个地址称为开放地址 1 开放定址法 2020 4 7 106 1 开放定址法 H key 求得一个地址序列 H0 H1 H2 Hs1 k m 1其中 H0 H key Hi H key di MODmi 1 2 kdi为增量序列 2020 4 7 107 对增量di有三种取法 线性再探测散列当取di 1 2 3 m 1二次探测散列当取di 12 12 22 22 m 2 2 m 2 2随机探测散列当di是一组随机数列时 2020 4 7 108 例当在表长为11的Hash表中已填有关键字17 60 29 按除留余数法 H key keymodp 取P 11 插入关键字38 60 17 29 38 K key 17mod11 6 K key 60mod11 5 2020 4 7 109 例当在表长为11的Hash表中已填有关键字17 60 29 按除留余数法 H key keymod11插入关键字38 60 17 29 38 38 38 38 线性再探测散列Hi H key di mod11di 1 2 3 m 1 2020 4 7 110 例当在表长为11的Hash表中已填有关键字17 60 29 按除留余数法 H key keymod11插入关键字38 60 17 29 38 38 2 用二次探测再散列Hi H key di mod11di 12 12 22 22 m 2 2 m 2 2 2020 4 7 111 例2 关键字集合 19 01 23 14 55 68 11 82 36 设定哈希函数H key keyMOD11 表长 11 19 01 23 14 55 68 19 01 23 14 68 1 采用线性探测再散列处理冲突 2 采用二次探测再散列处理冲突 11 82 36 55 11 82 36 112136251 2020 4 7