徐有為,張宏軍,程 愷,陳裕田,周彬彬

(陸軍工程大學(xué) 指揮控制工程學(xué)院,江蘇 南京 210000)

0 引言

二分查找又稱為折半查找[1]，是實(shí)現(xiàn)有序表查找的一個(gè)非常高效的算法。在對二分查找進(jìn)行時(shí)間復(fù)雜性分析和評價(jià)時(shí)，應(yīng)用判定樹這一工具可以使分析更加科學(xué)、形象、直觀。然而在結(jié)點(diǎn)總數(shù)發(fā)生變化的情況下，判定樹樹形也會(huì)相應(yīng)地發(fā)生改變。通過分析二分查找算法，本文旨在解決以下兩個(gè)問題：對于不同結(jié)點(diǎn)總數(shù)的判定樹樹形，其結(jié)構(gòu)特點(diǎn)是否具有一般性的規(guī)律？針對這一規(guī)律，將如何構(gòu)造判定樹，是否存在一個(gè)快速并且通用的構(gòu)造方法？

1 二分查找判定樹

二分查找是“基于計(jì)算中值地址的”，其原理[2]是：將數(shù)組中間位置記錄的數(shù)據(jù)與待查找數(shù)據(jù)K比較，若兩者相等，則查找成功，否則利用中間位置元素將數(shù)組分成前后兩個(gè)子數(shù)組，如果中間位置數(shù)據(jù)大于待查找數(shù)據(jù)，則進(jìn)一步查找前一子數(shù)組，否則進(jìn)一步查找后一子數(shù)組，重復(fù)以上過程，直到找到帶查找數(shù)據(jù)或者查找區(qū)間長度為0(即查找不成功)為止。

二分查找由于其高效的平均運(yùn)算性能，已經(jīng)廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、通信工程、電子科學(xué)等多個(gè)學(xué)科，其在中文信息處理、中文分詞方法[3]、路由查找算法[4]等多個(gè)領(lǐng)域的應(yīng)用均大大降低了傳統(tǒng)算法的時(shí)間復(fù)雜度,取得了滿意的結(jié)果。二分查找的折半思想也為多目標(biāo)線性規(guī)劃尋找近似解[5]、支持向量機(jī)分類[6]、最長前綴匹配算法[7]提供了非常高效的解決思路。

以判斷選擇為主要操作的算法，其流程可以表示成一棵樹，稱為算法的判定樹。判定樹由鐘鳴等人[8]首次使用，并逐漸廣泛應(yīng)用于算法效率分析中。二分查找判定樹是判定樹的一種典型應(yīng)用：把當(dāng)前查找區(qū)間中間位置的結(jié)點(diǎn)作為根，左子表和右子表中的結(jié)點(diǎn)分別作為根的左子樹和右子樹。由此得到的二叉樹，稱為二分查找判定樹(Decision Tree)或比較樹(Comparison Tree)[9-10]。二分查找判定樹是對有序表數(shù)據(jù)結(jié)構(gòu)很直觀形象的表達(dá)，便于訪問查找。

結(jié)點(diǎn)數(shù)為13的二分查找判定樹如圖1所示。

圖1 二分查找判定樹示意圖

判定樹傳統(tǒng)的構(gòu)造方法是依照二分查找算法的流程，逐步構(gòu)造的，需要依次確定根結(jié)點(diǎn)位置的元素、縮小范圍遞歸地對左子表進(jìn)行操作并確定根、縮小范圍遞歸地對右子表進(jìn)行操作并確定根。圖中的每一個(gè)結(jié)點(diǎn)都代表了一次查找。顯然這種面向過程的方法非常復(fù)雜，會(huì)對有序表的每一個(gè)元素都進(jìn)行比較，尤其當(dāng)結(jié)點(diǎn)數(shù)增多時(shí)，就顯得“耗時(shí)耗力”。

