二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(5)

分块查找 blocking search 又称作索引顺序查找。它是一种性能介于顺序查找和折半查找之间的查找方法。分块查找的基本方法是：1. 建立结构。⑴ 分块分块查找要求把线性表均匀地分成若干块，在每一块中结点是任意存放的，但块与块之间必须是有序的。假设这种有序是按关键字值非递减的，也就是说在第一块中的任一结点的关键字都小于第二块中所有结点的关键字；第二块中的任一结点的关键字都小于第三块中所有结点的关键字；以此类推。即对于线性表中任意两个关键字keyi, keyj, 若keyi∈Bi, keyj∈Bj且i j, 则必有keyi keyj 。其中Bi 和Bj表示第i块与第j块。⑵ 建立辅助表 索引表建立一个最大 最小 关键字表，即把块中最大 最小 的关键字值依次填入索引表中，并通过指针指向本块首址。二叉排序树的建立例9.3 设一个线性表中有15个结点，现将其分成三块，每块5个结点，各块采用顺序存储，分别存放在三个连续的内存空间中，索引表也用一个向量来表示，它含有三个表目，每个表目包括两个字段，一个是对应块中的最大关键字，一个是指向该块首址的指针 如图9-4所示 。2. 查找假设要查找关键字与K相等的结点，则查找时先将K和索引表的最大 最小 关键字比较，确定它在哪一块中，然后再到此块中进行检索。

因为索引表是有序表，因此确定块的查找既可以顺序查找，也可以折半查找；而块中的结点是任意存放的，在块中的查找只能是顺序查找。假设要查找关键字等于23的结点，先在索引表中进行查找，因为23 19且23 51，所以，若表中有此结点的话，必在表的第二块中，因此，第二块中进行顺序查找，查得此块的第三个结点。这是查找成功的情况。现假设要找表中关键字等于100的结点，先在索引表中进行查找，因为100 19, 所以不会在第一块中，又由于100 51，所以也不会在第二块中，最后K与索引表的最后一项比较：100 97, 说明也不会存在于第三块中，这时以查找失败而告终。清楚了分块查找的存储结构和查找方法，不难写出分块查找的算法。这里仅就分块查找的时间性能进行分析。从前面已经看到，分块查找过程是分两步进行的，第一步是确定结点所在块，第二步是在块内查找。假设线性表共有n个结点，平均分成b块，每块s个结点 s×b n ，并假设查找每个结点的概率相等。则每块被查找的概率为1/b，块中每个结点被查找的概率为1/s。若采用顺序查找的方法来查找索引表以确定结点所在的块，并只考虑查找成功的情况，则有ASLn ASLb + ASLs 可见，分块查找的平均查找长度不仅和表的长度n有关，而且和每块中的结点个数s有关，在给定n的前提下，s是可以选择的。

容易推得，当 时，分块查找的平均查找长度为最小，即ASLn取最小值：ASLn 上式实际上也给出了采用分块查找方法时对全部结点如何进行分块的原则。例如，如果要查找的线性表中有10000个结点，应把它分成100块，则分块查找平均需要100次比较，而顺序查找平均需要5000次比较，折半查找则最多需要14次比较。由此可见，分块查找的速度比顺序查找要快得多，但不如折半查找。如果线性表中结点个数很多，且被分成的块数b很大时，对索引表的查找可以采用折半查找，还能进一步提高查找速度。为便于插入、删除运算，分块时，块中的结点未必为满额，可以预留出一些未用的结点空间，但要使每块的长度相等。分块查找的优点是：在表中插入或删除一个结点时，只要找到该结点应属于的块，然后在块内进行插和删除运算。由于块内结点的存放是任意的，所以插入或删除比较容易，不需要移动大量的结点。其缺点是：① 分块查找的主要代价是增加了一个辅助数组 索引表 的存贮空间和初始线性表分块排序的运算。② 当大量的插入、删除运算使块中结点数分布不均匀时，分块查找的速度将会有所下降。9.3 树形表的查找从上一节的讨论中我们已经看到，用线性表这种数据结构来作为查找表，属于静态查找结构，在三种查找方法中，折半查找效率最高。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-5.html