最優(yōu)二叉樹算法

在實際應(yīng)用中，常常要考慮一個問題:如何設(shè)計一棵二叉樹，使得執(zhí)行路徑最短，即算法的效率最高。

例1.快遞包裹的郵資問題

假設(shè)郵政局的包裹自動測試系統(tǒng)能夠測出包裹的重量，如何設(shè)計一棵二叉樹將包裹根據(jù)重量及運距進(jìn)行分類從而確定郵資。

國內(nèi)快遞包裹資費 單位:元

(2004年1月1日起執(zhí)行)

表1 國家郵政局制定的快遞包裹參考標(biāo)準(zhǔn)

根據(jù)表1可以制定出許多種二叉樹，但不同的二叉樹判定的次數(shù)可能不一樣，執(zhí)行的效率也不同。

鐵球分類

現(xiàn)有一批球磨機(jī)上的鐵球，需要將它分成四類:直徑不大于20的屬于第一類;直徑大于20而不大于50的屬于第二類;直徑大于50而不大于100的屬于第三類;其余的屬于第四類;假定這批球中屬于第一、二、三、四類鐵球的個數(shù)之比例是1:2:3:4。

我們可以把這個判斷過程表示為 圖1中的兩種方法:

最優(yōu)二叉樹算法

兩種判斷二叉樹示意圖

那么究竟將這個判斷過程表示成哪一個判斷框，才能使其執(zhí)行時間最短呢?讓我們對上述判斷框做一具體的分析。

假設(shè)有1000個鐵球，則各類鐵球的個數(shù)分別為:100、200、300、400;

對于圖7.1中的上圖和下圖比較的次數(shù)分別如表所示:

左圖 和下圖

表2 兩種判斷二叉樹比較次數(shù)

過上述分析可知，圖1中右圖所示的判斷框的比較次數(shù)遠(yuǎn)遠(yuǎn)小于左圖所示的判斷框的比較次數(shù)。為了找出比較次數(shù)最少的判斷框，將涉及到樹的路徑長度問題。

最優(yōu)二叉樹，也稱哈夫曼(Haffman)樹，是指對于一組帶有確定權(quán)值的葉結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。

那么什么是二叉樹的帶權(quán)路徑長度呢?

在前面我們介紹過路徑和結(jié)點的路徑長度的概念，而二叉樹的路徑長度則是指由根結(jié)點到所有葉結(jié)點的路徑長度之和。如果二叉樹中的葉結(jié)點都具有一定的權(quán)值，則可將這一概念加以推廣。設(shè)二叉樹具有n個帶權(quán)值的葉結(jié)點，那么從根結(jié)點到各個葉結(jié)點的路徑長度與相應(yīng)結(jié)點權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度，記為:

WPL= Wk·Lk

其中Wk為第k個葉結(jié)點的權(quán)值，Lk 為第k個葉結(jié)點的路徑長度。如圖7.2所示的二叉樹，它的帶權(quán)路徑長度值WPL=2×2+4×2+5×2+3×2=28。

在給定一組具有確定權(quán)值的葉結(jié)點，可以構(gòu)造出不同的帶權(quán)二叉樹。例如，給出4個葉結(jié)點，設(shè)其權(quán)值分別為1，3，5，7，我們可以構(gòu)造出形狀不同的多個二叉樹。這些形狀不同的二叉樹的帶權(quán)路徑長度將各不相同。圖7.3給出了其中5個不同形狀的二叉樹。

這五棵樹的帶權(quán)路徑長度分別為:

(a)WPL=1×2+3×2+5×2+7×2=32

(b)WPL=1×3+3×3+5×2+7×1=29

(c)WPL=1×2+3×3+5×3+7×1=33

(d)WPL=7×3+5×3+3×2+1×1=43

(e)WPL=7×1+5×2+3×3+1×3=29

最優(yōu)二叉樹算法

最優(yōu)二叉樹算法