李金霞[1]等人提出了一種改進(jìn)的二分查找判定樹構(gòu)造方法，但是該方法的本質(zhì)也是一種面向過程的構(gòu)造方式，同樣存在著復(fù)雜性的問題。

本文提出的RHC構(gòu)造方法是面向計(jì)算的，有效避免了面向過程構(gòu)造方法的復(fù)雜性，做到迅速準(zhǔn)確。為了更好地說明RHC構(gòu)造法，首先給出傾斜二叉樹的定義。

2 傾斜二叉樹

2.1 相關(guān)定義

定義1(平衡因子)：對于二叉樹的結(jié)點(diǎn)v，其右子樹的所有結(jié)點(diǎn)個(gè)數(shù)NR與左子樹的所有結(jié)點(diǎn)個(gè)數(shù)NL之差(NR-NL)稱為v的平衡因子。

定義2(傾斜二叉樹)：具有n(n≥1)個(gè)結(jié)點(diǎn)的二叉樹，如果滿足，對任意結(jié)點(diǎn)v，v的平衡因子等于0或者1，即右子樹的結(jié)點(diǎn)個(gè)數(shù)或者比其左子樹的結(jié)點(diǎn)個(gè)數(shù)多1，或者與其左子樹的結(jié)點(diǎn)個(gè)數(shù)相等，那么稱這樣的二叉樹為傾斜二叉樹。

根據(jù)定義，對圖2所示樹形進(jìn)行判斷，顯然圖(a)是一棵傾斜二叉樹，因?yàn)樗械慕Y(jié)點(diǎn)都滿足平衡因子等于0或者1，圖(b)不是一棵傾斜二叉樹，盡管結(jié)點(diǎn)b、c、d、e的平衡因子均等于0，但是a結(jié)點(diǎn)的平衡因子等于2，不符合傾斜二叉樹的要求。

圖2 傾斜二叉樹示意圖

2.2 構(gòu)造——開關(guān)法

下面給出傾斜二叉樹的一種構(gòu)造方式，結(jié)合了面向過程的思想，稱為開關(guān)法(Switch Method)。假設(shè)初態(tài)時(shí)樹為空(即樹有0個(gè)結(jié)點(diǎn))，一共有n個(gè)小球，按順序依次完成進(jìn)樹的過程。每個(gè)小球進(jìn)樹到不能進(jìn)為止(即碰到空結(jié)點(diǎn)時(shí)停止進(jìn)樹)，并在該空結(jié)點(diǎn)處填補(bǔ)形成新的結(jié)點(diǎn)，比如第一個(gè)小球進(jìn)樹填補(bǔ)后成為根結(jié)點(diǎn)，以此類推；每個(gè)小球變成結(jié)點(diǎn)的同時(shí)就在對應(yīng)的結(jié)點(diǎn)位置生成出一個(gè)開關(guān)，開關(guān)一共有左右兩個(gè)狀態(tài)，用來判定當(dāng)后續(xù)球經(jīng)過時(shí)應(yīng)該向左走還是向右走，新生成的開關(guān)初始狀態(tài)為右；每有一個(gè)小球經(jīng)過一個(gè)開關(guān)，該開關(guān)的狀態(tài)發(fā)生一次改變。具體構(gòu)造過程如圖3所示。

圖3 傾斜二叉樹的構(gòu)造示意圖

