基于紅黑樹的操作與檢驗(yàn)

唐 松，格桑多吉，高定國(guó)

（西藏大學(xué)工學(xué)院，拉薩850000）

紅黑樹屬于自平衡二叉查找樹，是二叉2-3-4樹和對(duì)稱B-樹，是在計(jì)算機(jī)科學(xué)技術(shù)中使用的一種數(shù)據(jù)結(jié)構(gòu)，其典型用途是關(guān)聯(lián)數(shù)組的實(shí)現(xiàn)。紅黑樹的每個(gè)節(jié)點(diǎn)都有顏色屬性，顏色為紅色或黑色。除了二叉查找樹的一般要求以外，對(duì)于任何有效的紅黑樹增加了如下的要求：

性質(zhì)1：節(jié)點(diǎn)顏色為紅色或黑色。

性質(zhì)2：根節(jié)點(diǎn)為黑色。

性質(zhì)3：每個(gè)葉節(jié)點(diǎn)（NIL）為黑色。

性質(zhì)4：每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)皆為黑色(從根到每個(gè)葉子所有路徑上不能有兩個(gè)連續(xù)紅色節(jié)點(diǎn))。

性質(zhì)5：從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都含有相等數(shù)目的黑色節(jié)點(diǎn)。

這些約束規(guī)定了紅黑樹的關(guān)鍵性質(zhì):從根到葉子的最長(zhǎng)可能路徑少于或等于最短可能路徑的兩倍長(zhǎng)，且這棵樹大致上是平衡的。因?yàn)椴迦?、刪除和查找某個(gè)值的操作的最壞情況，其時(shí)間都要求與樹高度成比例，這個(gè)高度的理論上限不同于普通的二叉查找樹，且允許紅黑樹在最壞情況下都是高效的。

1 優(yōu)點(diǎn)和用途

雖然hash表查找非常迅速，但隨著數(shù)據(jù)種類變多，hash表長(zhǎng)會(huì)變得更長(zhǎng)且沖突也會(huì)增多，那么如何能實(shí)現(xiàn)數(shù)據(jù)量無(wú)論多大，查找依然高性能？一般情況下，樹是很好的一種數(shù)據(jù)結(jié)構(gòu)，用于插入、查找和刪除等操作都很高效，但在很壞的情況下，操作很費(fèi)時(shí)間，性能難以保證。向樹中插入時(shí)，按一定規(guī)則調(diào)整，使其達(dá)到規(guī)則，從而提高其整體與局部的查找效率。

紅黑樹復(fù)雜，但其操作有良好的最壞情況運(yùn)行時(shí)間，且在實(shí)踐中高效：可以在O(log n)時(shí)間內(nèi)插入、查找和刪除（log n中的n是樹中元素的數(shù)目）。它的統(tǒng)計(jì)性能優(yōu)于平衡二叉樹(AVL-樹)，所以紅黑樹應(yīng)用很廣，如字典的實(shí)現(xiàn)、關(guān)聯(lián)數(shù)組上，且內(nèi)存使用率較高。在C++STL中，不少部分(目前包括set、multiset、map、multimap)應(yīng)用了紅黑樹的變體(SGI STL中的紅黑樹的修改提供了更好的性能、對(duì)set操作的支持)。

2 紅黑樹的構(gòu)建、操作

2.1 紅黑樹的構(gòu)建

2.1.1 旋轉(zhuǎn)

圖1 旋轉(zhuǎn)

左旋：在某結(jié)點(diǎn)x上做左旋操作時(shí)，先假設(shè)其右孩子y不是NIL[T]，x可為樹內(nèi)任意右孩子而非NIL[T]結(jié)點(diǎn)。左旋以x至y間的鏈為“支軸”進(jìn)行，使y變?yōu)樵摵⒆訕湫碌母瑈的左孩子β變?yōu)閜ivot的右孩子。

右旋：可由左旋類推之。

樹旋轉(zhuǎn)后，保持不變的唯有原樹的搜索性質(zhì)，而不能保持原樹的紅黑性質(zhì)，紅黑樹的數(shù)據(jù)插入、刪除后可用旋轉(zhuǎn)和重新涂色來(lái)恢復(fù)樹的紅黑性質(zhì)。

2.1.2 插入和調(diào)整

調(diào)用插入操作時(shí)，為了維護(hù)紅黑樹的五個(gè)性質(zhì)，需要進(jìn)行左旋、右旋相應(yīng)操作，因?yàn)椴迦胨惴ㄖ袑涂為紅色可能違背紅黑性質(zhì)的某一條，所以要進(jìn)行相應(yīng)的調(diào)整和顏色重涂，直至滿足紅黑樹的全部性質(zhì)。

2.2 紅黑樹的操作

