劉紹翰 高天行 黃志球

(南京航空航天大學(xué)信息科學(xué)與技術(shù)學(xué)院,南京 210093)

平衡樹是二叉查找樹的一種,維持樹的平衡可以避免二叉查找樹的病態(tài)結(jié)構(gòu),減少查找路徑的平均長(zhǎng)度,降低查找的時(shí)間平均復(fù)雜度.自1962年第一種平衡樹被發(fā)現(xiàn)至今[1],圍繞著更簡(jiǎn)單的實(shí)現(xiàn)和更高的性能,提出了多種平衡樹,不同平衡樹的平衡調(diào)整策略往往不相同.最經(jīng)典的平衡樹是AVL樹[1],加權(quán)平衡樹[2]、替罪羊樹[3]、伸展樹[4]、隨機(jī)平衡樹[5]、秩平衡樹等[6].AVL樹的性能是最優(yōu)二叉查找樹與任意二叉樹的折衷,平衡程度嚴(yán)格,查找的時(shí)間復(fù)雜度低,適用于刪除插入操作較少的場(chǎng)合.

本文對(duì)AVL樹的實(shí)現(xiàn)進(jìn)行了分析研究:第1部分介紹了二叉查找樹及AVL樹的基本原理和操作;第2部分在分析AVL樹的數(shù)學(xué)模型的基礎(chǔ)上,給出了更為簡(jiǎn)潔的數(shù)學(xué)描述—HAVL樹,包括定義、插入、刪除、平衡等基本操作;最后進(jìn)行了總結(jié).

1 二叉查找樹的基本性質(zhì)與操作

一棵二叉查找樹是按二叉樹結(jié)構(gòu)來組織的.其每個(gè)節(jié)點(diǎn)中至少含有3個(gè)域:key,left,right.其中key為關(guān)鍵字域,用于節(jié)點(diǎn)大小的比較;left和right用來存放指向左子樹和右子樹的指針.如果某個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)不存在,則該節(jié)點(diǎn)相應(yīng)的指針域?yàn)镹IL.二叉查找樹中關(guān)鍵字的存儲(chǔ)方式滿足二叉查找樹性質(zhì):設(shè)x為二叉查找樹的一個(gè)節(jié)點(diǎn),如果y是x的左子樹中的一個(gè)節(jié)點(diǎn),則key[y]≤key[x];如果y是x的右子樹中的一個(gè)節(jié)點(diǎn),則key[x]≤key[y].

一棵n個(gè)節(jié)點(diǎn)高度為h的二叉查找樹的基本操作如下,如SEARCH(查找)、PREDECESSOR(前驅(qū))、SUCCESSOR(后繼)、MINIMUM(最小值)、MAXIM UN(最大值)、INSERT(插入)、DELETE(刪除)、HAVL-MAINTAIN(維持平衡)和輔助ROTATE(旋轉(zhuǎn)操作)等,其時(shí)間復(fù)雜度都為O(lgn).當(dāng)樹退化為線性結(jié)構(gòu)時(shí),其操作的時(shí)間復(fù)雜度就與鏈表相同,為O(n);而平衡二叉查找樹通過旋轉(zhuǎn)使二叉樹在插入、刪除等操作過程中保持子樹的高度差相差不大,能保證在最壞情況下查找的時(shí)間復(fù)雜度為 O (lgn).

AVL的邏輯簡(jiǎn)單,易于理解,效率優(yōu)秀.但是AVL實(shí)現(xiàn)較復(fù)雜,因?yàn)槠溆糜谄胶獾母郊佑虿僮鲝?fù)雜,不易于更新,本文采用另一種“簡(jiǎn)單的”附加域—高度(Height)來代替通常用的平衡因子,用于控制二叉查找樹的平衡,從而簡(jiǎn)化AVL的實(shí)現(xiàn),簡(jiǎn)稱它為HAVL(Height VAL).

2 HAVL樹的性質(zhì)與操作

