数据结构与算法第8章查找.pptVIP

第8章 查找 实施查找时有两种不同的环境 静态环境 查找结构不用插入和删除操作 ? 静态查找表 查找算法的评价指标 查找成功:最少比较次数 最多比较次数 平均比较次数 查找失败:最少比较次数 最多比较次数 平均比较次数 基于有序顺序表的折半查找 设n个对象存放在一个有序顺序表中，并按其关键码从小到大排好了序 折半查找时, 先求位于查找区间正中的对象的下标mid，用其关键码与给定值x比较 1.elem[mid]==x 查找成功 2.elem[mid]x 把查找区间缩小到表的前半部分，继续折半查找 3.elem[mid]x 把查找区间缩小到表的后半部分，继续折半查找 如果查找区间已缩小到没有对象，仍未找到想要查找的对象，则查找失败 二叉排序树的插入算法 根据动态查找表的定义，“插入”操 作在查找不成功时才进行； 结点的平衡因子(balance factor) 每个结点附加一个数字, 给出该结点左子树的高度减去右子树的高度所得的高度差, 这个数字即为结点的平衡因子 AVL树任一结点平衡因子只能取 -1, 0, 1 如果一个结点的平衡因子的绝对值大于1, 则这棵二叉查找树就失去了平衡, 不再是AVL树 如果一棵二叉查找树是平衡的, 且有 n个结点，其高度可保持在 O(log2n),平均查找长度也可保持在O(log2n) 平衡化旋转 如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化 平衡化旋转有两类： 单旋转 (左旋和右旋) 双旋转 (左旋加右旋和右旋加左旋) 哈 希 查 找 (Hash) 以上讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系 查找的过程为给定值依次和关 键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数 用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同 只有一个办法：预先知道所查关键字在表中的位置 对于频繁使用的查找表，希望 ASL = 0 即，要求：记录在表中位置和其关键字之间存在一种确定的关系 在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 H(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 H(key) 为哈希函数 ※哈希函数是一个映象，即：将关键 字的集合映射到某个地址集合上，它 的设置很灵活，只要这个地址集合的 大小不超出允许范围即可 ※由于哈希函数是一个压缩映象，因 此，在一般情况下，很容易产生 “ 冲 突 ” 现象，即： key1? key2，而 H(key1) = H(key2) 4 2 6 5 8 9 6 4 2 8 9 5 向左旋转一次 继续插入关键字 9 在平衡树上进行查找的过程和二叉 排序树相同，因此，查找过程中和给定 值进行比较的关键字的个数不超过平衡 树的深度。 平衡树的查找性能分析： 问：含 n 个关键字的二叉平衡树可 能达到的最大深度是多少？ n = 0 空树 最大深度为 0 n = 1 最大深度为 1 n = 2 最大深度为 2 n = 4 最大深度为 3 n = 7 最大深度为 4 先看几个具体情况: 反过来问，深度为 h 的二叉平衡树 中所含结点的最小值 Nh 是多少？ h = 0 N0 = 0 h = 1 h = 2 h = 3 一般情况下 N1 = 1 N2 = 2 N3 = 4 Nh = Nh-1 + Nh-2 + 1 利用归纳法可证得 Nh = Fh+2 - 1 因此，在二叉平衡树上进行查找时， 查找过程中和给定值进行比较的关键字 的个数和 log(n) 相当。 由此推得，深度为 h 的二叉平衡树中所含结点的最小值 Nh = ?h+2/5 - 1。 反之，含有 n 个结点的二叉平衡树 能达到的最大深度 hn = log?(?5 (n+1)) - 2。 B - 树 B-树（Balanced Tree）是一种平衡的多叉树，由R. Bayer和E. Mccreight在1970年提出的。 B-树是一种 平衡 的 多路 查找 树 在 m 阶的B-树上，每个非终端结点可能含有：