如圖3(a)所示，第一個(gè)小球進(jìn)樹，變成根結(jié)點(diǎn)，生成開關(guān)，初始狀態(tài)向右。圖3(b)中，第二個(gè)小球進(jìn)樹，遇到第一個(gè)開關(guān)向右，相應(yīng)的開關(guān)狀態(tài)變?yōu)橄蜃?。小球不能再進(jìn)，變成新的結(jié)點(diǎn)，成為根結(jié)點(diǎn)的右兒子，生成新的開關(guān)，初始狀態(tài)向右。圖3(c)中，第三個(gè)小球進(jìn)樹，遇到第一個(gè)開關(guān)向左，相應(yīng)的開關(guān)狀態(tài)變?yōu)橄蛴遥∏虿荒茉龠M(jìn)，形成新的結(jié)點(diǎn)，成為根結(jié)點(diǎn)的左兒子，生成新的開關(guān)，初始狀態(tài)向右。圖3(d)中，第四個(gè)小球進(jìn)樹，遇到第一個(gè)開關(guān)向右，相應(yīng)的開關(guān)狀態(tài)變?yōu)橄蜃?，遇到第二個(gè)開關(guān)向右，相應(yīng)的開關(guān)狀態(tài)變?yōu)橄蜃?，小球不能再進(jìn)，形成新的結(jié)點(diǎn)和開關(guān)，開關(guān)初始狀態(tài)向右。

當(dāng)所有的小球都完成進(jìn)樹時(shí)，就構(gòu)造出了一棵結(jié)點(diǎn)數(shù)為n的傾斜二叉樹。因?yàn)獒槍蝹€(gè)結(jié)點(diǎn)v，凡是經(jīng)過結(jié)點(diǎn)v的小球，都是按照右、左、右、左的順序進(jìn)入其子樹的，所以對于每個(gè)結(jié)點(diǎn)v，其平衡因子或者等于1，或者等于0，符合傾斜二叉樹的定義。

2.3 性質(zhì)探究

由傾斜二叉樹的定義和構(gòu)造法，很容易給出以下性質(zhì)：

性質(zhì)1：結(jié)點(diǎn)數(shù)為n的傾斜二叉樹樹形唯一。

證明采用第二數(shù)學(xué)歸納法，對n進(jìn)行歸納。

當(dāng)n=1或n=2時(shí)，結(jié)論顯然成立，其樹形如圖3(a)和圖3(b)。

假設(shè)結(jié)論對n≤k均成立，那么當(dāng)n=k+1時(shí)，對n進(jìn)行奇偶討論分析。

若n為偶數(shù)，令n=2p，由傾斜二叉樹的定義可得：根結(jié)點(diǎn)的左子樹有p-1個(gè)結(jié)點(diǎn)，右子樹有p個(gè)結(jié)點(diǎn)。因?yàn)閜-1和p均小于等于k，由歸納假設(shè)知，它們的樹形是唯一的，所以這種假設(shè)下，結(jié)點(diǎn)總數(shù)為n的樹形也是唯一的。

若n為奇數(shù)，令n=2p+1，由傾斜二叉樹的定義可得：根結(jié)點(diǎn)的左、右子樹均有p個(gè)結(jié)點(diǎn)，同理可得此時(shí)結(jié)點(diǎn)總數(shù)為n的樹形是唯一的。

故結(jié)論對任意的n都成立，證明完畢。

性質(zhì)1建立了傾斜二叉樹與二分查找判定樹之間的一一對應(yīng)關(guān)系，確保了兩者構(gòu)造的等價(jià)性，是進(jìn)行后續(xù)性質(zhì)推導(dǎo)的前提。

性質(zhì)2：傾斜二叉樹的左子樹、右子樹也為傾斜二叉樹。

性質(zhì)3：對于結(jié)點(diǎn)數(shù)為n的傾斜二叉樹，樹高為k，其中:k=log2(n+1)，為上取整函數(shù)。

證明：采用第二數(shù)學(xué)歸納法,對n進(jìn)行歸納，

當(dāng)n=1或n=2時(shí)，結(jié)論顯然成立。

假設(shè)結(jié)論對n≤k均成立，那么當(dāng)n=k+1時(shí)，對n進(jìn)行奇偶討論分析。

若n為偶數(shù)，令n=2p，由傾斜二叉樹的定義可得：根結(jié)點(diǎn)的左子樹有個(gè)結(jié)點(diǎn)，右子樹有p個(gè)結(jié)點(diǎn)，因?yàn)閜-1和p均小于等于k，由歸納假設(shè)知，左子樹樹高為k1=log2(p)，右子樹樹高為k2=log2(p+1)，所以整個(gè)樹高為log2(p+1)+1，只需證log2(p+1)+1=log2(2p+1)，而k2-1

