排序二叉树的平均查找长度_设二叉排序树中有n个节点

《数据结构》复习10 查找　　一、查找　　1.1 基本概念　　1、查找　　在数据集合中寻找满足某种条件的数据素的过程称为查找　　2、查找表（查找结构）　　用于查找的数据集合称为查找表，它由同一类型的数据素（或记录）组成　　3、关键字　　数据素中唯一标识该素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的　　1.2 对查找表的常见操作　　1、查找符合条件的数据素　　2、插入、删除某个数据素　　3、图示

　　1.3 查找算法的评价指标　　1、查找长度　　在查找运算中，需要对比关键字的次数称为查找长度　　2、平均查找长度（ASL, Average Search Length）　　所有查找过程中进行关键字的比较次数的平均值　　
$ASL=\sum_{i=1}^{n}{P_iC_i}$ 　　n：数据素的个数　　
：查找第 i 个素的概率　　
：查找第 i 个素的查找长度

　　1.4 总结　　

　　二、顺序查找　　2.1 算法思想　　顺序查找，又叫“线性查找”，通常用于线性表（顺序表、链表）　　算法思想：从头到脚挨个找（或者反过来也可以）　　2.2 实现1 　　1、伪代码　　2、图示

　　2.3 实现2：哨兵　　1、代码　　2、图示

　　2.4 查找效率分析　　
$ASL_{成功}=\frac{1+2+3+...+n}{n}=\frac{n+1}{2}$ 　　
$ASL_{失败}=n+1$ 　　2.5 优化（对有序表）　　1、图示

　　2、查找效率分析

　　
$ASL_{失败}=\frac{1+2+3+...+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$ 　　3、用判定树分析 ASL 　　有 n+1 个“失败结点”，有 n 个“成功结点” 　　一个成功结点的查找长度 = 自身所在层数　　一个失败结点的查找长度 = 其父节点所在层数　　默认情况下，各种失败情况或成功情况都等概率发生　　2.6 优化（被查概率不相等）　　被查概率 7: 15%、13: 5%、19: 10%、29: 40%、37: 28%、43: 2%

　　2.7 总结　　

　　三、折半查找　　3.1 算法思想　　1、折半查找，又称“二分查找”，仅适用于有序的顺序表。　　2、图示

　　33 > mid，所以只可能在右边区域

　　33 < mid，只可能在左边区域

　　如果 high = low 的时候，mid 不等于要查找的数则会出现 low = mid +1，high = high，high < low

　　3.2 实现　　1、代码　　2、注意　　顺序表拥有随机访问的特性，链表没有。所以折半查找仅适用于有序的顺序表。　　3.3 查找效率分析　　1、构造判定树

　　2、判定树分析效率

　　3、判定树规律　　练习：若 mid = [(low+ high)/2]，画出含 1 个素、2 个素、3 个素、… 6 个素的查找表对应的折半查找判定树，注：暂不考虑失败结点（Key：右子树结点数 – 左子树结点数 = 0 或 1）

　　折半查找的判定树一定是平衡二叉树　　折半查找的判定树中，只有最下面一层是不满的。因此，素个数为 n 时树高
　　判定树结点关键字：左 < 中 < 右，满足二叉排序树的定义　　失败结点：n+1个（等于成功结点的空链域数量）

　　折半查找的时间复杂度 =
　　3.4 总结　　

　　四、分块查找　　4.1 分块查找的算法思想　　1、图示

　　2、特点　　块内无序、块间有序　　3、代码设计　　4、分块查找，又称索引顺序查找，算法过程如下：　　① 在索引表中确定待查记录所属的分块（可顺序、可折半）　　② 在块内顺序查找　　4.2 用折半查找查索引　　若索引表中不包含目标关键字，则折半查找索引表最终停在 low > high，要在 low 所指分块中查找

　　4.3 查找效率分析　　

　　假设，长度为 n 的查找表被均匀地分为 b 块，每块 s 个素，n = bs 　　设索引查找和块内查找的平均查找长度分别为
、
，则分块查找的平均查找长度为　　
　　1、用顺序查找查索引表，则
$L_I=\frac{1+2+...+b}{2}=\frac{b+1}{2}$ ，
$L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2}$ 　　则
$ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}$ ，则
$s=\sqrt{n}$ 时，
$ASL_{最小}=\sqrt{n}+1$ 　　2、用折半查找查索引表，则
，
$L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2}$ 　　则
$ASL=[log_2(b+1)]+\frac{s+1}{2}$ 　　4.4 分块查找优化　　分块查找插入和删除开销比较大，可以采用链式存储