2.2.1 結(jié)點(diǎn)的插入

插入分為下面兩類情況，相應(yīng)的流程圖如圖2和圖3。

1）情況1（如圖2）：z的叔叔y為紅色。(a)情況，即z是右孩子,因p[p[z]（]c）為黑色，所以將p[z]、y都涂成黑色，這就解決了z、p[z]皆為紅色的問(wèn)題，將p[p[z]]涂為紅色，則維持了性質(zhì)5。(b)情況同理分析。

圖2 結(jié)點(diǎn)的插入情況1

2）插入情況2（如圖3）：z的叔叔y為黑色，且z為右孩子。

插入情況3（如圖3）：z的叔叔y為黑色，且z為左孩子。

對(duì)于情況2（z是它父親的右孩子），為了維持紅黑樹性質(zhì)，左旋變成情況3，此時(shí)z為左孩子，因z、p[z]皆為黑色，故不違背紅黑樹性質(zhì)（注：情況3中，z的叔叔y為黑色，否則此種情況就變?yōu)榍闆r1）。

情況2、情況3都違背性質(zhì)4（一個(gè)紅結(jié)點(diǎn)的兩個(gè)兒子都為黑色）。因此，情況2-＞左旋后-＞情況3，這時(shí)情況3同樣違背性質(zhì)4，所以情況3-＞右旋，同時(shí)B變成黑色，C變成紅色，得到圖3的最后那一部分。（注：情況2、3都只違背性質(zhì)4，不違背其他性質(zhì)。）

圖3 結(jié)點(diǎn)的插入情況2

對(duì)以上三種情況，首先將待插入結(jié)點(diǎn)涂成紅色，接著按照二叉樹的方式進(jìn)行插入操作，因此元素的搜索性質(zhì)不會(huì)改變。為了保證紅黑樹性質(zhì)在插入后依然保持，上面代碼調(diào)用了一個(gè)調(diào)整的輔助程序，對(duì)結(jié)點(diǎn)進(jìn)行重新涂色并旋轉(zhuǎn)。若插入的結(jié)點(diǎn)是根結(jié)點(diǎn)，會(huì)破壞性質(zhì)2，若插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色，則性質(zhì)4會(huì)被破壞?？偠灾迦胍粋€(gè)紅色結(jié)點(diǎn)只會(huì)破壞性質(zhì)2或性質(zhì)4。

(a)結(jié)點(diǎn)z為紅色。

(b)若p[z]是根，則p[z]為黑色。

(c)若有紅黑樹的性質(zhì)被破壞，則最多有一個(gè)被破壞，不是性質(zhì)2就是性質(zhì)4。若違反性質(zhì)2，則發(fā)生原因是z為根且為紅色。若違反性質(zhì)4，則原因?yàn)閦和p[z]皆為紅色，p[p[z]]必然為黑色。

2.2.2 結(jié)點(diǎn)的刪除

1)若待刪除結(jié)點(diǎn)不在紅黑樹中，則輸出“not found!”提示。

2)若待刪除結(jié)點(diǎn)在紅黑樹中，則刪除分為四種情形，相應(yīng)的操作如圖4。

圖4 結(jié)點(diǎn)的刪除

注：若待刪除結(jié)點(diǎn)y有左孩子，那么x是y的左孩子，否則為右孩子。

情況1：x的兄弟w為紅色。同時(shí)改變w、p[z]的顏色，對(duì)p[x]左旋一次，保持了紅黑樹全部性質(zhì)。x的新兄弟new w為旋轉(zhuǎn)之前w的左孩子，且為黑色。所以，情況1轉(zhuǎn)變成情況2或3、4。

情況2：x的兄弟w為黑色，且w的兩個(gè)孩子都為黑色。因?yàn)閣也為黑色，所以x和w中必須去掉一個(gè)黑色，經(jīng)顏色重涂，w變?yōu)榧t色。p[x]為新結(jié)點(diǎn)new x，賦給x，即操作x＜-p[x]。

情況3：x的兄弟w為黑色，w的左孩子為紅色，w的右孩子為黑色。將w和其左孩子left[w]的顏色都改變（即它們的顏色交換——上圖的D、C顏色互換），并對(duì)w進(jìn)行右旋操作，從而保持了紅黑樹性質(zhì)?，F(xiàn)在x的新兄弟new w是有紅色右孩子的黑結(jié)點(diǎn)，從而把情況3轉(zhuǎn)變?yōu)榍闆r4.

情況4：x的兄弟w為黑色，且w的右孩子為紅色。改變w顏色，并旋轉(zhuǎn)p[x]一次，可以去掉x的額外的黑色，變x為單一黑色，這些并沒(méi)有破壞紅黑樹性質(zhì)。將x置為根（new x=root[T]），結(jié)束程序循環(huán)。

