基于紅黑樹的操作與檢驗

唐 松，格桑多吉，高定國

（西藏大學工學院，拉薩850000）

紅黑樹屬于自平衡二叉查找樹，是二叉2-3-4樹和對稱B-樹，是在計算機科學技術中使用的一種數據結構，其典型用途是關聯數組的實現。紅黑樹的每個節點都有顏色屬性，顏色為紅色或黑色。除了二叉查找樹的一般要求以外，對于任何有效的紅黑樹增加了如下的要求：

性質1：節點顏色為紅色或黑色。

性質2：根節點為黑色。

性質3：每個葉節點（NIL）為黑色。

性質4：每個紅色節點的兩個子節點皆為黑色(從根到每個葉子所有路徑上不能有兩個連續紅色節點)。

性質5：從任一節點到其每個葉子的所有路徑都含有相等數目的黑色節點。

這些約束規定了紅黑樹的關鍵性質:從根到葉子的最長可能路徑少于或等于最短可能路徑的兩倍長，且這棵樹大致上是平衡的。因為插入、刪除和查找某個值的操作的最壞情況，其時間都要求與樹高度成比例，這個高度的理論上限不同于普通的二叉查找樹，且允許紅黑樹在最壞情況下都是高效的。

1 優點和用途

雖然hash表查找非常迅速，但隨著數據種類變多，hash表長會變得更長且沖突也會增多，那么如何能實現數據量無論多大，查找依然高性能？一般情況下，樹是很好的一種數據結構，用于插入、查找和刪除等操作都很高效，但在很壞的情況下，操作很費時間，性能難以保證。向樹中插入時，按一定規則調整，使其達到規則，從而提高其整體與局部的查找效率。

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

2 紅黑樹的構建、操作

2.1 紅黑樹的構建

2.1.1 旋轉

圖1 旋轉

左旋：在某結點x上做左旋操作時，先假設其右孩子y不是NIL[T]，x可為樹內任意右孩子而非NIL[T]結點。左旋以x至y間的鏈為“支軸”進行，使y變為該孩子樹新的根，y的左孩子β變為pivot的右孩子。

右旋：可由左旋類推之。

樹旋轉后，保持不變的唯有原樹的搜索性質，而不能保持原樹的紅黑性質，紅黑樹的數據插入、刪除后可用旋轉和重新涂色來恢復樹的紅黑性質。

2.1.2 插入和調整

調用插入操作時，為了維護紅黑樹的五個性質，需要進行左旋、右旋相應操作，因為插入算法中將z涂為紅色可能違背紅黑性質的某一條，所以要進行相應的調整和顏色重涂，直至滿足紅黑樹的全部性質。

2.2 紅黑樹的操作

2.2.1 結點的插入

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

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

圖2 結點的插入情況1

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

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

對于情況2（z是它父親的右孩子），為了維持紅黑樹性質，左旋變成情況3，此時z為左孩子，因z、p[z]皆為黑色，故不違背紅黑樹性質（注：情況3中，z的叔叔y為黑色，否則此種情況就變為情況1）。

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

圖3 結點的插入情況2

對以上三種情況，首先將待插入結點涂成紅色，接著按照二叉樹的方式進行插入操作，因此元素的搜索性質不會改變。為了保證紅黑樹性質在插入后依然保持，上面代碼調用了一個調整的輔助程序，對結點進行重新涂色并旋轉。若插入的結點是根結點，會破壞性質2，若插入結點的父結點為紅色，則性質4會被破壞。總而言之，插入一個紅色結點只會破壞性質2或性質4。

(a)結點z為紅色。

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

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

2.2.2 結點的刪除

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

2)若待刪除結點在紅黑樹中，則刪除分為四種情形，相應的操作如圖4。

圖4 結點的刪除

注：若待刪除結點y有左孩子，那么x是y的左孩子，否則為右孩子。

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

情況2：x的兄弟w為黑色，且w的兩個孩子都為黑色。因為w也為黑色，所以x和w中必須去掉一個黑色，經顏色重涂，w變為紅色。p[x]為新結點new x，賦給x，即操作x＜-p[x]。

情況3：x的兄弟w為黑色，w的左孩子為紅色，w的右孩子為黑色。將w和其左孩子left[w]的顏色都改變（即它們的顏色交換——上圖的D、C顏色互換），并對w進行右旋操作，從而保持了紅黑樹性質。現在x的新兄弟new w是有紅色右孩子的黑結點，從而把情況3轉變為情況4.

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

若從被刪除結點的顏色分析，可以得到：

結論1：若被刪除的結點為紅色,則結點被刪除后,紅黑樹性質仍保持,原因如下:

(a)樹中各結點的黑高都沒變。

(b)不存在兩個相鄰紅色結點。

(c)因為若該節點為紅色,就不可能為根,所以根仍然為黑色。

結論2：若被刪除的結點為黑色，則會產生三個問題。（待刪除結點是y，若y有一個不是NIL的孩子，則x是y的唯一孩子；若y沒有孩子，則x為NIL，賦y的父節點值給x的父節點(原來是y)。）

(a)若y原來為根，而y的一個紅色孩子變為新的根，這就違背了性質2。

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

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

3 紅黑樹的檢驗

利用中序遍歷函數，將構建或是操作（插入、刪除）后經過調整的紅黑樹輸出，能直觀地看出構建或是操作（插入、刪除）后經過調整的紅黑樹的正確與否，若輸出的數列是升序，那么正確（調整后結點顏色的正確性基于算法的正確性），反之錯誤，因為樹的中序遍歷按照結點進行升序排列。

4 流程圖和運行結果

流程圖和運行結果如圖5和圖6所示。

圖5 流程圖

5 小結

紅黑樹為樹的構建、插入、查找和刪除操作的時間提供了最佳可能的最壞情況保證，這不僅使它們在對時間敏感的應用如實時應用中有價值，而且使它們在最壞情況擔保的其他數據結構中擁有作為建造板塊的價值，如計算幾何中使用的很多數據結構皆可基于紅黑樹。在函數式編程中，紅黑樹也特別有用，它們是最常用的持久數據結構之一，用來構造集合和關聯數組，且在突變之后仍能保持以前的版本。除了O(log n)的時間，紅黑樹持久版本對每次的插入或刪除都要O(log n)的空間。

圖6 運行結果

因此，深入研究紅黑樹的算法，在理解的基礎上實現，并用中序遍歷輸出這種簡易且可靠的方法檢驗，對紅黑樹的應用方面有很重要的參考價值。

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

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

[3]嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，2001.