　　4.5 总结　　

　　五、散列查找　　5.1 散列表　　散列表（Hash Table），又称哈希表，是一种数据结构，特点是：数据素的关键字与其存储地址直接相关

　　若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词” 　　通过散列函数确定的位置已经存放了其他素，则称这种情况为“冲突” 　　5.2 拉链法处理冲突　　用拉链法（又称链接法、链地址法）处理“冲突”：把所有“同义词”存储在一个链表中

　　5.3 散列查找（上）　　查找长度：在查找运算中，需要对比关键字的次数称为查找长度　　1、查找成功：

　　2、第一种查找失败：

　　3、第二种查找失败：

　　4、平均查找长度计算

　　冲突越多，查找效率越低

　　装填因子越大，说明散列表装的越满，越满的话平均查找长度也会越长　　5.4 常见的散列函数　　目的：尽量使得一个关键字对应一个信息。　　散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低　　1、除留余数法：H(key) = key % p 　　散列表表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p （设计目标——让不同的关键字的冲突尽可能地少）　　质数又称素数。指除了1和此整数自身外，不能被其他自然数整除的数

　　用质数取模，分布更均匀，冲突更少　　Tips：散列函数的设计要结合实际的关键字分布特点来考虑，不要教条化　　2、直接定址法：H(key) = key 或 H(key) = a*key+b 　　其中，a 和 b 是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。　　例：存储同一个班级的学生信息，班内学生学号为(~) 　　H(key) = key –

　　3、数字分析法　　选取数码分布较为均匀的若干位作为散列地址　　设关键字是 r 进制数（如十进制数），而 r 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

　　4、平方取中法　　取关键字的平方值的中间几位作为散列地址。　　具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

　　5.5 开放定址法处理冲突（这部分我不能理解为什么要这么做，或者是应用场景）　　1、思想　　开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：
%m 　　i = 0, 1, 2, …… (k ≤ m – 1)，m 表示散列表表长；di 为增量序列；i 可理解为“第 i 次发生冲突”

　　2、线性探测法　　(1) 线性探测法 di = 0, 1, 2, 3, … m-1; 即发生冲突时，每次往后探测相邻的下一个单是否为空

　　(2) 查找　　成功

　　失败1

　　

　　失败2

　　(3) 删除　　采用“开放定址法”时，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除（查找的时候到这一点不会停下来）　　会出现的情况

　　(4) 查找效率分析

　　线性探测法很容易造成同义词、非同义词的“聚集(堆积) ”现象，严重影响查找效率　　产生原因：冲突后再探测一定是放在某个连续的位置　　3、平方探测法　　(1) 存储　　发生冲突后存放的位置：d0 = 0、d1 = 1、d2 = -1、d3 = 4、d4 = -4、d5 = 9、d6 = -9 ……

　　平方探测法：比起线性探测法更不易产生“聚集（堆积）”问题　　(2) 查找　　查找顺序同上面存储的顺序，先查找 H(key) = key % 13，再查找 H(key) + d1，…… 　　注意：散列表长度 m 必须是一个可以表示成 4j + 3 的素数才能探测到所有位置

　　4、伪随机序列法　　di 是一个伪随机序列，如di = 0, 5, 24, 11, … 　　5.6 再散列法处理冲突　　再散列法（再哈希法）：除了原始的散列函数 H(key) 之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止　　5.7 总结　　

　　参考文献：　　【1】视频：王道计算机考研数据结构

排序二叉树的平均查找长度_设二叉排序树中有n个节点

相关推荐