靜態(tài)最優(yōu)查找樹
當(dāng)有序表中每個(gè)記錄的查詢概率相同時(shí)，用折半查找性能最優(yōu)蜒谤。當(dāng)有序表的查找概率不等時(shí)山宾，折半查找的概率未必最優(yōu)。
若只考慮查找成功的情況鳍徽，則使查找性能最優(yōu)的判定樹其帶權(quán)路徑長(zhǎng)度之和為PH值。
PH=∑wihi
hi為第i個(gè)結(jié)點(diǎn)在二叉樹上的層次數(shù);結(jié)點(diǎn)的權(quán)wi=c*pi敢课，pi為第i個(gè)結(jié)點(diǎn)的查找概率阶祭，c為某個(gè)常量。
稱PH值最小的二叉判定樹為靜態(tài)最優(yōu)查找樹(Static Optimal Search Tree).
次優(yōu)查找樹(Nearly Optimal Search Tree)
構(gòu)造次優(yōu)查找樹的方法：首先在記錄序列中取第i個(gè)記錄構(gòu)造根結(jié)點(diǎn)直秆，使得左部分序列的累計(jì)權(quán)值和與右部分序列的累計(jì)權(quán)值和差的絕對(duì)值最小;再對(duì)左右子序列分別構(gòu)造次優(yōu)查找樹濒募。
void SecondOptimal(BiTree &T,ElemType R[],float sw[],int low,high){
i=low;
min=abs(sw[high]-sw[low]);
dw=sw[high]+sw[low-1];
for(j=low+1;j<=high;++j){
i=j;min=abs(dw-sw[j]-sw[j-1]);
}//for
T=(BiTree)malloc(sizeof(BiNode));
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);
}//SecondOptimal