性質(zhì)4：若n是形如2m-1(m為正整數(shù))的整數(shù)，那么結(jié)點(diǎn)總數(shù)為n的傾斜二叉樹是滿二叉樹。

證明：利用性質(zhì)二可得，此時(shí)樹高為m，而樹高為m的二叉樹結(jié)點(diǎn)總數(shù)不超過2m-1，當(dāng)且僅當(dāng)二叉樹為滿二叉樹時(shí)取等，故結(jié)點(diǎn)總數(shù)為n的傾斜二叉樹是滿二叉樹，證畢。

性質(zhì)5：對于任意的n，k=log2(n+1)，結(jié)點(diǎn)總數(shù)為n的傾斜二叉樹的前k-1層，一定為滿二叉樹。

證明：同樣對n采用第二數(shù)學(xué)歸納法：

當(dāng)n=1或n=2時(shí)，結(jié)論顯然成立。

假設(shè)結(jié)論對n≤k的情況成立，那么當(dāng)n=k+1時(shí)，對n進(jìn)行奇偶討論分析。

若n為偶數(shù)，令n=2p，由傾斜二叉樹的定義可得：根結(jié)點(diǎn)的左子樹有p-1個(gè)結(jié)點(diǎn)，右子樹有p個(gè)結(jié)點(diǎn)，由性質(zhì)2知，左子樹樹高為k1=log2(p)，右子樹樹高為k2=log2(p+1)，因?yàn)閜-1和p均小于等于k，由歸納假設(shè)知，左子樹前k1-1層為滿二叉樹，右子樹前k2-1層為滿二叉樹。若k1=k2，則結(jié)論顯然成立；若k2=k1+1，則p=2k1，由性質(zhì)3知，左子樹前k1層為滿二叉樹，結(jié)論同樣成立。

若n為奇數(shù)，同理可證，故結(jié)論對任意的n均成立，證畢。

性質(zhì)2～5簡化了對二分查找判定樹樹形的判斷流程，僅僅需要判斷底層結(jié)點(diǎn)(即葉子結(jié)點(diǎn))的放置順序而不需要判斷整棵樹，進(jìn)一步說明了二分查找判定樹與完全二叉樹在性質(zhì)上的相似性。

性質(zhì)6：如果結(jié)點(diǎn)v的平衡因子等于0，那么結(jié)點(diǎn)v的左、右子樹樹形完全一致。

由于結(jié)點(diǎn)v的平衡因子等于0，因此結(jié)點(diǎn)v的左、右子樹結(jié)點(diǎn)數(shù)相等。根據(jù)性質(zhì)1結(jié)點(diǎn)數(shù)與樹形之間的一一對應(yīng)關(guān)系，故左、右子樹樹形完全一致。

在給出性質(zhì)7之前，先定義逆向哈夫曼編碼(Reverse Huffman Coding，RHC)。

定義3(逆向哈弗曼編碼)：對傾斜二叉樹上的每條邊附上編號(hào)，左枝編號(hào)為0，右枝編號(hào)為1。模仿哈弗曼編碼的形式，對第k層上的每個(gè)結(jié)點(diǎn)，按照從結(jié)點(diǎn)到根的路徑順序得到一個(gè)二進(jìn)制編碼序列，該序列稱為該結(jié)點(diǎn)的逆向哈弗曼編碼。

圖4為一棵逆向哈弗曼編碼樹，其中第三層上結(jié)點(diǎn)的逆向哈弗曼編碼依次為(00)2、(10)2、(01)2、(11)2。依照逆向哈弗曼編碼的構(gòu)造特征，可以得到性質(zhì)7所述的結(jié)點(diǎn)放置順序。

圖4 逆向哈弗曼編碼樹

