8.5 算法总结
查找是一种使用最频繁的基本操作,无论是编译中的符号表,还是数据库系统的信息检索，都涉及查找操作。因此,查找操作的实现效率十分重要,衡量查找效率的主要性能指标就是平均查找长度(ASL)。本章介绍了三种类型的查找表。
(1)基于线性的查找表
主要分顺序查找、折半查找以及索引查找。
顺序查找对查找表没有特别要求,但是查找效率不高,几乎是表长的一半。现在有很多技术可以改进这种查找方法
折半查找要求查找表必须采用顺序结构而且按照关键字有序排列。整个折半查找过程借助于折半判定树加以描述,判定树中每一个结点对应表中一个记录的位置序号。它的查找速度快， 平均性能较好,但是插人和删除操作较困难。它在等概率的情况下,查找成功的平均查找长度与 折半判定树的深度相关:
ASL≈log2(n+1)-122(n+1)-1
索引查找是一种性能介于顺序查找和折半查找之间的查找办法,平均查找长度等于两个阶 段各自查找的长度之和。它有较快的查找速度,又可以动态更新变化。在插入或删除一个结点时,找到该结点所属的块,然后在块内进行插人和删除运算。由于块内结点的存放是任意的,因此插人或删除比较容易,不需要移动大量的结点。插人可直接在块尾进行,如果待删的记录不是块中最后一个记录,可以将本块内最后一个记录移入被删记录的位置。
(2)基于树形的查找表
针对大型数据库的数据查找工作,要求支持高效的动态查找能力。由于数据库中包含了大量的记录,前面讲到的基于线性表的查找本身会因为记录太大而无法存储到主存中。另外,对于 记录的插人和删除操作来说,都需要移动大量的元素。事实上,对于大型数据库的组织结构一般都采用树形结构的查找表:
①二叉排序树。
基于二叉排序树的查找过程与折半查找过程类似,在二叉排序树中查找一 个记录的比较次数不超过树的深度,平均查找长度仍然是O(log2n)。但是它的插入、删除操作 无须移动大量结点,经常需要变化的动态表宜采用二叉排序树结构。
②平衡二叉树。由于二叉排序树在建立时受输人序列影响,有可能退化为最差的查找情 况,这也可能是由于在树中插人或删除结点而造成的。平衡一又树不受输人序列或插入结点等 的影响,始终保持平衡状态,从而达到很好的检索效率。它的查找、插入和删除效率都是O(log2n)，而且都是从根到叶子结点单路径进行的局部运算
③伸展树。伸展树的吸引力在于查找和更新方法的简洁性。它是一种自调整形式的二叉查找树,每次查找、插入或删除之后,通过仔细设计旋转序列,将被访问的结占向上移动到根。这 钟简单“移动到顶”的启发式策略有利于所进行的各种操作。它会沿着从某个结占到树根之间 的路径,通过一系列旋转把这个结点搬移到树根去。事实上,伸展树只是改进了一叉排序树性能的一组规则,可以在O(log2n)内完成插入、查找和删除等操作,控制了查找、插人和删除等操作 对排序树的修改,从而避免二叉排序树在最差情况下的线性时间代价。
④红黑树。红黑树是一种自平衡二叉查找树,它的操作有着良好的最坏情况运行时间,并 且在实践中是高效的,它可以在0(log,n)时间进行查找、插人和删除等操作。其中每个结点被 “染成”红色或黑色。它利用对树中结点红黑着色的要求达到局部平衡。
(3)散列
散列方法是一种计算式查找方法,其核心就是由哈希函数决定关键字值与散列地址之间的 对应关系,通过这种关系来组织存储并进行查找等操作。该方法面临的主要问题是哈希函数的 选取以及处理冲突的方法。而影响整个哈希查找的主要因素就是哈希函数、处理冲突的方法以 及哈希表的装填因子。如果假设哈希函数是均匀的,并且按处理冲突的方法分别考虑,则影响平均查找长度的因素就只有装填因子了。
总之,查找技术很多,具体采用哪一种应根据实际的应用环境和需求进行选取。
习题8
1 单项选择题 1~5 8 9
(1)在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与B数量级相当
A.顺序查找
B.折半查找
C.分块查找
D.哈希香找
(2)分别以下列序列构造二叉排序树,与用其他三个序列所构造的结果不同的是C
A.(100,80,90,60,120,110,130)
B.(100,120,110,130,80.60,90)
C.(100,60,80,90,120,110,130)
D.(100,80,60,90,120,130,110)
(3)顺序查找适合于存储结构为D的线性表。
A.散列存储
B.压缩存储
C.索引存储
D.顺序或链式存储
(4)如果要求用线性表既能较快地查找,又能适应动态变化的要求,则可采用A查找方法
A.分块查找
B.顺序查找
C.折半查找
D.基于属性
(5)已知一个有如下10个记录的表，其关键字序列为（2，15，19，25，30,34,44，55
，58,80）用折半查找关键字为55的记录,比较次数是B
A.1次
B.2次
C.3次
D.4次
(8)哈希表的地址区间为0~17,哈希函数为H(K)=K MOD 17。采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到哈希表中,则元素59存放在哈希表中的地址为D
A.8
B.9
C.10
D.11
(9)设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79}用链地址法构造
散列表。散列函数为H(key)=key MOD 13,散列地址为1的链中有D个记录。
A.1
B.2
C.3
D.4
3 完成题 1~4
(1)已知一个有7个数据元素的有序顺序表,其关键字为13,18,25,37,69,87,
38，99},请给出用折半查找方法查找关键字值18的查找过程。
(2)已知关键字序列为{53,17,19,61,98,75,79,63,46,40,请给出利用这些关键字构造的二叉排序树。
(3)根据如图8-62所示的二叉排序树,给出刚联老键字88后的二叉排序树。
(4)已知一组关键字序列为{5，88,12,56,79,28，33，43，93，17}，哈希表长为13,哈希函数为H(key)=key%13,请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表,并计算查找成功时的平均查找长度。
4 算法设计题 6
（6）编写算法,输出给定二叉排序树中数据域值最大的结点。
略
