一蜈膨、靜態(tài)樹表的查找
對有序表的查找悼沿，如使用折半查找方法等舔，是在“等概率”的前提下進(jìn)行的，如果查找概率不一樣糟趾，折半查找就不是最佳方法了慌植。
舉例：假設(shè)有序表有5條記錄，且各記錄的查找概率不等义郑，分別為p1 = 0.1蝶柿，p2 = 0.2，p3= 0.1非驮，p4 = 0.4交汤，p5 = 0.2，劫笙，則對此有序表進(jìn)行折半查找芙扎，查找成功時的平均查找長度為
但是，如果在查找是令給定值先和第4個記錄（這條記錄查找概率高）進(jìn)行比較填大，比較不相等時在繼續(xù)在左子序列或右子序列中進(jìn)行折半查找戒洼，則查找成功時的平均查找長度為
由此說明，對于每個元素被查找的概率不同的情況下栋盹，折半查找不是最佳方法施逾。
如果把權(quán)值越大的結(jié)點放到越靠近根結(jié)點的位置，縮短查找概率高的結(jié)點的查找路徑例获，進(jìn)而提高查找效率汉额，但是構(gòu)造這種最優(yōu)查找樹，時間復(fù)雜度非常高O(n3)榨汤。因此采用構(gòu)造次優(yōu)查找樹的方法進(jìn)行查找蠕搜，這種樹的查找效率很少低于最優(yōu)查找樹的3%，且構(gòu)造次優(yōu)查找樹的算法的時間復(fù)雜度為O(nlogn)收壕。
構(gòu)造的核心時間就是妓灌，選出一個結(jié)點轨蛤，使得它左右兩側(cè)的子數(shù)組的權(quán)值累加和之差的絕對值最小。把這個結(jié)點當(dāng)做根節(jié)點虫埂，遞歸地用剛才的左右字?jǐn)?shù)組構(gòu)造它的左右子樹祥山。
算法：
void SecondOptional(BiTree &T,Elemtype R[],float sw[],int low,int high)
{
/** 由有序表R[low..high]及其累計權(quán)值表sw(其中sw[0]=0)遞歸構(gòu)造次優(yōu)查找樹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];//生成結(jié)點
if(i == low) T->lchild = NULL;//左子樹空
else SecondOptimal(T->lchild,R,sw,low,i-1);//構(gòu)造左子樹
if(i == high) T->rchild = NULL;//右子樹空
else SecondOptimal(T->rchild,R,sw,i+1,high);//構(gòu)造右子樹
}
舉例：
wi為第i個關(guān)鍵字的權(quán)值，swl為從0到i個關(guān)鍵字之間的權(quán)值之和掉伏，
設(shè)wl-1= 0缝呕，swl-1 = 0
按照上面的算法，得到的構(gòu)造次優(yōu)查找樹的過程如下：
構(gòu)造所得次優(yōu)二叉查找樹如下圖所示：
從次優(yōu)查找樹的結(jié)構(gòu)特點可見斧散，其查找過程類似于折半查找供常，若次優(yōu)查找樹為空，則查找失敗鸡捐，否則栈暇，先將給定值K和其根節(jié)點相比，若不相等箍镜，則根據(jù)給定值K大于或小于根節(jié)點的情況分別在左子樹或右子樹中繼續(xù)查找源祈，直至成功或不成功為止。由于查找過程恰走了一條從根到待查記錄所在結(jié)點的一條路徑色迂，進(jìn)行比較的關(guān)鍵字個數(shù)不超過樹的深度新博，因此，次優(yōu)查找樹的平均查找長度和logn成正比脚草。
二、索引順序表的查找
分塊查找又稱索引順序查找原献，這是順序查找的一種改進(jìn)方法馏慨，在此查找法中，除表本身外姑隅，還要建立一個“索引表”写隶，如下圖
表中含有18個記錄，分成三個子表（R1, R2, ... R6）（R7, R8, ... R12）（R13, R14, ... R18）讲仰，對每個子表建立一個索引項慕趴，索引項包括兩項內(nèi)容：關(guān)鍵字項（其值為該子表內(nèi)的最大關(guān)鍵字）和項指針（指示該子表的第一個記錄在表中的位置）。索引表按關(guān)鍵字有序鄙陡，則表或者有序冕房，或者分塊有序（分塊有序：第二個子表中所有記錄的關(guān)鍵字均大于第一個子表中的最大關(guān)鍵字，第三個子表中的所有關(guān)鍵字均大于第二個子表中的最大關(guān)鍵字趁矾，以此類推）耙册。
因此，分塊查找過程分兩步：
1毫捣、確定待查記錄所在塊详拙。2帝际、在塊中順序查找
舉例：
給定值K = 38，先將K依次和索引表中最大關(guān)鍵字進(jìn)行比較饶辙，因為22 < K < 48蹲诀，則關(guān)鍵字為38的記錄若存在，必在第二個子表中弃揽，第二個子表的索引項的項指針脯爪，指向第二個子表的第一個記錄是表中的第7個記錄，所以從第7個記錄開始進(jìn)行順序查找蹋宦，直到查到r[10].key = K為止披粟，若K = 29，從第7個記錄查到第12個記錄都沒有比較成功冷冗，則查找失敗守屉。
由于由索引項組成的索引表按關(guān)鍵字有序，則確定塊的查找可以用順序查找蒿辙，也可以用折半查找拇泛，若塊中的記錄是任意排列的，則只能用順序查找了思灌。
分塊查找的平均查找長度為：查找索引表的平均查找長度 + 在塊中查找元素的平均查找長度俺叭。
