宋景平

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

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

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

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

1 次優(yōu)查找樹概念

次優(yōu)查找樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹:

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

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

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

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

已知一個按關(guān)鍵字有序的記錄序列

其中 RL.key＜RL+1.key＜ … ＜RH.key與每個記錄相對應(yīng)的權(quán)值為

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

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

2 優(yōu)化實例和計算

2.1 僅考慮查找成功的次優(yōu)查找樹

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

表1 含有7個關(guān)鍵字的有序表及其相應(yīng)權(quán)值表

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

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

圖1 經(jīng)典次優(yōu)查找數(shù)

圖2 優(yōu)化調(diào)整的次優(yōu)查找樹

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

這種次優(yōu)查找樹的人工調(diào)整應(yīng)遵循兩個原則:

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

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

如果結(jié)點個數(shù)較少，可以憑經(jīng)驗而為之;如果結(jié)點個數(shù)較多，則需要采用類似構(gòu)造Huffman樹的理念進行構(gòu)造這棵次優(yōu)查找樹。即權(quán)重的結(jié)點盡量靠近樹根，仍然保持有序表。

2.2 考慮查找成功和查找不成功次優(yōu)查找樹

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

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

PHL3=32和PHL4=34相差不大?？紤]非等概率查找不成功，則如圖5非等概率查找不成功經(jīng)典次優(yōu)查找樹、圖6非等概率查找不成功優(yōu)化調(diào)整次優(yōu)查找樹所示。

圖3 經(jīng)典等概率查找不成功次優(yōu)查找樹

圖4 優(yōu)化調(diào)整后等概率查找不成功的次優(yōu)查找樹

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

表2 8個查找不成功的區(qū)間相應(yīng)權(quán)值表

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

非等概率查找不成功的總次數(shù)的計算就是用權(quán)值乘以次優(yōu)查找樹的對應(yīng)層次的累加和。

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

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

看到ASL6小于ASL5。優(yōu)化調(diào)整次優(yōu)查找樹效果非常明顯。

圖5 非等概率查找不成功經(jīng)典次優(yōu)查找樹

圖6 非等概率查找不成功調(diào)整后次優(yōu)查找樹

3 結(jié)論

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

［1］黃劉生.數(shù)據(jù)結(jié)構(gòu)［M］.合肥:經(jīng)濟科學出版社，1999.

［2］李春葆.數(shù)據(jù)結(jié)構(gòu)教程［M］.2版.北京:清華大學出版社，2007.

［3］陳小平.數(shù)據(jù)結(jié)構(gòu)［M］.南京:南京大學出版社，1997.

［4］嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu):C語言版［M］.北京:清華大學出版社，2007.