查找效率最高即平均查找長度最小，根據前面所學知識，我們可以給出有序表在非等機率情況下應遵循的兩個原則：
1、最先通路的結點應是通路機率最大的結點；
2、每次通路應使結點兩邊尚未通路的結點的被訪機率之和盡可能相等。
這兩個原則可用一句話來表示，即判定樹為帶權内路徑長度之和最小的二叉樹，亦即：PH = ∑wihi 最小，其中 n 為有序表長度，hi 為第 i 個結點在判定樹上的層次數，wi = cpi，c 為某個常數，pi 為第 i 個結點的查找機率。
這樣的樹稱為靜态最優查找樹（static optimal search tree），構造這樣一棵樹的時間代價太大，亦即時間複雜度很大，是以我們通常是構造次優查找樹（nearly optimal search tree），構造它的時間代價遠遠低于構造最優查找樹，但查找性能隻比最優查找樹差1%~2%，很少差3%以上。
次優查找樹的構造：
設有序表每個記錄的權值為 wl,wl+1,…,wh，第一個應通路的結點号為 i ，則有：
Δpi = ∑wj - ∑wj 最小，即 Δpi = Min {Δpj }
再分别對 {rl,rl+1,…,ri-1} 和 {ri+1,ri+2,…,rh} 分别構造次優查找樹。
為便于計算，引入累計權值swi=∑wj，并設wl-1=swl-1=0，則：
由于在構造次優查找樹時沒有考慮前面說的原則一，是以被選為根的結點的權值可能比其鄰近結點的權值小，此時應對查找樹作适當的調整，将相鄰權值大的結點作為根結點。
次優查找樹的查找方法與折半查找類似，其平均查找長度與 log n 成正比。
注意：利用上述算法構造好次優二叉樹之後，可能并不是最優的，因為在構造過程中，沒有考慮單個關鍵字的相應權值，則有可能出現被選為根的關鍵字的權值比與
它相鄰的關鍵字的權值小。此時應做适當的調整：選取鄰近的權值較大的關鍵字作為次優查找樹的根節點（也就是左旋和右旋子樹
9
A 1
B 1
C 2
D 5
E 3
F 4
G 4
H 3
I 5
沒有調整前的先序周遊:
F D B A C E G H I
調整後的先序周遊:
D C B A F E G I H
5
B 30
D 29
E 2
C B A D E
B A D C E
F
-------
| |
D G
-------------
| | |
B E H
-----------------
| | |
A C I
D
| |
C F
-----------
| | |
B E G
| |
A I
------------------
|
H