魏志威，王防修

(武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430023)

?

一種無(wú)需借助棧的嚴(yán)格平衡二叉樹(shù)建立

魏志威，王防修

(武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430023)

摘要：針對(duì)當(dāng)前嚴(yán)格平衡二叉樹(shù)的建立需要借助棧來(lái)實(shí)現(xiàn)的問(wèn)題，提出一種無(wú)需借助棧也能建立嚴(yán)格平衡二叉樹(shù)的算法。為能對(duì)關(guān)鍵字進(jìn)行二分查找，需要對(duì)現(xiàn)有的關(guān)鍵字序列進(jìn)行排序,以便統(tǒng)計(jì)關(guān)鍵字的有序序列中每個(gè)關(guān)鍵字在二分查找時(shí)的比較次數(shù)。在統(tǒng)計(jì)完所有關(guān)鍵字的二分查找的比較次數(shù)后,通過(guò)關(guān)鍵字比較次數(shù)序列的排序得到嚴(yán)格平衡二叉樹(shù)序列。最后，用非遞歸的二叉排序樹(shù)插入算法依次插入嚴(yán)格平衡二叉樹(shù)序列的每個(gè)關(guān)鍵字，得到的二叉排序樹(shù)就是一棵嚴(yán)格平衡二叉樹(shù)。算例仿真表明，無(wú)需借助棧也可建立一棵嚴(yán)格平衡二叉樹(shù)。

關(guān)鍵詞：選擇排序；二叉排序樹(shù)；嚴(yán)格平衡二叉樹(shù)；二分查找；查找效率

1引言

在信息的查詢(xún)中，二分查找由于具有較高的查找效率而受到人們的青睞。然而，二分查找[1]要求索引表在計(jì)算機(jī)內(nèi)存里必須以有序順序表的形式存放。如果內(nèi)存中地址連續(xù)的空閑存儲(chǔ)空間不夠，則這樣的順序表無(wú)法建立，從而也就無(wú)法實(shí)現(xiàn)二分查找。與二分查找具有相同查找效率的是嚴(yán)格平衡二叉樹(shù)，而嚴(yán)格平衡二叉樹(shù)能充分利用地址不連續(xù)的空閑內(nèi)存空間。因此，從內(nèi)存管理[2]的角度出發(fā)，嚴(yán)格平衡二叉樹(shù)的查詢(xún)使用得更加廣泛。

目前，建立嚴(yán)格平衡二叉樹(shù)的方法不外乎兩種，分別是遞歸算法[3-4]和非遞歸算法[5]。然而，無(wú)論是遞歸方法還是非遞歸方法，都需要借助棧。比如遞歸算法需要使用系統(tǒng)棧，而非遞歸算法則需要使用用戶(hù)自定義棧。那么能否不使用棧也可建立嚴(yán)格平衡二叉樹(shù)呢，本文將研究并解決該問(wèn)題。

2建立嚴(yán)格平衡二叉樹(shù)的原理

由輸入的關(guān)鍵字序列建立的二叉排序樹(shù)不一定是嚴(yán)格平衡二叉樹(shù)，只有特定的關(guān)鍵字序列輸入才能使得建立的二叉排序樹(shù)是嚴(yán)格平衡二叉樹(shù)。比如相同的整數(shù)關(guān)鍵字集合{6,7,8,9,10,11}，如果輸入序列為8,7,6,11,10,9，則建立的二叉排序樹(shù)不是嚴(yán)格平衡二叉樹(shù)。相反，如果輸入序列為9,7,6,8,11,10，則建立的二叉排序樹(shù)就是嚴(yán)格平衡二叉樹(shù)。由于二叉排序樹(shù)可以在無(wú)需借助棧的情況下非遞歸建立，因此只要找到關(guān)鍵字集合的特定輸入序列，則可以使建立的二叉排序樹(shù)就是嚴(yán)格平衡二叉樹(shù)。為敘述方便，不妨將這種序列稱(chēng)為嚴(yán)格平衡二叉樹(shù)序列。

設(shè)X=x1x2…xn是由n個(gè)關(guān)鍵字xi(i=1,2,…,n)組成的關(guān)鍵字序列，如果能將其轉(zhuǎn)化為一個(gè)嚴(yán)格平衡二叉樹(shù)序列Y=y1y2…yn，則由Y建立的二叉排序樹(shù)就是嚴(yán)格平衡二叉樹(shù)。

由X=x1x2…xn得到關(guān)鍵字的升序序列Z=z1z2…zn,即z1

因此, 升序序列Z=z1z2…zn與比較次數(shù)序列C=c1c2…cn之間存在一對(duì)一的關(guān)系,即存在一個(gè)二分查找函數(shù)f,使得