由此可見，由相同權(quán)值的一組葉子結(jié)點所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長度，那么如何找到帶權(quán)路徑長度最小的二叉樹(即哈夫曼樹)呢?根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉結(jié)點越遠(yuǎn)離根結(jié)點。

哈夫曼(Haffman)依據(jù)這一特點于1952年提出了一種方法，這種方法的基本思想是:

(1)由給定的n個權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個葉結(jié)點的二叉樹，從而得到一個二叉樹的集合F={T1，T2，…，Tn};

(2)在F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點權(quán)值之和;

(3)在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中;

(4)重復(fù)(2)(3)兩步，當(dāng)F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。

在本章的引入部分，兩個例子都是判定問題，這兩個判定問題都可以通過構(gòu)造哈夫曼樹來優(yōu)化判定，以達(dá)到總的判定次數(shù)最少。

再如，要編制一個將百分制轉(zhuǎn)換為五級分制的程序。顯然，此程序很簡單，只要利用條件語句便可完成。

程序段

if a<60 then b:='bad'

else if a<70 then b:='pass'

else if a<80 then b:='general'

else if a<90 then b:='good'

else b:='excellent';

如果上述程序需反復(fù)使用，而且每次的輸入量很大，則應(yīng)考慮上述程序的質(zhì)量問題，即其操作所需要的時間。因為在實際中，學(xué)生的成績在五個等級上的分布是不均勻的，假設(shè)其分布規(guī)律如表4所示:

表4 分?jǐn)?shù)段的分布頻率

則80%以上的數(shù)據(jù)需進(jìn)行三次或三次以上的比較才能得出結(jié)果。假定以5，15，40，30和10為權(quán)構(gòu)造一棵有五個葉子結(jié)點的哈夫曼樹，它可使大部分的數(shù)據(jù)經(jīng)過較少的比較次數(shù)得出結(jié)果。但由于每個判定框都有兩次比較，將這兩次比較分開，得到新的判定樹，按此判定樹可寫出相應(yīng)的程序。請您自己畫出此判定樹。

假設(shè)有10000個輸入數(shù)據(jù)，若上程序段的判定過程進(jìn)行操作，則總共需進(jìn)行31500次比較;而若新判定樹的判定過程進(jìn)行操作，則總共僅需進(jìn)行22000次比較。

如果一棵具有n個結(jié)點的深度為k的二叉樹，它的每一個結(jié)點都與深度為k的滿二叉樹中編號為1~n的結(jié)點一一對應(yīng)，這棵二叉樹稱為完全二叉樹。

可以根據(jù)公式進(jìn)行推導(dǎo)，假設(shè)n0是度為0的結(jié)點總數(shù)(即葉子結(jié)點數(shù))，n1是度為1的結(jié)點總數(shù)，n2是度為2的結(jié)點總數(shù)，則 ①n= n0+n1+n2 (其中n為完全二叉樹的結(jié)點總數(shù));又因為一個度為2的結(jié)點會有2個子結(jié)點，一個度為1的結(jié)點會有1個子結(jié)點，除根結(jié)點外其他結(jié)點都有父結(jié)點，所以②n= 1+n1+2*n2 ;由①、②兩式把n2消去得:n= 2*n0+n1-1，由于完全二叉樹中度為1的結(jié)點數(shù)只有兩種可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

簡便來算，就是 n0=n/2，其中n為奇數(shù)時(n1=0)向上取整;n為偶數(shù)時(n1=1)?？筛鶕?jù)完全二叉樹的結(jié)點總數(shù)計算出葉子結(jié)點數(shù)。

由于網(wǎng)絡(luò)所有可能的劃分?jǐn)?shù)量是巨大的，假設(shè)網(wǎng)絡(luò)的結(jié)點數(shù)和邊數(shù)分別為n和m，則所有可能的社區(qū)劃分?jǐn)?shù)是一個以n為指數(shù)的數(shù)。因此，在所有可能的劃分中找出最優(yōu)劃分是一個NP-hard問題。針對這一問題，目前一些相應(yīng)算法已被提出，其可以在合理的時間內(nèi)找出模塊度最大化的近似最優(yōu)劃分。

