二分查找判定樹的RHC構造法*

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

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

0 引言

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

1 二分查找判定樹

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

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

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

結點數為13的二分查找判定樹如圖1所示。

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

判定樹傳統的構造方法是依照二分查找算法的流程，逐步構造的，需要依次確定根結點位置的元素、縮小范圍遞歸地對左子表進行操作并確定根、縮小范圍遞歸地對右子表進行操作并確定根。圖中的每一個結點都代表了一次查找。顯然這種面向過程的方法非常復雜，會對有序表的每一個元素都進行比較，尤其當結點數增多時，就顯得“耗時耗力”。

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

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

2 傾斜二叉樹

2.1 相關定義

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

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

根據定義，對圖2所示樹形進行判斷，顯然圖(a)是一棵傾斜二叉樹，因為所有的結點都滿足平衡因子等于0或者1，圖(b)不是一棵傾斜二叉樹，盡管結點b、c、d、e的平衡因子均等于0，但是a結點的平衡因子等于2，不符合傾斜二叉樹的要求。

圖2 傾斜二叉樹示意圖

2.2 構造——開關法

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

圖3 傾斜二叉樹的構造示意圖

如圖3(a)所示，第一個小球進樹，變成根結點，生成開關，初始狀態向右。圖3(b)中，第二個小球進樹，遇到第一個開關向右，相應的開關狀態變為向左。小球不能再進，變成新的結點，成為根結點的右兒子，生成新的開關，初始狀態向右。圖3(c)中，第三個小球進樹，遇到第一個開關向左，相應的開關狀態變為向右，小球不能再進，形成新的結點，成為根結點的左兒子，生成新的開關，初始狀態向右。圖3(d)中，第四個小球進樹，遇到第一個開關向右，相應的開關狀態變為向左，遇到第二個開關向右，相應的開關狀態變為向左，小球不能再進，形成新的結點和開關，開關初始狀態向右。

當所有的小球都完成進樹時，就構造出了一棵結點數為n的傾斜二叉樹。因為針對單個結點v，凡是經過結點v的小球，都是按照右、左、右、左的順序進入其子樹的，所以對于每個結點v，其平衡因子或者等于1，或者等于0，符合傾斜二叉樹的定義。

2.3 性質探究

由傾斜二叉樹的定義和構造法，很容易給出以下性質：

性質1：結點數為n的傾斜二叉樹樹形唯一。

證明采用第二數學歸納法，對n進行歸納。

當n=1或n=2時，結論顯然成立，其樹形如圖3(a)和圖3(b)。

假設結論對n≤k均成立，那么當n=k+1時，對n進行奇偶討論分析。

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

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

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

性質1建立了傾斜二叉樹與二分查找判定樹之間的一一對應關系，確保了兩者構造的等價性，是進行后續性質推導的前提。

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

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

證明：采用第二數學歸納法,對n進行歸納，

當n=1或n=2時，結論顯然成立。

假設結論對n≤k均成立，那么當n=k+1時，對n進行奇偶討論分析。

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

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

證明：利用性質二可得，此時樹高為m，而樹高為m的二叉樹結點總數不超過2m-1，當且僅當二叉樹為滿二叉樹時取等，故結點總數為n的傾斜二叉樹是滿二叉樹，證畢。

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

證明：同樣對n采用第二數學歸納法：

當n=1或n=2時，結論顯然成立。

假設結論對n≤k的情況成立，那么當n=k+1時，對n進行奇偶討論分析。

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

若n為奇數，同理可證，故結論對任意的n均成立，證畢。

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

性質6：如果結點v的平衡因子等于0，那么結點v的左、右子樹樹形完全一致。

由于結點v的平衡因子等于0，因此結點v的左、右子樹結點數相等。根據性質1結點數與樹形之間的一一對應關系，故左、右子樹樹形完全一致。

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

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

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

圖4 逆向哈弗曼編碼樹

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

證明：對層數k應用數學歸納法。

當k=2時，顯然此結論成立。

假設當k=m時，結論也成立，

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

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

性質6和7，借助二進制哈弗曼編碼，以面向計算的方式確立了底層結點的放置順序，這是RHC構造法成立的理論基礎。

3 RHC構造法

根據以上對傾斜二叉樹性質的研究，給出二分查找判定樹的RHC構造法，具體步驟如下：

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

第二步：根據性質5，二分查找判定樹前k-1層是一棵滿二叉樹，將前k-1層結點取滿。

第三步：對第k層結點按照RHC規則編碼，分別計算對應的編碼值，將編碼值按照從大到小的順序排列，由性質6，取排序序列中前n-2k-1+1個結點。

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

如果結點數增加，不必重新構造該判定樹，只要按照如上規則增加一個結點，然后重新填入關鍵字，使其中序遍歷為遞增(或遞減)序列即可。

至此長度為n的有序順序表進行二分查找時的判定樹構造完成。

下面以結點總數13為例，給出RHC構造法的演示。

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

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

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

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

圖5 逆向哈弗曼編碼圖

圖6 結點數為13的二分查找判定樹

中序序列填數完成后可以做一個投影，在樹形規則的前提下，可以發現投影是一個遞增的序列，并把數軸分成了14個區域。

4 性能分析

評估構造法效率最直接的方式，是計算使用該構造法需要耗用多少時間。于是，假設一次運算耗時一個單位時間，便將效率分析問題轉換為統計運算次數問題。

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

根據上述的耗用時間表達式，分別繪制出運算耗費時間隨結點數變化的趨勢圖，如圖7所示。

圖7 效率對比

從圖7中可以看出，面向過程的構造法對應了一條直線，其耗用時間與結點總數呈線性關系。RHC構造法是一個分段函數，運算時間與樹高有關。通過比較分析，相較于傳統構造法，RHC構造法存在明顯的優越性，并且當結點總數增加時，這種優越性更加明顯。

另外，當結點總數為n的二分查找判定樹樹形已知，需要新增一個結點時，面向過程的構造法必須重新構造整個二分查找判定樹，因為面向過程的構造法不具有可重復性，由前面的分析可知，這種情況，傳統方法需要的時間復雜度是O(n)，而RHC構造法只需要在原有樹形的基礎上額外進行一次運算，該方法對應的時間復雜度是O(1)，這大大提高了構造效率。

5 結束語

本文定義的傾斜二叉樹實用性強，具有很好的平衡性和單向傾斜性，基于傾斜二叉樹性質提出的RHC構造法是一種面向計算的構造法，經對比驗證，比傳統面向過程的構造法更高效、迅速、準確。該方法對于同類的采用分治方法進行問題求解的算法分析具有借鑒意義。