高度的定義1:height用來存儲(chǔ)以該節(jié)點(diǎn)為根的子樹的高度.其中高度定義為:如果樹是葉子節(jié)點(diǎn),則其高度為1,否則節(jié)點(diǎn)t的定義如下: height[t]=max(height[left],height[right])+1 (1)“高度”相對(duì)于“高度差”是一種更簡(jiǎn)單的統(tǒng)計(jì)量,因?yàn)橐粋€(gè)節(jié)點(diǎn)的高度可以僅由其左右子樹的高度求得. AVL為每個(gè)節(jié)點(diǎn)增加一個(gè)域表示其左右子樹的高度差,稱為平衡因子,該因子可由高度求出.平衡因子取值范圍是:-1,0或1,即0≤||height[right[t]]-height[left[t]]||≤1.按照左右子樹的高度的不同可分為如下兩種情況:

如果height[right[t]]-height[left[t]]≥0,有

否則height[left[t]]-height[right[t]]≥0,有

2.1 HAVL樹定義

HAVL是二叉查找樹,在每個(gè)節(jié)點(diǎn)上增加了一個(gè)域height存儲(chǔ)以該節(jié)點(diǎn)為根的子樹的高度.由定義1和公式(2)、(3),高度平衡樹中的任意節(jié)點(diǎn)t滿足兩個(gè)條件之一:

令height[left[t]]=max(height[left[left[t]]], height[left[right[t]]])+1代入公式(4),height [right[t]]=max(height[right[right[t]]],height [right[left[t]]])+1代入公式(5),可以立即得出平衡因子為1,0,-1的情況,該定義與AVL樹的定義是等價(jià)的,但是HAVL樹的實(shí)現(xiàn)不必按照平衡因子分情況討論.

2.2 HAVL樹的旋轉(zhuǎn)操作

從定義1可以看出,節(jié)點(diǎn)的高度等于左右子樹的高度取最大值加1,在旋轉(zhuǎn)操作的同時(shí)可以維持節(jié)點(diǎn)的高度信息,從而使調(diào)用該函數(shù)的上層函數(shù)不必關(guān)心該域的計(jì)算,簡(jiǎn)化了實(shí)現(xiàn)方式.

維持平衡的左旋與右旋過程:在過程HAVLRIGHT-ROTATE中,假設(shè)left[x]≠NIL;HAVL -LEFT-ROTATE中,假設(shè)right[x]≠NIL.

2.3 HAVL樹的平衡操作

過程HAVL-MAINTAIN實(shí)現(xiàn)對(duì)HAVL的子樹的平衡.AVL樹的不平衡情況有多種,都是經(jīng)過合理的調(diào)整,按照平衡因子分為不同的旋轉(zhuǎn)情況. HAVL樹給出了它的簡(jiǎn)潔定義(公式(4)、(5)),從中可以看出,HAVL-MAINTAIN邏輯上與一般的AVL平衡過程等價(jià),AVL樹的實(shí)現(xiàn)需要按照不同的平衡因子分情況旋轉(zhuǎn)并重新計(jì)算平衡因子[7],程序代碼太長(zhǎng),而HAVL由于不必關(guān)心平衡因子取值的不同情況,過程相當(dāng)簡(jiǎn)潔,實(shí)現(xiàn)簡(jiǎn)單,代碼是一般AVL樹實(shí)現(xiàn)方式的幾分之一.

HAVL-MAINTAIN(t)

(1)if height[left[t]]＜height[right[t]]-1

(2)then if height[right[left[t]]]＜height[right[right [t]]]

(3)then HAVL-RIGHT-ROTATE(right[t])

(4)HAVL-LEFT-ROTA TE(t)

(5)return

(6)if height[right[t]]＜height[left[t]]-1

(7)then if height[left[right[t]]]＜height[left[left [t]]]

(8)then HAVL-LEFT-ROTATE(left[t])

(9)HAVL-RIGHT-ROTATE(t)

(10)return

2.4 HAVL樹的插入操作

為了將一個(gè)新值v插入HAVL,可調(diào)用過程HAVL-INSERT.傳遞給該過程的參數(shù)是節(jié)點(diǎn)z,且有key[z]=v,left[z]=NIL,right[z]=NIL,height [z]=0.

HAVL-INSERT(t,z)

(1)if t=NIL then t←z return

(2)if key[z]≤key[t]

(3)then HAVL-INSERT(left[t],z)

(4)else HAVL-INSERT(right[t],z)

(5)height[t]←max(height[left[t]],height[right[t]]) +1

