優化調整次優查找樹的探討

宋景平

(揚州職業大學，江蘇揚州 225009)

查找是計算機軟件設計的一種重要操作，簡單比對查找常常會占有整個軟件設計工作的25%。如何查找才能使得查找的總次數更少一直是軟件設計人員孜孜以求的。查找分為查找成功(數據表中存在這個關鍵字等于給定值的記錄)［1］和查找不成功(數據表中不存在這個關鍵字等于給定值的記錄)［2］。對于大部分查找一般采用哈希(Hash)散列方法，能夠有效地降低查找總次數。而等概率的有序表采用折半查找［3］，查找性能最優。如果對于查找非等概率的有序表采用折半查找，其查找性能未必最好。查找成功的判定樹是帶權路徑之和PH值

其中:n為二叉樹上的結點個數;Wi為(i=1，2，…，n)結點的權;Di為(i=1，2，…，n)第 i個結點在二叉樹上的層次數。

由于構造靜態最優查找樹需要花費相當高的時間代價。計算機資源就是時間和空間，耗費過多的時間用于構造靜態最優查找樹，不符合軟件設計減少軟件運行時間和節省軟件占用空間的理念。故轉而構造時間代價較少的次優查找樹［4］。次優查找樹查找性能只比最優查找樹差1%～2%，很少差3%以上。

1 次優查找樹概念

次優查找樹，它或者是一棵空樹，或者是具有下列性質的二叉樹:

(1)若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值;

(2)若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值;

(3)它的左、右子樹也分別為二叉排序樹。

次優查找樹的查找過程類似折半查找，首先將給定值KEY與根結點關鍵字相比，若相等，則查找成功，該結點的記錄即為所求;否則根據給定值KEY小于或大于根結點關鍵字而分別在左子樹或右子樹繼續查找直至查找成功或查找不成功為止。這種查找比較的關鍵字個數不超過樹的高度。構造次優查找樹的方法如下:

已知一個按關鍵字有序的記錄序列

其中 RL.key＜RL+1.key＜ … ＜RH.key與每個記錄相對應的權值為

具體方法:首先在式(1)所示的記錄序列中取第i(l≤i≤h)個記錄構造根記錄使得

然后分別對子序列{RL，RL+1，…，Ri－1} 和{Ri+1，Ri+2，…，RH}構造兩棵次優查找樹，并且分別設為的左子樹和右子樹。

2 優化實例和計算

2.1 僅考慮查找成功的次優查找樹

例1:已知含有7個關鍵字的有序表及其相應權值表(見表1)，關鍵字ASCII碼:C＜F＜I＜L＜P＜S＜W，為一非等概率有序表。按照式(3)的方法構造次優查找樹。

表1 含有7個關鍵字的有序表及其相應權值表

按照式(3)的方法構造得到如圖1經典次優查找樹，查找成功的總次數PHS1=(3)×1+(4+5)×2+(24+40+21+36)×3=384。

人工優化處理后得如圖2優化調整次優查找樹，查找成功的總次數PHS2=(40)×1+(24+36)×2+(4+21)×3+(3+5)×4=267。

圖1 經典次優查找數

圖2 優化調整的次優查找樹

兩種次優查找樹的總查找次數PHS1=384和PHS2=267可以相差很大。優化調整后次優查找樹優越性明顯。我們當然選擇更少的(次優查找樹)，但是不能選擇最少的(靜態最優查找樹)，花費時間代價太大。

這種次優查找樹的人工調整應遵循兩個原則:

(1)最先訪問的結點應是訪問概率較大的靠近中央的結點;

(2)每次訪問應使結點兩邊尚未訪問的結點的被訪概率之差盡可能相等。

如果結點個數較少，可以憑經驗而為之;如果結點個數較多，則需要采用類似構造Huffman樹的理念進行構造這棵次優查找樹。即權重的結點盡量靠近樹根，仍然保持有序表。

2.2 考慮查找成功和查找不成功次優查找樹

考慮等概率查找不成功，如圖3經典等概率查找不成功(^表示查找不成功)所示。查找不成功的總次數為

考慮等概率查找不成功，如圖4調整后等概率查找不成功所示。

PHL3=32和PHL4=34相差不大?？紤]非等概率查找不成功，則如圖5非等概率查找不成功經典次優查找樹、圖6非等概率查找不成功優化調整次優查找樹所示。

圖3 經典等概率查找不成功次優查找樹

圖4 優化調整后等概率查找不成功的次優查找樹

例2 已知含有7個關鍵字的有序表(表1)和8個區間查找不成功的表(表2)，區間ASCII碼:″＜C″＜″C—F″＜″F—I″＜″I—L″＜″L—P″＜″P—S″＜″S—W″＜″S—W″＜″＞W″并且它們的查找概率不相等。以7個關鍵字構造次優查找樹。

表2 8個查找不成功的區間相應權值表

把查找成功關鍵字權值累加 WS=24+4+40+3+21+5+36=133，把查找不成功關鍵字權值累加WL=15+20+12+9+11+8+10+30=115，則總查找權值W=WS+WL=248。

非等概率查找不成功的總次數的計算就是用權值乘以次優查找樹的對應層次的累加和。

計算圖5的平均查找長度ASL5:

計算圖6的平均查找長度ASL6:

看到ASL6小于ASL5。優化調整次優查找樹效果非常明顯。

圖5 非等概率查找不成功經典次優查找樹

圖6 非等概率查找不成功調整后次優查找樹

3 結論

對于查找成功概率不等的有序表和對于查找不成功概率不等的有序表使用次優查找樹能夠最大節省總的查找次數。靈活地采用構造類似Huffman樹的理念進行優化調整次優查找樹可以降低查找總次數，科學地計算平均查找長度ASL。

［1］黃劉生.數據結構［M］.合肥:經濟科學出版社，1999.

［2］李春葆.數據結構教程［M］.2版.北京:清華大學出版社，2007.

［3］陳小平.數據結構［M］.南京:南京大學出版社，1997.

［4］嚴蔚敏，吳偉民.數據結構:C語言版［M］.北京:清華大學出版社，2007.