ci=f(Z,zi),i=1,2,…,n.

(1)

進(jìn)一步對(duì)比較次數(shù)序列C=c1c2…cn進(jìn)行升序排序,如果在排序過(guò)程中發(fā)生ci與cj互換,則zi與zj也進(jìn)行互換。當(dāng)比較次數(shù)序列C=c1c2…cn變?yōu)樯蛐蛄袝r(shí),則此時(shí)的Z=z1z2…zn就是一個(gè)嚴(yán)格平衡二叉樹(shù)序列。

在二叉排序中,越早插入的關(guān)鍵字,由于其在二叉排序樹(shù)的路徑越短,從而在二叉排序查找過(guò)程中的比較次數(shù)也越少,而這與二分查找的比較次數(shù)是一致的。因此,根據(jù)得到的嚴(yán)格平衡二叉樹(shù)序列就可以建立關(guān)鍵字的嚴(yán)格平衡二叉樹(shù)。

3建立嚴(yán)格平衡二叉樹(shù)的算法

根據(jù)建立嚴(yán)格平衡二叉樹(shù)的原理,為了保證建立的二叉排序樹(shù)是嚴(yán)格平衡二叉樹(shù),需要改變關(guān)鍵字的輸入順序,因?yàn)槎媾判驑?shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不光與關(guān)鍵字的大小有關(guān),還與關(guān)鍵字的插入二叉排序樹(shù)的先后有關(guān)。

整個(gè)建立嚴(yán)格平衡二叉樹(shù)的算法步驟可以歸納如下。

第1步通過(guò)排序,將一個(gè)初始的關(guān)鍵字序列轉(zhuǎn)化為一個(gè)關(guān)鍵字的升序序列。不妨設(shè)初始序列為X=x1x2…xn,而轉(zhuǎn)化后的升序序列為Z=z1z2…zn。

第2步用二分查找統(tǒng)計(jì)升序序列中每個(gè)元素zi(i=1,2,…,n)在查找過(guò)程中的比較次數(shù)ci(i=1,2,…,n),其計(jì)算公式見(jiàn)(1)式。

第3步對(duì)比較次數(shù)序列C=c1c2…cn進(jìn)行升序排序。如果在排序過(guò)程中出現(xiàn)需要ci與cj交換,則相應(yīng)有zi與zj交換。排序的結(jié)果是, C=c1c2…cn是一個(gè)升序序列,而Z=z1z2…zn變成一個(gè)嚴(yán)格平衡二叉樹(shù)序列。

第4步在二叉排序樹(shù)的建立過(guò)程中,依次插入嚴(yán)格平衡二叉樹(shù)序列中的每個(gè)關(guān)鍵字,則最終得到嚴(yán)格平衡二叉樹(shù)。

3.1初始序列的選擇排序

對(duì)于一個(gè)無(wú)序的關(guān)鍵字序列X=x1x2…xn，序列中的元素各不相同。為了將其變成一個(gè)關(guān)鍵字的升序序列，需要進(jìn)行的選擇排序過(guò)程如下：

步0 給出關(guān)鍵字序列X=x1x2…xn。令i=1。

步1令l=i，表示第i個(gè)位置需要競(jìng)爭(zhēng)。

步2令j=i+1，如果xj

步3如果j

步4如果l≠i，則將xl與xi交換，即

xl=min{xi,xi+1,…,xn}.

(2)

步5令i=i+1。如果i

經(jīng)過(guò)選擇排序后，X=x1x2…xn變成一個(gè)關(guān)鍵字的升序序列。

3.2二分查找統(tǒng)計(jì)比較次數(shù)

由于無(wú)序序列X經(jīng)過(guò)3.1中的選擇排序后，已經(jīng)變成一個(gè)關(guān)鍵字的升序序列。因此，接下來(lái)就可以用二分查找法依次統(tǒng)計(jì)每個(gè)關(guān)鍵字的比較次數(shù)。統(tǒng)計(jì)過(guò)程如下：

步0令i=1和cj=0(j=1,2,…,n)。

步1令l=1，h=n。

步3令ci=ci+1。如果xi≠xm，則轉(zhuǎn)步2；否則，轉(zhuǎn)步4。

步4令i=i+1。如果i

3.3嚴(yán)格平衡二叉樹(shù)序列生成

從生成嚴(yán)格平衡二叉序列的原理可知，該序列的生成完全取決于比較序列C的升序排序。在升序排序過(guò)程中，如果出現(xiàn)ci與cj交換，則同時(shí)進(jìn)行xi與xj的交換。具體步驟如下：

