優(yōu)化調(diào)整次優(yōu)查找樹(shù)的探討

宋景平

(揚(yáng)州職業(yè)大學(xué)，江蘇揚(yáng)州 225009)

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

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

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

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

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

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

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

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

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

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

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

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

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

2 優(yōu)化實(shí)例和計(jì)算

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

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

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

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

人工優(yōu)化處理后得如圖2優(yōu)化調(diào)整次優(yōu)查找樹(shù)，查找成功的總次數(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)查找樹(shù)

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

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

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

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

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

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

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

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

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

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

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

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

表2 8個(gè)查找不成功的區(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ù)的計(jì)算就是用權(quán)值乘以次優(yōu)查找樹(shù)的對(duì)應(yīng)層次的累加和。

計(jì)算圖5的平均查找長(zhǎng)度ASL5:

計(jì)算圖6的平均查找長(zhǎng)度ASL6:

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

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

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

3 結(jié)論

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

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

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

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

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