一、静态树表的查找
对有序表的查找，如使用折半查找方法，是在“等概率”的前提下进行的，如果查找概率不一样，折半查找就不是最佳方法了。
举例：假设有序表有5条记录，且各记录的查找概率不等，分别为p1 = 0.1，p2 = 0.2，p3= 0.1，p4 = 0.4，p5 = 0.2，，则对此有序表进行折半查找，查找成功时的平均查找长度为
image.png
但是，如果在查找是令给定值先和第4个记录（这条记录查找概率高）进行比较，比较不相等时在继续在左子序列或右子序列中进行折半查找，则查找成功时的平均查找长度为
image.png
由此说明，对于每个元素被查找的概率不同的情况下，折半查找不是最佳方法。
如果把权值越大的结点放到越靠近根结点的位置，缩短查找概率高的结点的查找路径，进而提高查找效率，但是构造这种最优查找树，时间复杂度非常高O(n3)。因此采用构造次优查找树的方法进行查找，这种树的查找效率很少低于最优查找树的3%，且构造次优查找树的算法的时间复杂度为O(nlogn)。
构造的核心时间就是，选出一个结点，使得它左右两侧的子数组的权值累加和之差的绝对值最小。把这个结点当做根节点，递归地用刚才的左右字数组构造它的左右子树。
算法：
void SecondOptional(BiTree &T,Elemtype R[],float sw[],int low,int high)
{
/** 由有序表R[low..high]及其累计权值表sw(其中sw[0]=0)递归构造次优查找树T */
i = low; min = abs(sw[high]-sw[low]) ; dw = sw[high]+sw[low-1];
for(j = low+1 ; j <= high ; j ++) {
if(abs(dw-sw[j]-sw[j-1]) < min) {
i = j;
min = abs(dw-sw[j]-sw[j-1]);
}
}
T = (BiTree)malloc(sizeof(BiTNode));
T -> data = R[i];//生成结点
if(i == low) T->lchild = NULL;//左子树空
else SecondOptimal(T->lchild,R,sw,low,i-1);//构造左子树
if(i == high) T->rchild = NULL;//右子树空
else SecondOptimal(T->rchild,R,sw,i+1,high);//构造右子树
}
举例：
image.png
wi为第i个关键字的权值，swl为从0到i个关键字之间的权值之和，
设wl-1= 0，swl-1 = 0
image.png
按照上面的算法，得到的构造次优查找树的过程如下：
image.png
构造所得次优二叉查找树如下图所示：
image.png
从次优查找树的结构特点可见，其查找过程类似于折半查找，若次优查找树为空，则查找失败，否则，先将给定值K和其根节点相比，若不相等，则根据给定值K大于或小于根节点的情况分别在左子树或右子树中继续查找，直至成功或不成功为止。由于查找过程恰走了一条从根到待查记录所在结点的一条路径，进行比较的关键字个数不超过树的深度，因此，次优查找树的平均查找长度和logn成正比。
二、索引顺序表的查找
分块查找又称索引顺序查找，这是顺序查找的一种改进方法，在此查找法中，除表本身外，还要建立一个“索引表”，如下图
image.png
表中含有18个记录，分成三个子表（R1, R2, ... R6）（R7, R8, ... R12）（R13, R14, ... R18），对每个子表建立一个索引项，索引项包括两项内容：关键字项（其值为该子表内的最大关键字）和项指针（指示该子表的第一个记录在表中的位置）。索引表按关键字有序，则表或者有序，或者分块有序（分块有序：第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，以此类推）。
因此，分块查找过程分两步：
1、确定待查记录所在块。2、在块中顺序查找
举例：
给定值K = 38，先将K依次和索引表中最大关键字进行比较，因为22 < K < 48，则关键字为38的记录若存在，必在第二个子表中，第二个子表的索引项的项指针，指向第二个子表的第一个记录是表中的第7个记录，所以从第7个记录开始进行顺序查找，直到查到r[10].key = K为止，若K = 29，从第7个记录查到第12个记录都没有比较成功，则查找失败。
由于由索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，也可以用折半查找，若块中的记录是任意排列的，则只能用顺序查找了。
分块查找的平均查找长度为：查找索引表的平均查找长度 + 在块中查找元素的平均查找长度。
网友评论