步0根據(jù)算法3.2，用二分法統(tǒng)計(jì)出關(guān)鍵字升序序列X中的每個(gè)元素xi的比較次數(shù)ci，得到比較次數(shù)序列C=c1c2…cn。令i=1。

步1令l=i，表示第i個(gè)位置需要競(jìng)爭(zhēng)。

步2令j=i+1，如果cj

步3如果j

步4如果l≠i，則將cl與ci交換，即

cl=min{ci,ci+1,…,cn}.

(3)

同時(shí)將xi與xj交換。

步5令i=i+1。如果i

步6在二叉排序樹(shù)的非遞歸建立[6]過(guò)程中，依次插入關(guān)鍵字xi(i=1,2,…,n)。

經(jīng)過(guò)上述算法，先通過(guò)選擇排序生成嚴(yán)格平衡二叉樹(shù)序列，然后由該序列的非遞歸插入產(chǎn)生的二叉排序樹(shù)就是嚴(yán)格平衡二叉樹(shù)。

4算例測(cè)試

本算法使用VC 6.0作為仿真工具，在CPU為3.2 GHz和內(nèi)存為1.86 Gb的個(gè)人臺(tái)式電腦上完成仿真。

算例1已知關(guān)鍵字序列X={36, 15,18，17，53 ,45 ,48 ,47,72 ,93 ,95，100}。求由該整型關(guān)鍵字序列構(gòu)成的嚴(yán)格平衡二叉樹(shù)。

解第一步關(guān)鍵字序列X通過(guò)選擇排序轉(zhuǎn)化為關(guān)鍵字的升序序列X={15, 17,18，36，45,47,48,53,72,93,95，100}。

第二步元素xi(i=1,2,…,12)在二分查找X過(guò)程中的比較次數(shù)ci(i=1,2,…,12)如表1所示。

表1二分查找關(guān)鍵字的比較次數(shù)

i123456789101112xi1517183645474853729395100ci342341342434

第三步在對(duì)比較次數(shù)序列ci(i=1,2,…,12)進(jìn)行升序排序過(guò)程中得到如表2所示的關(guān)鍵字序列xi(i=1,2,…,12)。

表2關(guān)鍵字重排結(jié)果

i123456789101112ci122333344444xi4718721536489517455393100

第四步根據(jù)得表2所示的嚴(yán)格平衡二叉樹(shù)序列xi(i=1,2,…,12)構(gòu)造的二叉排序樹(shù)如圖1。

圖1　二叉樹(shù)排序樹(shù)

顯然，圖1顯示的二叉樹(shù)排序樹(shù)是一棵嚴(yán)格平衡二叉樹(shù)。

算例2已知關(guān)鍵字序列X={C, B,A，G,E，D，F(xiàn)}。求由該字符關(guān)鍵字構(gòu)成的嚴(yán)格平衡二叉樹(shù)。

解第一步 關(guān)鍵字序列X通過(guò)選擇排序轉(zhuǎn)化為關(guān)鍵字的升序序列X={A,B,C,D,E,F,G}。

第二步 元素xi(i=1,2,…,7)在二分查找X過(guò)程中的比較次數(shù)ci(i=1,2,…,7)如表3。

表3字符二分查找的比較次數(shù)

i1234567xiABCDEFGci3231323

第三步比較次數(shù)序列ci(i=1,2,…,7)進(jìn)行升序排序后得到如表4示的關(guān)鍵字序列xi(i=1,2,…,7)。

表4字符重排結(jié)果

i1234567ci1223333xiDBFACEG

第四步根據(jù)表4所示的嚴(yán)格平衡二叉樹(shù)序列xi(i=1,2,…,7)構(gòu)造的二叉排序樹(shù)如圖2。

圖2　二叉排序樹(shù)

同樣,如圖2所示的二叉排序樹(shù)是一棵嚴(yán)格平衡二叉樹(shù)。

5算法分析

筆者設(shè)計(jì)的算法有兩次升序排序:一次是關(guān)鍵字的選擇升序排序,該排序是為關(guān)鍵字的二分查找做準(zhǔn)備的;另一個(gè)是關(guān)鍵字的比較次數(shù)的選擇升序排序,它是生成嚴(yán)格平衡二叉樹(shù)序列的關(guān)鍵.需要指出的是，兩次排序都是用的選擇排序，而且都是升序排序。事實(shí)上，這里也可以選擇其它任意一種排序方法，而且無(wú)論是升序排序還是降序排序都可以。也就是說(shuō)，可以是下列情形之一。

(1)關(guān)鍵字序列與比較次數(shù)序列都是升序。

(2)關(guān)鍵字序列與比較次數(shù)序列都是降序。