(6)HAVL-M AIN TAIN(t)

2.5 HAVL樹的刪除操作

過程HAVL-DELETE-MIN的功能是刪除樹中鍵值最小的節(jié)點(diǎn),并返回被刪除節(jié)點(diǎn).

HAV L-DELETE-MIN(x)

(1)if left[x]=NIL

(2)then y←x

(3)x←right[x]

(4)return y

(5)y←HAVL-DELETE-MIN(left[x])

(6)height[x]←max(height[left[x]],height[right[x]]) +1

(7)HAVL-M AIN TAIN(x)

(8)return y

過程HAVL-DELETE-ROOT的功能是刪除樹的根節(jié)點(diǎn),并返回被刪除節(jié)點(diǎn);過程HAVL-DELETE的功能是刪除樹中的鍵值為v的節(jié)點(diǎn),并返回被刪除節(jié)點(diǎn).若節(jié)點(diǎn)不存在,無操作,返回NIL.

HAV L-DELETE-ROOT(x)

(1)if height[x]=1

(2)then y←x

(3)if left[x]=NIL

(4)then x←right[x]

(5)else x←left[x]

(6)return y

(7)y←HAVL-MIN(right[x])

(8)swap(key[y],key[x])

(9)HAVL-M AIN TAIN(x)

(10)return y

HAV L-DELETE(x,v)

(1)if x=NIL then return NIL

(2)if v=key[x]

then return HAVL-DELET E-ROOT(x)

(3)if v＜key[x]

(4)then y←HAVL-DELETE(left[x],v)

(5)else y←HAVL-DELETE(right[x],v)

(6)HAVL-M AIN TAIN(x)

(7)return y

3 實(shí)驗(yàn)結(jié)果比較

實(shí)驗(yàn)設(shè)置下:分別向完全為二叉樹、AVL, HAVL,紅黑樹(RBT)樹插入2000000個(gè)隨機(jī)結(jié)點(diǎn),分別計(jì)算其運(yùn)行時(shí)間、樹的高度、深度、旋轉(zhuǎn)的次數(shù).取20次實(shí)驗(yàn)的平均值結(jié)果并與完全二叉樹進(jìn)行比較,實(shí)驗(yàn)結(jié)果見表1.

平均深度反映了樹的平衡程度,并且直接與查找性能成正比.表1中不同的平衡樹的運(yùn)行速度有明顯的差異,HAVL因?yàn)槌绦蛟O(shè)計(jì)更為緊湊,運(yùn)行時(shí)間更短比AVL樹更短,但是HAVL樹與AVL樹的平均路徑長(zhǎng)度、高度、深度和旋轉(zhuǎn)次數(shù)是一樣的,平均路徑長(zhǎng)度要好于RBT.由于RBT是不嚴(yán)格的平衡樹,所需旋轉(zhuǎn)的次數(shù)更少時(shí)間更快,少于 AVL樹,但比HAVL樹長(zhǎng).

表1 與主流平衡樹的性能比較

4 總 結(jié)

本文論述了平衡二叉查找樹附加域選擇的靈活性和由此帶來的實(shí)現(xiàn)上的簡(jiǎn)潔.這種簡(jiǎn)化能保持AVL樹的特性,并且原理描述直觀、程序?qū)崿F(xiàn)簡(jiǎn)單,運(yùn)行時(shí)間更短.

[1] Adelson-Velskii G M,Landis E M.An Algorithm for the Organization of Information[J].Soviet.Mat.Doklady,1962.

[2] Baer J L.Weight-balanced Trees[C].Proceedings of AFIPS 1975 NCC.,1975,44:467-472.

[3] Galperin,Rivest R.Scapegoat T rees[C].In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA'93),1993:165-174.

[4] Sleator D D,Tarjan R E.Self-adjusting Binary Search Trees[J].JACM,1985,32:652-686.

[5] Bent S W,Driscoll J R.Randomly Balanced Search Trees[M].Manuscript,1991.

[6] Haeupler B,Sen S,Tarjan R E.Rank-Balanced Trees [C].11th International Workshop on Algorithms and Data Structures(WADS 2009),Aug 21-23,2009 Banff Canada.Algorithms and Data Structures,2009:351-362.

[7] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社, 1997.