8 数据结构-查找

、查找、查找表：通常由多个数据项组成的相同类型的数据元素(对象)的集合。键：数据元素中标识数据元素的一个或多个数据项值。如果关键字唯一标识数据元素，则关键字称为主关键字。标识多个数据元素的关键字称为次关键字。查找/搜索：根据指定的k值确定查找表中关键字等于指定值的记录或数据元素。表中有符合条件的记录：查找成功；结果：找到的记录信息或记录在查询表中的位置。查找表中不存在满足条件的记录：查找失败。查找、查找有两种基本形式：静态查找和动态查找。静态搜索：查询时仅查询或搜索数据元素。查找表称为静态查找表，适用于静态查找表的查找方法包括顺序查找、半圆形查找和散列查找。动态搜索：在实现查询的过程中，插入查找表中不存在的记录或删除查找表中的某个现有记录的查找表称为动态查找表。适合动态查找的查找方法有二进制排序树查找。查找，查找方法评估指标查找过程中的主要任务是关键字比较，查找过程中关键字的平均比较次数(平均查找长度ASL:AverageSearchLength)是衡量查找算法效率水平的标准。ASL定义为：其中：Pi:查找第一条记录的概率；Ci:寻找第I笔记录需要比较的次数。顺序查找，1查找想法从表的一端开始，逐个比较记录的关键字和给定的k值，如果记录的关键字和给定的k值相同，查找成功；否则，扫描整个表，如果没有相应的记录，查找将失败。顺序查找，2算法分析在不丢失一般性的情况下，将每个记录的成功概率设置为相同。也就是说，pi=1/n；成功查找第I个元素的比较次数ci=n-I 1；成功时平均查找长度ASL查找：查找失败时包含：查找失败比较为n 1，成功和失败概率为pi=1/(2n)时平均查找长度ASL:半查找、半查找等是更有效的查找方法。前提条件：查找表中的所有记录均按关键字(升序或降序)排序。查找过程中，确定要在表中查找的记录的范围，然后逐步缩小范围，直到找到或找不到记录(将每次要检查的记录所在的地块减少一半)。寻找一半，1寻找想法以Low=1，High=n表示要寻找区域的下限、上限和中间位置指标。抓住中间位置mid=(low high)/2；中间位置记录的关键字与指定k值的比较：相同：查找成功；大于：将记录在范围的前半部分。修改上限指针：High=Mid-1，然后按顺序进行；小于：确认在间隔的后半部分记录，修改下限指针：Low=Mid 1，转；到边界外找不到。寻找一半，寻找成功范例，寻找一半，寻找失败范例，寻找一半，2。算法分析在查找时，每次进行比较，查找范围缩小一半，此过程可以用一个二叉树表示：根节点是进行比较的第一个中间位置的记录；作为左侧子树的节点，行在中间位置之前；右子树，中间位置后面的节点行；每个子树都相同。这样得到的二叉树称为决策树。补充二进制树的二次一层的节点，使二进制树充满。深度不变。h=2(n 1)。半查找，已知为全二叉树特性，层I的节点数为2i-1(Ih)，设置表中每个记录的查找概率相同。也就是说，Pi=1/n，成功时的平均查找长度ASL: n非常大(n50)时的ASL-2(n 1)-1。，第二排序树搜索，第二排序树，也称为第二搜索树，或空树；或者，它可以是具有以下特征的二进制树：1.如果左侧子树不为空，则左侧子树中的所有节点值都小于相应的根节点值。2.如果右侧子树不为空，则右侧子树中的所有节点值都大于根节点值。左侧和右侧的子树也分别是辅助排序树。查找第二排序树，1。查找二级排序树在二级树中查找最大最小元素非常简单。在根节点向左移动，直到不能再前进为止，您可以取得最小值。从根节点继续向右走，可以得到最大值，直到没有路可走为止。查找第二排序树，2。第二对齐树插入新元素时，可以从根节点开始，然后向左移动关键点值(如果关键点值较大)、向右移动关键点值(如果关键点值较小)、向右移动到结束位置，最后移动到插入点。第二排序树查询，3。删除辅助排序树对辅助排序树中节点a的删除分为两个方案：(1)如果a只有一个子节点，则将a的子节点直接连接到a的父节点，然后删除a。查找第二排序树，3。删除辅助排序树如果a有两个子节点，则将a替换为右侧子树中的最小节点。搜索辅助排序树，4。次排序树性能分析高度为H的次排序树的插入和删除操作运行时间为O(H)。但是，在最坏的情况下，构成二进制排序树的输入顺序已排序，形成倾斜的单个树。二进制排序树的性能明显下降，树的高度增加到元素数n。如下图所示，(a)的查询成功平均查询长度为ASL=(1 2 * 2 3 * 4 * 3)/10=2.9 (b)的查询成功平均查询长度为ASL=(1 2 3 5 7 8 9 10)/10=5.5如果二进制排序树是单个分支树，则平均查找长度与单个链接列表相同，且为O(n)。如果次排序树的左右子树的高度差不超过1，则此类次排序树称为平衡二进制树。他的平均查询长度达到O(log2n)。二进制树平衡、二进制树平衡或空树，或者满足以下特性的二进制树：:左侧和右侧子树深度之间的差异，绝对值不大于1。:左右子树也是平衡二叉树。BalanceFactor:二进制树中节点的左侧子树深度减去右侧子树深度的节点的平衡因子。因此，平衡二叉树中每个节点的平衡因子可以是-1、0和1。否则，只要一个节点的平衡因子的绝对值大于1，二叉树就不是平衡二叉树。如果二进制排序树既是二进制排序树又是平衡二进制树，则称为平衡二进制排序树。平衡的二叉树，1。平衡旋转典型的二进制排序树，如果通过不平衡、某种方法既可以保持排序又可以保持平衡，则寻找一种构建平衡的二进制排序树(称为平衡旋转)的方法。平衡的二叉树，1。平衡旋转LL类型平衡旋转将a的位置替换为b，a成为b右侧子树的根节点，b原始右侧子树用作a的左侧子树。平衡二叉树，1。平衡旋转LR类型平衡旋转绕b逆时针旋转(将根b的子树旋转到c)，绕a顺时针旋转，如图9-8所示。绕c旋转整个子树。b是c的左侧子树，a是c的右侧子树。c的右侧子树移动到a的左侧子树位置，c的左侧子树移动到b的右侧子树位置。平衡二叉树，1。平衡旋转RL类型平衡旋转从b顺时针旋转，从a逆时针旋转，如图9-9所示。将整个子树(a作为根)旋转到c，a作为c的左侧子树，b作为c的右侧子树；c的右侧子树移动到b的左侧子树位置，c的左侧子树移动到a的右侧子树位置。，平衡的二叉树，1。平衡旋转RR类型平衡旋转将a的位置替换为b，将a替换为b的左侧子树的根节点，将b的原始左侧子树替换为a的右侧子树。散乱的列表，1基本思想：在存储的地址和相应关键字之间建立明确的对应关系；这样，无需进行比较即可查找通过一次访问检索到的元素。示例30个地区的民族人口统计信息，使用数字作为关键字，配置散列函数：H(key)=keyH(1)=1，H(2)=2，使用区域名称中第一个拼音字符的序列号作为散列函数：H(beeh)散列函数是从关键字空间到存储地址空间的图像类型。可写：addr(ai)=H(ki)。其中I是表格的一个元素，addr(ai)是ai的位址，ki是ai的关键字。哈希表：通过应用散列函数、使用记录的关键字确定表中记录的地址，并将记录放入此地址而构成的表称为哈希表。散列查找(也称为散列查找):使用散列函数查找的过程称为散列查找。冲突：ki，对于kj，ki(kj)不同，但H(ki)=H(kj)的现象称为冲突。同义字：具有相同函数值的两个不同关键字，称为杂凑函数的同义字。散列函数通常是压缩图像，因此冲突是不可避免的，可以最小化。发生冲突时，必须有处理冲突的方法。决定散列函数的范围设计包含散列列表的空间范围的分布式列表。针对函数值可能的所有元素(记录的关键字)，配置相应的哈希函数，使其位于分布式列表的地址空间内，并尽可能少地发生冲突。冲突处理方法。发生冲突时如何解决？构成、散列函数、2的散列函数是具有灵活设置的图像，只要任意关键字的散列函数值位于表长度的允许范围内。散列函数“好与坏”的主要评价因素如下。散列函数的构造很简单；可以将散乱的列表的关键字“均匀”映射到地址空间。所谓统一，是指发生冲突的可能性最小。(1)直接寻址方法使用密钥或关键字的线性函数之一作为散列地址。换句话说，h (key)=密钥或H(key)=akey b(a，b是常量)特征：直接寻址方法获得的地址集与密钥集大小相同，没有冲突，但实际上很少使用。(2)数值分析分析关键字，将关键字的多个位或组合用作散列地址。如果关键字位数大于散列地址位数，并且预先知道可能出现的关键字，则适用。散乱的列表，(3)平方，将关键字平方，然后把中间带到散列地址。如果一平方后的几个中间和每个数字相关，则随机分布的关键字创建的散列地址也是随机的。散列函数选择的位数取决于哈希表的长度。这种方法适用于不知道全部关键字的情况，是比较普通的方法。(4)折叠将关键字分成相同数量的部分(最后的部分可能不同)，并导入该部分的嵌套和哈希地址。数字叠加有移位叠加和边界叠加。移位叠加：拆分后添加低排列的一部分。复叠边界：沿分割边界前后折叠，从一端到另一端，然后对齐总和。适用于关键字位数很多，数字几乎均匀分布在每个位上的情况。用作散列地址的哈希表(h (key)=key modp (pm)是一种简单的散列函数构建方法，其中，除残差方法外，关键字不大于哈希表长度m的p的数量评估了关键字。这个方法的核心是p的选择，p的选择不好，很容易产生同义词。对p的选择分析：p=2i(pm)选择：运算可以用移位轻松完成，但相当于忽略关键字的高值，只留下低二进制数。高关键字和低关键字是同义词。如果p=选择qf (q，f都是小数，pm)，则包含q或f因子的所有关键字的散列地址都是q或f的倍数。选择p作为小数或p=qf (q，f为小数，全部为20，大于pm):通过常规选择方法，可以减少碰撞的可能性。超差列表、3冲突处理的方法冲突处理：发生冲突时，查找冲突元素的其他存储位置。(1)开放式寻址方法基本方法：发生冲突时形成探测顺序；按此序列逐个检查分布式列表中的其他地址，直到找到指定的关键字或空地址(打开的地址)，然后将冲突记录放在该地址。散列地址是Hi(key)=(H(key) di)MODm，I=1，2，按k (km-1)计算。其中H(key):散列函数；m:批量列表长度；Di:第I个探测的增量序列；Hi(key):第I次检测后获取的散列地址。分布列表，线性探针方法是分布列表t 0.将m-1视为循环矢量。如果发生冲突，则在第一次发生冲突的位置循环访问其他地址。增量序列为di=1，2，3，如果m-1将第一个冲突的地址设置为h，则依次检测Th 1、t h 2，直到Tm-1循环回标题为止，再次检测T0、t 1，直到Th-1探测过程终止的情况如下：检测到的地址为空：表中没有记录。寻找时失败；如果插入，则将记录写入该地址。找到的地址包含指定的关键字。如果找到，则成功。插入失败。 Th:仍然没有检测到空地址或给定的关键字，散列表已满。散列函数：h(密钥)=密钥mod 7，崩溃处理为7，记录密钥组：15，14，28，26，56，23，散列函数：h(密钥)=密钥mod 7。解决方法：h(15)=15 mod 7=1h(14)=14 mod 7=0h(28)=28 mod 7=0冲突H1(28)=1和冲突H2 (28)缺点：导致冲突的每个记录都解析为最接近冲突的空地址，因此冲突的可能性更大(这种现象称为冲突“集合”)。哈希表，辅助探测增量顺序为di=1，-1，2，-2，3，k (km/2)在上例中，如果使用辅助探测方法处理碰撞，则H(15)=15 mod 7=1h(14)=14 mod 7=0h(28)=28 mod 7=0碰撞H1()缺点：不能保证批量列表中的所有地址都被检测到。分散列表，散列构造多个散列函数，并使用其他散列函数计算下一个新散列地址，