性質(zhì)7：如果對傾斜二叉樹的第k層的每個(gè)結(jié)點(diǎn)進(jìn)行RHC編碼，且將第k層的結(jié)點(diǎn)按照編碼值由大到小的順序排列，那么第k層的結(jié)點(diǎn)一定是由排序序列中前n-2k-1+1個(gè)結(jié)點(diǎn)構(gòu)成。

證明：對層數(shù)k應(yīng)用數(shù)學(xué)歸納法。

當(dāng)k=2時(shí)，顯然此結(jié)論成立。

假設(shè)當(dāng)k=m時(shí)，結(jié)論也成立，

那么，當(dāng)k=m+1時(shí)，由性質(zhì)2可得：根結(jié)點(diǎn)的左右子樹各有m層，且均為傾斜二叉樹。根據(jù)RHC的定義，第m+1層的結(jié)點(diǎn)編碼共有m位，且最低位(即第m位)編碼由根結(jié)點(diǎn)的枝節(jié)決定，前m-1位編碼由左子樹或右子樹決定。結(jié)合開關(guān)法的過程，結(jié)點(diǎn)按照右、左的順序依次重復(fù)出現(xiàn)在根結(jié)點(diǎn)的子樹上，故結(jié)點(diǎn)編碼的第m位一定是按1、0、1、0的順序重復(fù)出現(xiàn)。而由歸納假設(shè)：前m-1位滿足由大到小的順序，且根據(jù)性質(zhì)6，左、右子樹對稱一致，所以對于整個(gè)m位的逆哈弗曼編碼，結(jié)點(diǎn)符合編碼值由大到小的順序出現(xiàn)。因此結(jié)論成立。

例如：當(dāng)n=5時(shí)，需要在第三層上取兩個(gè)結(jié)點(diǎn)，那么按照編碼值排序，應(yīng)分別取編碼為(11)2和(10)2的結(jié)點(diǎn)，如圖4所示，圖中灰色圓形表示第三層上應(yīng)該包含的結(jié)點(diǎn)。

性質(zhì)6和7，借助二進(jìn)制哈弗曼編碼，以面向計(jì)算的方式確立了底層結(jié)點(diǎn)的放置順序，這是RHC構(gòu)造法成立的理論基礎(chǔ)。

3 RHC構(gòu)造法

根據(jù)以上對傾斜二叉樹性質(zhì)的研究，給出二分查找判定樹的RHC構(gòu)造法，具體步驟如下：

第一步：確定二分查找判定樹的層數(shù)。由性質(zhì)3可知，對于結(jié)點(diǎn)數(shù)為n的傾斜二叉樹，樹高k滿足k=log2(n+1)。

第二步：根據(jù)性質(zhì)5，二分查找判定樹前k-1層是一棵滿二叉樹，將前k-1層結(jié)點(diǎn)取滿。

第三步：對第k層結(jié)點(diǎn)按照RHC規(guī)則編碼，分別計(jì)算對應(yīng)的編碼值，將編碼值按照從大到小的順序排列，由性質(zhì)6，取排序序列中前n-2k-1+1個(gè)結(jié)點(diǎn)。

第四步：填入關(guān)鍵字，使得中序遍歷該樹為遞增(或遞減)序列。

如果結(jié)點(diǎn)數(shù)增加，不必重新構(gòu)造該判定樹，只要按照如上規(guī)則增加一個(gè)結(jié)點(diǎn)，然后重新填入關(guān)鍵字，使其中序遍歷為遞增(或遞減)序列即可。

至此長度為n的有序順序表進(jìn)行二分查找時(shí)的判定樹構(gòu)造完成。

下面以結(jié)點(diǎn)總數(shù)13為例，給出RHC構(gòu)造法的演示。

第一步：確定樹高k，k=log2(n+1)=log214=4；

第二步：前k-1層，即前3層取滿；

第三步：對第k層編碼，如圖5所示，取前n-2k-1+1=6個(gè)點(diǎn)；