若從被刪除結(jié)點(diǎn)的顏色分析，可以得到：

結(jié)論1：若被刪除的結(jié)點(diǎn)為紅色,則結(jié)點(diǎn)被刪除后,紅黑樹性質(zhì)仍保持,原因如下:

(a)樹中各結(jié)點(diǎn)的黑高都沒(méi)變。

(b)不存在兩個(gè)相鄰紅色結(jié)點(diǎn)。

(c)因?yàn)槿粼摴?jié)點(diǎn)為紅色,就不可能為根,所以根仍然為黑色。

結(jié)論2：若被刪除的結(jié)點(diǎn)為黑色，則會(huì)產(chǎn)生三個(gè)問(wèn)題。（待刪除結(jié)點(diǎn)是y，若y有一個(gè)不是NIL的孩子，則x是y的唯一孩子；若y沒(méi)有孩子，則x為NIL，賦y的父節(jié)點(diǎn)值給x的父節(jié)點(diǎn)(原來(lái)是y)。）

(a)若y原來(lái)為根，而y的一個(gè)紅色孩子變?yōu)樾碌母?，這就違背了性質(zhì)2。

(b)若x和p[y](現(xiàn)在也為p[x])都為紅色，就違背了性質(zhì)4。

(c)刪除y將導(dǎo)致之前包含y的任何路徑上黑結(jié)點(diǎn)個(gè)數(shù)少1。因此，y的一個(gè)祖先破壞了性質(zhì)5，應(yīng)對(duì)的一個(gè)方法是將x視為還有另外的一重黑色，即是說(shuō)，若將任意包含x的路徑上的黑結(jié)點(diǎn)個(gè)數(shù)加1，則此假設(shè)下性質(zhì)5成立。當(dāng)刪除黑節(jié)點(diǎn)y時(shí)，將其黑色“下推”至y的子節(jié)點(diǎn)?，F(xiàn)在就有這樣的問(wèn)題，x可能既不是紅，也不是黑，違背了性質(zhì)1。x為雙重黑色或紅黑，這就分別給包含x的路徑上黑結(jié)點(diǎn)的個(gè)數(shù)貢獻(xiàn)2個(gè)或1個(gè)。x的顏色屬性仍為紅(若x是紅黑的)或者黑(若x為雙重黑色)。換言之，一個(gè)結(jié)點(diǎn)額外的黑色體現(xiàn)在x指向它，而不是它的顏色屬性。

3 紅黑樹的檢驗(yàn)

利用中序遍歷函數(shù)，將構(gòu)建或是操作（插入、刪除）后經(jīng)過(guò)調(diào)整的紅黑樹輸出，能直觀地看出構(gòu)建或是操作（插入、刪除）后經(jīng)過(guò)調(diào)整的紅黑樹的正確與否，若輸出的數(shù)列是升序，那么正確（調(diào)整后結(jié)點(diǎn)顏色的正確性基于算法的正確性），反之錯(cuò)誤，因?yàn)闃涞闹行虮闅v按照結(jié)點(diǎn)進(jìn)行升序排列。

4 流程圖和運(yùn)行結(jié)果

流程圖和運(yùn)行結(jié)果如圖5和圖6所示。

圖5 流程圖

5 小結(jié)

紅黑樹為樹的構(gòu)建、插入、查找和刪除操作的時(shí)間提供了最佳可能的最壞情況保證，這不僅使它們?cè)趯?duì)時(shí)間敏感的應(yīng)用如實(shí)時(shí)應(yīng)用中有價(jià)值，而且使它們?cè)谧顗那闆r擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中擁有作為建造板塊的價(jià)值，如計(jì)算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)皆可基于紅黑樹。在函數(shù)式編程中，紅黑樹也特別有用，它們是最常用的持久數(shù)據(jù)結(jié)構(gòu)之一，用來(lái)構(gòu)造集合和關(guān)聯(lián)數(shù)組，且在突變之后仍能保持以前的版本。除了O(log n)的時(shí)間，紅黑樹持久版本對(duì)每次的插入或刪除都要O(log n)的空間。

圖6 運(yùn)行結(jié)果

因此，深入研究紅黑樹的算法，在理解的基礎(chǔ)上實(shí)現(xiàn)，并用中序遍歷輸出這種簡(jiǎn)易且可靠的方法檢驗(yàn)，對(duì)紅黑樹的應(yīng)用方面有很重要的參考價(jià)值。

[1]THOMAS H C,LEISERSON C E.Introduction to algorithms[M].北京:機(jī)械工業(yè)出版社,2006.

[2]Kenneth A·Reek.C和指針 POINTERS ON C[M].北京：人民郵電出版社，2008.

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