(3)關(guān)鍵字序列是升序排序，而比較次數(shù)序列是降序排序。

(4)關(guān)鍵字序列是降序排序，而比較次數(shù)序列是升序排序。

無(wú)論采用上述哪種情形,最終都會(huì)得到相同的嚴(yán)格平衡二叉樹(shù)序列,即構(gòu)造的嚴(yán)格平衡二叉樹(shù)是唯一的。如果關(guān)鍵字的比較次數(shù)序列采用升序排序，即情形(1)或情形(4),則嚴(yán)格平衡二叉樹(shù)序列是X=x1x2…xn。如果是情形(2)或情形(3),則嚴(yán)格平衡二叉樹(shù)序列是X=xnxn-1…x1。

6結(jié)束語(yǔ)

筆者提出了一種不需要借助棧也可以構(gòu)造嚴(yán)格平衡二叉樹(shù)的非遞歸算法。通過(guò)排序算法將關(guān)鍵字序列變?yōu)橐粋€(gè)有序序列,將其作為二分查找的依據(jù)。利用二分查找算法,對(duì)關(guān)鍵字序列中的每個(gè)關(guān)鍵字進(jìn)行二分查找的比較次數(shù)進(jìn)行統(tǒng)計(jì)。進(jìn)一步使用排序算法對(duì)查找次數(shù)序列進(jìn)行排序,在排序過(guò)程中對(duì)關(guān)鍵字的相應(yīng)位置進(jìn)行調(diào)整,排序完后就形成一個(gè)嚴(yán)格平衡二叉樹(shù)序列。最后,通過(guò)嚴(yán)格平衡二叉樹(shù)序列建立二叉排序樹(shù),該二叉排序樹(shù)就是一棵嚴(yán)格平衡二叉樹(shù)。實(shí)驗(yàn)結(jié)果表明,利用本文算法進(jìn)行二叉排序樹(shù)的建立,能夠?qū)崿F(xiàn)不借助棧也能非遞歸地建立一棵嚴(yán)格平衡二叉樹(shù)。

參考文獻(xiàn):

[1]譚浩強(qiáng).實(shí)用數(shù)據(jù)結(jié)構(gòu)[M].北京: 清華大學(xué)出版社,2008．

[2]孫曉輝,王勁林,陳曉.實(shí)時(shí)系統(tǒng)中的動(dòng)態(tài)內(nèi)存分配算法[J] .計(jì)算機(jī)工程 ,2008, 34(8): 80-81.

[3]岑崗,周炳生.嚴(yán)格平衡二叉排序樹(shù)及其構(gòu)造[J].計(jì)算機(jī)工程與應(yīng)用 ,2005 (13): 57-60．

[4]胡云 ,黃震宇. 一種快速構(gòu)建平衡二叉搜索樹(shù)的算法[J] 大慶師范學(xué)院學(xué)報(bào), 2008，28(2)：20-23.

[5]王防修,周康. 一種構(gòu)建嚴(yán)格平衡二叉搜索樹(shù)的非遞歸算法[J]. 武漢工業(yè)學(xué)院學(xué)報(bào), 2013，32(4)：32-34。

[6]徐孝凱，賀桂英.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言描述)[M].北 京: 清華大學(xué)出版社,2008．

A method to establish a strict balance two

fork tree without the help of a stack

WEIZhi-wei，WANGFang-xiu

(School of Mathematics and Computer Science,Wuhan Polytechnic University,Wuhan 430023,China)

Abstract：Because establishment of a strict balanced two binary tree needs the help of the stack, this paper presents an algorithm to establish a strict balanced two binary tree without the help of the stack. In order to search for keywords in half, it needs to sort the existing keyword sequence. It statistics the number of comparision in binary search in the ordered keyword sequence. A strict balanced binary tree sequence will be obtained by the sortion of the times of comparison of the keywords after the statistics. Finally, a strict balance two fork tree is obtained after every keyword has been successively inserted into the two binary sort tree on non recursive insertion algorithm. The results of the examples show that a strict balance two fork tree can also be established without the help of the stack.

Key words：Selection sort; Two binary sort tree; Strict balanced two binary tree; Binary search; Search efficiency

DOI:10.3969/j.issn.2095-7386.2015.04.013

文章編號(hào)：2095-7386(2015)04-0051-05

基金項(xiàng)目：2013年國(guó)家自然科學(xué) (61201452).

作者簡(jiǎn)介：劉光蓉(1971-)，女，副教授，E-mail：lgr981009@126.com.

收稿日期：2015-09-14.

中圖分類(lèi)號(hào)：TP 391

文獻(xiàn)標(biāo)識(shí)碼：A