第四步：按照中序序列填數(shù)，最終填數(shù)后得到的結(jié)果如圖6所示。

圖5 逆向哈弗曼編碼圖

圖6 結(jié)點(diǎn)數(shù)為13的二分查找判定樹

中序序列填數(shù)完成后可以做一個(gè)投影，在樹形規(guī)則的前提下，可以發(fā)現(xiàn)投影是一個(gè)遞增的序列，并把數(shù)軸分成了14個(gè)區(qū)域。

4 性能分析

評估構(gòu)造法效率最直接的方式，是計(jì)算使用該構(gòu)造法需要耗用多少時(shí)間。于是，假設(shè)一次運(yùn)算耗時(shí)一個(gè)單位時(shí)間，便將效率分析問題轉(zhuǎn)換為統(tǒng)計(jì)運(yùn)算次數(shù)問題。

傳統(tǒng)面向過程(Process-oriented)的構(gòu)造法需要對二分查找判定樹上的每個(gè)結(jié)點(diǎn)運(yùn)算三次，分別是計(jì)算左邊界下標(biāo)、右邊界下標(biāo)和“中值”點(diǎn)下標(biāo)。因此，對于結(jié)點(diǎn)總數(shù)為n的二分查找判定樹，面向過程構(gòu)造法需要耗時(shí)TP-o(n)=3×n。RHC構(gòu)造法利用逆向哈弗曼編碼和二分查找判定樹的中序有序性，只需針對二分查找判定樹最底層的結(jié)點(diǎn)計(jì)算編碼值，每個(gè)底層結(jié)點(diǎn)只運(yùn)算一次，所以，對于結(jié)點(diǎn)總數(shù)為n的二分查找判定樹，總耗時(shí)TC-o(n)滿足TC-o(n)=2k-1，其中k表示二分查找判定樹的樹高，k=log2(n+1)。

根據(jù)上述的耗用時(shí)間表達(dá)式，分別繪制出運(yùn)算耗費(fèi)時(shí)間隨結(jié)點(diǎn)數(shù)變化的趨勢圖，如圖7所示。

圖7 效率對比

從圖7中可以看出，面向過程的構(gòu)造法對應(yīng)了一條直線，其耗用時(shí)間與結(jié)點(diǎn)總數(shù)呈線性關(guān)系。RHC構(gòu)造法是一個(gè)分段函數(shù)，運(yùn)算時(shí)間與樹高有關(guān)。通過比較分析，相較于傳統(tǒng)構(gòu)造法，RHC構(gòu)造法存在明顯的優(yōu)越性，并且當(dāng)結(jié)點(diǎn)總數(shù)增加時(shí)，這種優(yōu)越性更加明顯。

另外，當(dāng)結(jié)點(diǎn)總數(shù)為n的二分查找判定樹樹形已知，需要新增一個(gè)結(jié)點(diǎn)時(shí)，面向過程的構(gòu)造法必須重新構(gòu)造整個(gè)二分查找判定樹，因?yàn)槊嫦蜻^程的構(gòu)造法不具有可重復(fù)性，由前面的分析可知，這種情況，傳統(tǒng)方法需要的時(shí)間復(fù)雜度是O(n)，而RHC構(gòu)造法只需要在原有樹形的基礎(chǔ)上額外進(jìn)行一次運(yùn)算，該方法對應(yīng)的時(shí)間復(fù)雜度是O(1)，這大大提高了構(gòu)造效率。

5 結(jié)束語

本文定義的傾斜二叉樹實(shí)用性強(qiáng)，具有很好的平衡性和單向傾斜性，基于傾斜二叉樹性質(zhì)提出的RHC構(gòu)造法是一種面向計(jì)算的構(gòu)造法，經(jīng)對比驗(yàn)證，比傳統(tǒng)面向過程的構(gòu)造法更高效、迅速、準(zhǔn)確。該方法對于同類的采用分治方法進(jìn)行問題求解的算法分析具有借鑒意義。