查找-数据结构.ppt

第九章查找 静态查找表动态查找表哈希表 查找的基本概念和术语 查找的基本概念和术语查找表 由同一类型的数据元素 或记录 构成的集合 静态查找表 若对查找表只作查找操作 则称此类查找表为静态查找表 动态查找表 若在查找过程中同时插入表中不存在的数据元素 或者从查找表中删除已经存在的某个数据元素 则称此类查找表为动态查找表 关键字 数据元素中某个数据项的值 用它可以标识一个数据元素 若此关键字可以唯一的标识一个记录 则称此关键字为主关键字 反之 称用以识别若干记录的关键字为次关键字 当数据元素只有一个数据项时 其关键字即为该数据元素的值 查找 根据给定的某个值 在查找表中确定一个其关键字等于给顶值的记录或数据元素 若表中存在这样的一个记录 则称查找是成功的 此时查找的结果为给出整个记录的信息 或指示该记录在查找表中的位置 若表中不存在关键字等于给定值的记录 则称查找不成功 此时查找的结果可给出一个 空 记录或 空 指针 平均查找长度 为确定记录在查找表中的位置 需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度 简称ASL 对于含有n个记录的表 查找成功时的平均查找长度为 其中 Pi为查找表中第i个记录的概率 Ci为找到表中其关键字与给定值相等的第i个记录时和给定值已进行过比较的关键字个数 静态查找表 顺序查找的基本思想 从表的一端开始 顺序扫描线性表 依次将扫描到的结点关键字和待找的值K相比较 若相等 则查找成功 若整个表扫描完毕 仍末找到关键字等于K的元素 则查找失败 顺序表的类型描述 definemax1024typedefintElemType typedefstruct ElemTypedata max 0号单元留空 intlength SSTable 算法实现 intST search SSTableST KeyTypekey inti ST elem 0 key key 设置监视哨 当从表尾向前查找失败时 不必判别是否检测完毕 i ST length while ST elem i key key i returni 设置监视哨的目的在于免去查找过程中每一步都要检测整个表是否查找完毕 以提高算法的执行效率 性能分析对于含有n个记录的顺序表 在等概率情况下进行顺序查找的查找成功的平均查找长度为 假设查找成功和查找不成功的可能性相同 对每个记录的查找概率也相同 则此时顺序查找的平均查找长度为 折半查找的查找过程将待查的key值和有序表ST data low high 的中间位置mid上的结点的关键字进行比较 若相等 则查找成功 返回该结点的下标mid否则 若keyST data mid 则在右子表ST data mid 1 high 中继续进行折半查找 这样 经过一次关键字比较就缩小一半的查找区间 如此进行下去 直到找到关键字为key的结点 或者当前的查找区间为空 查找失败 有序表的查找 例如 已知如下11个数据元素的有序表 05 13 19 21 37 56 64 75 80 88 92 现要查找关键字为21和85的数据元素 假设指针low和high分别指示待查元素所在区间的下界和上界 指针mid指示区间的中间位置 mid low high 2 查找21 查找85 算法实现intSearch bin SSTableST KeyTypekey low 1 high ST length while low high mid low high 2 if key ST elem mid key return mid elseif key ST elem mid key high mid 1 elselow mid 1 return 0 性能分析 6 1 39 2 14710 3 25811 4 二分查找的查找过程可以用一棵二叉树来描述 其中 树中的每个结点表示一个记录 结点中的值为该记录在表中的位置 通常称这个描述查找过程的二叉树为判定树 判定树的构造过程 把整个查找区间的中间位置作为根结点 左子表或右子表的中间位置作为根的左孩子或右孩子 依此类推 得到的二叉树即为描述二分查找的判定树 6 由此可见 二分查找过程恰好是走了一条从判定树的根到被查结点的路径 比较的关键字个数恰为该结点在判定树中的层数 具有11个元素的有序表进行二分查找时 查找成功时的时间复杂度 如果在二分查找的判定树中的所有结点的空指针域上加上一个指向一个方形结点的指针并称这些方形结点为外部结点 与之相对 称那些圆形结点为内部结点 那么折半查找时查找不成功的过程就是走了一条从根结点到外部结点的路径 和给定值进行比较的关键字的个数等于路径上内部结点的个数 判定树非完全二叉树 但它的叶子结点所在的层次之差最多为1 则n个结点的判定树的深度和n个结点的完全二叉树的深度相同 这般查找在查找成功和查找失败时进行比较的关键字个数最多不超过树的深度 而具有n个结点的判定树的深度为 log2n 1 因此折半查找的平均时间复杂度为O log2n 顺序查找与折半查找比较 1 顺序查找的查找表既可以采用顺序存储结构 又可以采用链式存储结构 折半查找的查找表只能采用顺序存储结构 2 顺序查找大查找表可以是有序的也可以是无序的 折半查找的查找表必须是有序的 索引顺序表的查找 元素分块有序建立索引表 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 22 12 索引表 索引顺序表的查找 分块查找 在索引顺序表中查找指定元素时 分两步 先在索引表中确定元素所在的块 再在块中顺序查找 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 22 12 索引表 索引顺序表的查找 分块查找 在索引顺序表中查找指定元素时 分两步 先在索引表中确定元素所在的块 再在块中顺序查找 索引顺序表的查找 分块查找 设查找表中的元素可均匀地分为b块 每块含有s个记录若在索引表和块内都进行顺序查找 则 实际上 在索引表中可进行折半查找 动态查找表 二叉排序树 二叉排序树或者是一棵空树 或者是具有下列性质的二叉树 若它的左子树不空 则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空 则右子树上所有结点的值均大于它的根结点的值 它的左 右子树也分别为二叉排序树 例如 中序遍历序列 91318252931395260 二叉排序树的特点 中序遍历二叉排序树得到的关键字序列是一个递增的有序序列 基本思路 若二叉排序树为空 则查找失败 若key等于当前根结点的值 则查找成功 若key小于当前根结点的值 在继续在根的左子树中查找 若key大于当前根结点的值 在继续在根的右子树中查找 如何在二叉排序树中查找给定关键字值为key的结点 在二叉排序树中查找关键字值为29和30的过程 29 9 25 60 39 13 52 31 18 查找29 查找30 29 9 25 60 39 13 52 31 18 二叉排序树的插入基本思想 若二叉排序树为空 则待插结点作为根结点插入到空树中 若待插结点的关键字值和根结点的关键字值相等 则说明树中已有此结点 无需插入 若待插结点的关键字值小于根结点的关键字值 则将待插结点插入到根的左子树中 若待插结点的关键字值大于根结点的关键字值 则将待插结点插入到根的右子树中 如此进行下去 直到把待插结点作为一个叶结点插入到二叉排序树中 或直到发现树中已存在该结点为止 在二叉排序树中插入58和39 29 9 25 60 39 13 52 31 18 插入58 58 插入39 29 9 25 60 39 13 52 31 18 58 对给定的关键字序 7 16 4 8 20 9 6 18 5 构造一棵二叉排序树 二叉排序树的生成是从空的二叉排序树开始 每输入一个数据 建立一个新结点 插入到当前已经生成的二叉排序树中 输入数据 7 16 4 20 8 9 18 6 5 6 20 8 4 16 7 5 9 18 7 二叉排序树的删除如何在二叉排序树上删除一个结点 从二叉排序树中删除一个结点时 首先进行查找 以确定被删结点是否在二叉排序树中 若不在 则不做任何处理 否则 设找到的被删结点是 p 其双亲结点为 f 删除操作可按下列3种情况进行处理 设 p是 f的左子树 1 若 p为叶子结点 直接删除即可 45 12 53 3 37 100 90 24 61 78 60 删除24 f p f lchild null deletep 2 若 p结点只有左子树PL或只有右子树PR 此时只要令PL或PR直接成为 f的左子树即可 p F P f PL a p F P f PR F f PL PR F f b 3 若 p的左右子树均不空 可以有两种处理方法 A 令 p的左子树作为 f的左子树 而 p的右子树作为 s的右子树 s是 p的中序前驱结点 c F P f PR C p CL Q QL S SL q s c F f PR C CL Q QL S SL q s B 令 p的中序前驱 s代替 p 然后再从二叉排序树中删除 s c F P f PR C p CL Q QL S SL q s c F S f PR C p CL Q QL SL q 29 9 25 60 39 13 52 31 18 删除60 删除52 39 删除13 p f 9 29 18 25 29 18 25 s 29 9 25 60 39 13 52 31 18 删除31 29 p s 二叉排序树的查找分析下面两棵二叉排序树分别由序列 12 24 37 45 53 93 和序列 45 24 53 12 37 93 构成 计算其平均查找长度 由此可见 在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关 在最坏情况下二叉排序树是通过把一个有序表的n个结点依次插入而生成的 此时所得的二叉排序树退化为深度为n的单支树 它的平均查找长度和顺序查找相同 亦是 n 1 2 在最好的情况下 二叉排序树在生成的过程中 树的形态比较匀称 最终得到的是一棵形态与判定树相似的二叉排序树 此时它的平均查找长度大约是log2n 如果所建二叉排序树的形态和折半查找的判定树相似 平均查找长度和log2n是等数量级的 尚需在构造二叉排序树的过程中进行平衡化处理 成为平衡二叉树 如何构造平衡二叉树 平衡二叉树 平衡二叉树又称AVL树 它或者是一棵空树 或者是具有下列性质的二叉树 它的左右子树都是平衡二叉树 且左 右子树深度之差的绝对值不超过1 平衡因子 二叉树上任一结点的左子树深度与右子树深度之差 平衡二叉树的特点 平衡二叉树中所有结点的平衡因子只可能是0 1 1 1 1 0 0 0 0 0 0 0 平衡二叉树 0 0 0 0 0 0 0 0 0 1 2 非平衡二叉树 如何构造平衡二叉树呢 在构造平衡二叉树的过程中 每当插入一个结点时 首先检查是否因插入而破坏了树的平衡性 若是 则找出其中最小不平衡子树 在保持排序树特性的前提下 调整最小不平衡子树中各结点之间的链接关系 以达到新的平衡 所谓最小不平衡子树是指离插入结点最近 且平衡因子绝对值大于1的结点为根的子树 输入序列为 13 24 37 90 53 构造平衡二叉排序树的过程 90 37 53 24 13 13 37 24 练习 对给定的数列R 7 16 4 8 20 9 6 18 5 构造一棵平衡二叉树 B 树B 树 B 树的定义一棵m阶的B 树 或为空树 或为满足下列特性的m叉树 1 树中每个结点至多有m棵子树 2 若根结点不是叶子结点 则至少有两棵子树 3 除根结点之外的所有非终端结点至少有 m 2 棵子树 4 所有的非终端结点中包含以下信息数据 n A0 K1 A1 K2 Kn An 其中 Ki i 1 2 n 为关键字 且Ki Ki 1 Ai为指向子树根结点的指针 i 0 1 n 且指针Ai 1所指子树中所有结点的关键字均小于Ki i 1 2 n An所指子树中所有结点的关键字均大于Kn m 2 1 n m 1 n为关键字的个数 5 所有的叶子结点都出现在同一层次上 并且不带信息 可以看作是外部结点或查找失败的结点 实际上这些结点不存在 指向这些结点的指针为空 一棵4阶的B 树 t B 树的查找B 树的查找类似二叉排序树的查找 所不同的是B 树每个结点上是多关键字的有序表 在到达某个结点时 先在有序表中查找 若找到 则查找成功 否则 到按照对应的指针信息指向的子树中去查找 当到达叶子结点时 则说明树中没有对应的关键字 查找失败 即在B 树上的查找过程是一个顺指针查找结点和在结点中查找关键字交叉进行的过程 例如 在下图所示的B 树中查找关键字47和23的过程 t 查找47 查找23 B 树的查找包含两种基本操作 在B 树中找结点 在结点中找关键字 B 的插入在B 树上插入关键字与在二叉排序树上插入结点不同 关键字的插入不是在叶结点上进行的 而是首先在最底层的某个非终端结点中添加一个关键字 若该结点的关键字个数不超过m 1 则插入完成 否则 若该结点的关键字个数已达到m个 这与B 树定义不符 将引起结点的 分裂 分裂方法为 将结点中的关键字分成三部分 使得前后两部分的关键字个数均大于等于 m 2 1 而中间部分只有一个关键字 前后两部分成为两个结点 而中间部分的关键字将插入到父结点中 若插入父结点而使父结点中关键字个数超过m 1 则父结点继续分裂 直到插入某个父结点 其关键字个数小于m 分裂 45 24 5390 312 37 50 6770 100 插入30 t 3037 例如 在下面的3阶的B 树上依次插入结点30 26 85和7的插入过程 45 24 5390 312 3037 50 6770 100 t 插入26 263037 2430 26 37 45 2430 5390 312 37 50 6770 100 t 插入85 26 677085 537090 67 85 4570 53 90 50 61 85 100 4570 2430 90 312 37 53 t 插入7 50 50 50 50 26 3712 72430 3 12 90 53 t 插入7 50 50 50 50 244570 30 7 3 12 26 37 45 24 70 B 树的删除删除最底层的某个非终端结点中的关键字如果被删关键字所在的节点中的关键字数目不小于 m 2 则只须从该结点中删除该关键字 删除完成 45 24 5390 312 37 50 6770 100 删除关键字67 70 B 树的删除删除最底层的某个非终端结点中的关键字如果被删关键字所在的节点中的关键字数目不小于 m 2 则只须从该结点中删除该关键字 删除完成 否则要进行 合并 结点的操作 可以按照下列两种情况进行处理 若右兄弟 或左兄弟 结点中的关键字数目大于 m 2 1 则需将兄弟结点中的最小 或最大 的关键字上移至双亲结点中 而将双亲结点中小于 或大于 且紧靠该上移关键字的关键字下移至被删关键字所在结点 45 24 5390 312 37 50 6770 100 t 一棵3阶的B 树 删除关键字50 70 6790 53 若与该结点相邻的兄弟结点中关键字数目等于 m 2 1 假设该结点有右兄弟 且其右兄弟结点的地址由双亲结点中的指针Ai所指 则在删除关键字之后 他所在结点中剩余的关键字和指针 加上双亲结点中的关键字ki一起合并到Ai所指的兄弟结点中 若没有右兄弟 则合并到左兄弟中 45 24 5390 312 37 53 6770 100 t 一棵3阶的B 树 删除关键字53 70 6790 6770 90 删除非最底层结点的关键字若删除非底层结点中的关键字Ki 则可以指针Ai所指子树中的最小关键字X替代Ki 直到这个X在最底层结点上 然后 再删除关键字X 即转为第一种情形 45 24 5390 312 37 6770 100 t 一棵3阶的B 树 删除关键字45 90 67 70 67 练习 从下图所示的5阶的B 树中依次删除68 76 7 画出删除后的B 树 5阶B 树 B 树一棵m阶的B 树和m阶的B 树的差异在于 有n棵子树的结点中含有n个关键字 所有的叶子结点中包含了全部关键字的信息 及指向含有这些关键字结点的指针 且叶子结点本身依关键字的大小自小而大的顺序链接 所有的非终端结点可以看成是索引部分 结点中仅含有其子树根结点中最大 或最小 关键字 一棵3阶的B 通常在B 树上有两个头指针 一个指向根结点 另一个指向关键字最小的叶子结点 因此 可以对B 树进行两种查找运算 一种是从最小关键字起顺序查找 另一种是根结点开始 进行随机查找 在B 树上进行随机查找 插入和删除的过程基本上与B 树类似 只是在查找时 若非终端结点上的关键字等于给定值 并不终止 而是继续向下直到叶子结点 因此 在B 树 不管查找成功与否 每次查找都是走了一条从根到叶子结点的路径 哈希表 哈希 Hash 又称散列 它既是一种查找方法 又是一种存贮方法 称为散列存贮 散列存贮的内存存放形式也称为哈希表或散列表 它的基本思想是 以结点的关键字k为自变量 通过一个确定的函数H 计算出对应的函数值H k 作为结点的存储位置 将结点存入H k 所指的存储位置上 散列查找 与前面介绍的查找方法完全不同 前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法 而散列查找是通过计算哈希函数来得到待查关键字的地址 理论上讲 在哈希表中查找元素无须进行关键字间的比较 例如 要找关键字为k的元素 则只需求出函数值H k H为给定的哈希函数 H k 代表关键字k在存贮区中的地址 假设有一批关键字序列18 75 60 43 54 90 46 给定哈希函数H k k 13 存贮区的内存地址从0到15 则可以得到每个关键字的散列地址为 H 18 18 13 5H 75 75 13 10H 60 60 13 8H 43 43 13 4H 54 54 13 2H 90 90 13 12H 46 46 13 7于是 根据散列地址 可以将上述7个关键字序列存贮到一个一维数组HT 哈希表或散列表 中 具体表示为 例如 9 3哈希表 散列表 因此 一个散列结构是一块地址连续的存储空间 它与一个称为散列函数的函数相关联 该函数是数据记录的关键字到地址空间的映射 这种存储空间的使用方式 使得存储记录时 通过散列函数计算出记录的存储位置并按此存储位置存储记录记录位置 Hash 记录的关键字 Hash 关键字 地址 2 访问记录时 同样利用散列函数计算存储位置 然后根据所计算出的存储位置访问记录 冲突和同义词若某个哈希函数H对于不同的关键字key1和key2得到相同的哈希地址 这种现象称为冲突 而发生冲突的这两个关键字则称为该哈希函数的同义词 用哈希法存储的线性表叫做哈希表 上述的H函数称为哈希函数 H k 称为哈希地址 通常哈希表的存储空间是一个一维数组 哈希地址是数组的下标 key1 key2 但是 H key1 H key2 冲突 key1 key2同义词 9 3 2散列函数的构造方法 好 的散列函数是指 对于关键字集合中的任意一个关键字 经散列函数映像到地址集合中任意一个地址的概率是相等的 称此类散列函数为均匀的哈希函数 常用的散列函数构造方法有 1 直接定址法可表示为H key a key b 其中a b均为常数 这种方法计算特别简单 并且不会发生冲突 但当关键字分布不连续时 会出现很多空闲单元 会将造成大量存贮单元的浪费 9 3 2散列函数的构造方法1 直接定址法 2 数字分析法分析关键字的各个位的构成 截取其中若干位作为散列函数值 尽可能使关键字具有大的敏感度 通过对上述关键字序列分析 发现第4 5 6位的敏感度较大 于是有 H 99346532 465H 99372242 722H 99387433 874H 99301367 016H 99322817 228 9 3 2散列函数的构造方法1 直接定址法2 数字分析法 3 平方取中法这种方法是先求关键字的平方值 然后在平方值中取中间几位为散列函数的值 因为一个数平方后的中间几位和原数的每一位都相关 因此 可以使用随机分布的关键字得到的记录的存储位置也是随机的 9 3 2散列函数的构造方法1 直接定址法2 数字分析法3 平方取中法 4 折叠法将关键字分割成位数相同的几部分 最后一部分的位数可以不同 然后取这几部分的叠加和 舍去进位 作为散列函数的值 称为折叠法 例如 假设关键字为某人身份证号码430104681015355 则可以用4位为一组进行叠加 即有5355 8101 1046 430 14932 舍去高位 则有H 430104681015355 4932 9 3 2散列函数的构造方法1 直接定址法2 数字分析法3 平方取中法4 折叠法 5 除留余数法该方法的散列函数形式为 5 除留余数法 续 除留余数法计算简单 适用范围广 是一种最常使用的方法 这种方法的关键是选取较理想的p值 使得每一个关键字通过该函数转换后映射到散列空间上任一地址的概率都相等 从而尽可能减少发生冲突的可能性 一般情形下 取p为一个素数较理想 经验表明 p为1 1n 1 7n之间的一个素数较好 其中n为哈希表中待装入的元素个数 6 随机法选择一个随机函数 取关键值的随机函数值为它的哈希地址 即H key random key 9 3 2散列函数的构造方法 三 处理冲突的方法1 开放定址法用开放地址法解决冲突的做法是 当发生冲突时 使用某种探测技术在哈希表中形成一个探测序列 沿此序列逐个单元查找 直到找到给定的关键字或者遇到一个开放的地址 即该地址单元为空 为止 开放地址法的一般形式为 Hi H key di mi 1 2 3 m 1其中 H key 为哈希函数 m为哈希表的表长 di为增量序列 可以有下列三种取法 1 di 1 2 3 m 1 称线性探测再散列 2 di 12 12 22 22 32 k2 k2 k m 2 称二次探测再散列 3 di 伪随机数 称伪随机探测再散列 已知哈希表的空间为0 14 将关键字序列 19 14 23 01 68 20 84 27 55 11 10 79 按哈希函数H key key 13和线性探测法处理冲突构造所得的哈希表 19 14 23 01 68 20 84 27 55 11 10 79 H 19 19 13 6 19 H 14 14 13 1 14 H 23 23 13 10 23 H 01 01 13 1 H1 1 1 15 2 1 H 68 68 13 3 68 H 20 20 13 7 20 H 84 84 13 6 H1 6 1 15 7 H2 6 2 15 8 84 H 27 27 13 1 H1 1 1 15 2 H2 1 2 15 3 H3 1 3 15 4 27 H 55 55 13 3 H1 3 1 15 4 H2 3 2 15 5 55 H 11 11 13 11 11 H1 10 1 15 11 H2 10 2 15 12 H 10 10 13 10 10 H3 1 3 15 4 H1 1 1 15 2 H2 1 2 15 3 H 79 79 13 1 H4 1 4 15 5 H5 1 5 15 6 H6 1 6 15 7 H7 1 7 15 8 H8 1 8 15 9 79 练习 已知一组关键字为 39 23 41 38 44 15 68 12 06 51 25 则按哈希函数H key key 13和线性探测处理冲突构造所得的哈希表HT 0 14 已知哈希表的空间为0 14 将关键字序列 19 14 23 01 68 20 84 27 55 11 10 按哈希函数H key key 13和二次探测法处理冲突构造所得的哈希表 19 14 23 01 68 20 84 27 55 11 10 H 19 19 13 6 19 H 14 14 13 1 14 H 23 23 13 10 23 H 01 01 13 1 H1 1 1 15 2 01 H 68 68 13 3 68 H 20 20 13 7 20 H1 6 1 15 7 H 84 84 13 6 H2 6 1 15 5 84 H1 1 1 15 2 H 27 27 13 1 H2 1 1 15 0 27 H1 3 1 15 4 H 55 27 13 3 55 H 11 11 13 11 11 H2 10 1 15 9 H1 10 1 15 11 H 10 10 13 10 10 2 链地址法链地址法解决冲突的做法是将所有关键字为同义词的结点链接在同一个单链表中 若哈希函数的值域为0到m 1 则可将散列表定义为一个由m个头指针组成的指针数组HT m 凡是散列地址为i的结点 均插入到以HT i 为头指针的单链表中 已知哈希表的空间为0 14 将关键字序列 19 14 23 01 68 20 84 27 55 11 10 79 按哈希函数H key key 13和链地址法处理冲突构造所得的哈希表 19 14 23 01 68 20 84 27 55 11 10 H 19 19 13 6 H 14 14 13 1 H 23 23 13 10 H 01 01 13 1 H 68 68 13 3 H 20 20 13 7 H 84 84 13 6 H 27 27 13 1 H 55 27 13 3 H 11 11 13 11 H 10 10 13 10 1 开放定址法2 链地址法3 再哈希法4 公共溢出区法 按理论分析 散列查找它的时间复杂度应为O