模塊度最大化問題是一個經(jīng)典的最優(yōu)化問題，Mark NewMan 基于貪心思想提出了模塊度最大化的貪心算法FN 。貪心思想的目標(biāo)是找出目標(biāo)函數(shù)的整體最優(yōu)值或者近似最優(yōu)值，它將整體最優(yōu)化問題分解為局部最優(yōu)化問題，找出每個局部最優(yōu)值，最終將局部最優(yōu)值整合成整體的近似最優(yōu)值。FN算法將模塊度最優(yōu)化問題分解為模塊度局部最優(yōu)化問題，初始時，算法將網(wǎng)絡(luò)中的每個結(jié)點都看成獨立的小社區(qū)。然后，考慮所有相連社區(qū)兩兩合并的情況，計算每種合并帶來的模塊度的增量?；谪澬脑瓌t，選取使模塊度增長最大或者減小最少的兩個社區(qū)，將它們合并成一個社區(qū)。如此循環(huán)迭代，直到所有結(jié)點合并成一個社區(qū)。隨著迭代的進(jìn)行，網(wǎng)絡(luò)總的模塊度是不斷變化的，在模塊度的整個變化過程中，其最大值對應(yīng)網(wǎng)絡(luò)的社區(qū)劃分即為近似的最優(yōu)社區(qū)劃分。

貪心算法FN具體步驟:

該算法中，需要注意的是，每次加入的邊只是影響網(wǎng)絡(luò)的社區(qū)劃分，而每次計算網(wǎng)絡(luò)劃分的模塊度時，都是在網(wǎng)絡(luò)完整的拓?fù)浣Y(jié)構(gòu)上進(jìn)行，即網(wǎng)絡(luò)所有的邊都存在的拓?fù)浣Y(jié)構(gòu)上。

為了降低算法的時間復(fù)雜度，Vincent Blondel等人提出了另一種層次貪心算法 。該算法包括兩個階段，第一階段合并社區(qū)，算法將每個結(jié)點當(dāng)作一個社區(qū)，基于模塊度增量最大化標(biāo)準(zhǔn)決定你哪些鄰居社區(qū)應(yīng)該被合并。經(jīng)過一輪掃描后開始第二階段，算法將第一階段發(fā)現(xiàn)的所有社區(qū)重新看成結(jié)點，構(gòu)建新的網(wǎng)絡(luò)，在新網(wǎng)絡(luò)上重復(fù)進(jìn)行第一階段，這兩個階段重復(fù)運行，直到網(wǎng)絡(luò)社區(qū)劃分的模塊度不再增長，得到網(wǎng)絡(luò)的社區(qū)近似最優(yōu)劃分。

這個簡單算法具有一下幾個優(yōu)點:首先，算法的步驟比較直觀并且易于實現(xiàn);其次，算法不需要提前設(shè)定網(wǎng)絡(luò)的社區(qū)數(shù)，并且該算法可以呈現(xiàn)網(wǎng)絡(luò)的完整的分層社區(qū)結(jié)構(gòu)，能夠發(fā)現(xiàn)在線社交網(wǎng)絡(luò)的分層的虛擬社區(qū)結(jié)構(gòu)，獲得不同分辨率的虛擬社區(qū);再次，計算機(jī)模擬實驗顯示，在稀疏網(wǎng)絡(luò)上，算法是時間復(fù)雜度是線性的，在合理的時間內(nèi)可以處理結(jié)點數(shù)超過10^9的網(wǎng)絡(luò)，因此十分適合在線社交網(wǎng)絡(luò)這樣超大規(guī)模的負(fù)責(zé)網(wǎng)絡(luò)中虛擬社區(qū)的發(fā)現(xiàn)。

是程序算法中的一種算法模式。

在二叉樹中出現(xiàn)空的子樹（包括樹葉）上增加空的樹葉，使其成為滿二叉樹的二叉樹稱之為擴(kuò)充二叉樹。