紅黑樹 C++實現

高度為h的二叉查找樹在進行插入刪除等操作時，時間都是O(h),當樹的高度較低的時候，有著很好的執行速度。但是當樹的高度較高的時候，這些操作的效率可能並沒預想的好。紅黑樹是一種保證在最壞情況下，操作時間為O(lgn)的一種接近平衡的二叉搜索樹，並不像AVL樹那樣，是嚴格的高度平衡的。

[cpp]

1. //A binary search tree is a red-black tree if it satisfies the following red-black properties:   
2. //  Every node is either red or black.   
3. //  The root is black.   
4. //  Every leaf (NIL) is black.   
5. //  If a node is red, then both its children are black.   
6. //  For each node, all paths from the node to descendant leaves contain the same number of black nodes.  

上面是紅黑樹的五個基本性質，只要滿足了上面五個性質的二叉排序樹就是紅黑樹。上面第四個性質有的書上面也轉化為，紅黑樹中從根到葉子節點的任何一條路徑上，不可以出現連續的兩個紅色結點。這個性質在維護紅黑樹的過程中是很重要的。

紅黑樹的基本操作和二叉排序樹的可以說是一樣的，也是搜索，插入，刪除。

搜索沒什麼好說的，和二叉排序樹的搜索是一樣的。

在說插入之前，先說下旋轉操作，由於在維護紅黑樹的五個性質的保持的過程中，需要改變相關結點之間的父子或者是兄弟關系等，這些操作就用旋轉來實現，其實就是通過改變指針的指向來實現，和AVL樹一樣，有兩種基本的旋轉，左旋和右旋，如下圖所示的一樣

在插入操作中，先和二叉排序樹一樣，先找到可以插入的位置，然後插好後，先將該結點塗為紅色，然後再對插入後的新的紅黑樹進行結構的檢測，看看該樹是否依舊滿足紅黑樹的五個性質。

在將一個紅色結點插入紅黑樹之後，會破壞它的那些性質呢？那就是第二個和第四個啦，就是根必須為黑色和紅色結點不可以有紅色子樹這兩個性質。至於為什麼大家可以自己想下。

下面先貼出插入算法的偽代碼，然後再大概地分析一下，偽代碼是算法導論上的

[cpp]

1. RB-INSERT(T, z)  
2.  1  y ← nil[T]  
3.  2  x ← root[T]  
4.  3  while x ≠ nil[T]  
5.  4      do y ← x  
6.  5         if key[z] < key[x]  
7.  6            then x ← left[x]  
8.  7            else x ← right[x]  
9.  8  p[z] ← y  
10.  9  if y = nil[T]  
11. 10     then root[T] ← z  
12. 11     else if key[z] < key[y]  
13. 12             then left[y] ← z  
14. 13             else right[y] ← z  
15. 14  left[z] ← nil[T]  
16. 15  right[z] ← nil[T]  
17. 16  color[z] ← RED  
18. 17  RB-INSERT-FIXUP(T, z)  

[cpp]

1. RB-INSERT-FIXUP(T, z)  
2.  1 while color[p[z]] = RED  
3.  2     do if p[z] = left[p[p[z]]]  
4.  3           then y ← right[p[p[z]]]  
5.  4                if color[y] = RED  
6.  5                   then color[p[z]] ← BLACK                    ▹ Case 1  
7.  6                        color[y] ← BLACK                       ▹ Case 1  
8.  7                        color[p[p[z]]] ← RED                   ▹ Case 1  
9.  8                        z ← p[p[z]]                            ▹ Case 1  
10.  9                   else if z = right[p[z]]  
11. 10                           then z ← p[z]                       ▹ Case 2  
12. 11                                LEFT-ROTATE(T, z)              ▹ Case 2  
13. 12                           color[p[z]] ← BLACK                 ▹ Case 3  
14. 13                           color[p[p[z]]] ← RED                ▹ Case 3  
15. 14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3  
16. 15           else (same as then clause  
17.                          with "right" and "left" exchanged)  
18. 16 color[root[T]] ← BLACK  

其中插入的主調函數RB_INSERT是在二叉查找樹的基礎上進行修改的，只是將判斷指針是否為空的改為是否指向哨兵結點，以及在最後的部分將插入結點的顏色設置為紅色，然後就調用插入輔助函數 RB_INSERT_FIXUP 來調整紅黑樹的結構。在這個調整函數中，有三種情況，其中case2和case3不是互斥的，case2是在case3之內的。這點在看偽代碼的時候如果不熟悉它的語法結構，只是形式上的照打代碼，那就會出錯了，當然如果在理解整個調整過程的前提下，那麼也會知道那裡是不會互斥的。

前面說了，把一個紅結點插進去，只會破壞紅黑樹的第二和第四條性質，就是樹根可能會被變為紅色，還有紅黑樹的某個紅色內結點的子樹中會有紅子樹，上面的這個輔助函數就是來維護這兩個性質的，其中在第16行，將根結點的顏色設置為黑色，保證了第一條性質的成立，所以函數上面的while循環就是用來維護紅黑樹的第四條性質的。

分了6種情況，其中三種是對稱的，偽代碼中沒有給出，在寫代碼的時候只需要把左子樹改為右子樹，左旋改為右旋就可以了。

分別是以下的三種情況以及解決方法：

在上面的圖片中已經演示得很清楚，對應的每種情況是怎樣的解決方法。想更加詳細了解的同學可以看看算法導論，或者自己看著這幾種情況對照代碼畫一下圖，就會理解的。

利用一個數組元素來構建一棵紅黑樹的過程也就是從一棵空樹一步一步插入最後得到一棵樹。