紅黑樹是平衡樹的一種，保證最壞情況下操作時間複雜度為O(lgo(n))。紅黑樹的應用比較廣泛，比如作為C++中STL的set和map的底層資料結構，Java集合中TreeSet和TreeMap的底層資料結構等。學習紅黑樹，可以把二叉查找樹作為參考，這樣有助于加深了解。紅黑樹的操作主要包括節點旋轉、插入、删除等操作，下面咱們就一一來看：
1、紅黑樹性質
- 每個節點是紅色的，或者是黑色的
- 根節點是黑色的
- 每個葉節點(nil)是黑色的
- 如果一個節點是紅色的，則它的兩個子節點都是黑色的
- 對每個節點，從該節點到其後代葉節點的簡單路徑上，均包含相同數目的黑色節點
紅黑樹整體節點圖示如下：
2、旋轉
旋轉是保持二叉搜尋樹（紅黑樹）局部性質的操作，包括左旋和右旋。當在節點x上做左旋時，假設它的右孩子為y而不是T.nil，X可為其右孩子不是T.nil的任何節點，同理，X做右旋也是一樣的。
僞代碼如下(左旋)
左旋Java示例代碼：
/**
* 左旋操作
*/
private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != nil) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == nil) {
root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
x.parent = y;
y.left = x;
} 3、插入
在O(log(n))時間内插入一個節點，RB-INSERT過程完成該操作，像一個普通的二叉搜尋樹插入操作一樣，然後将要插入的節點Z着為紅色。為了保持紅黑樹的性質，調用一個輔助函數RB-INSERT-FIXUP來對節點重新着色并旋轉。待插入節點Z已儲存了資料項。
RB-INSERT-FIXUP過程僞代碼
注意：Case1屬于if判斷條件，Case2和Case3屬于else語句，Case2是else語句中的if判斷語句的。具體可以看代碼。
插入過程Java代碼示例：
/**
* 往紅黑樹中插入一個元素
* @param data
*/
public void insert(int data) {
Node y = nil;
Node x = root;
if (root == nil) {
root = newNode(data);
root.color = Node.BLACK;
} else {
while (x != nil) {
if (data < x.data) {
y = x;
x = x.left;
} else if (data > x.data) {
y = x;
x = x.right;
} else {
return;
}
}
Node z = newNode(data);
z.parent = y;
if (data < y.data) {
y.left = z;
} else {
y.right = z;
}
if (y.color == Node.RED) {
insertFixup(z);
}
}
} RB-INSERT-FIXUP過程分析
第1-15行的while循環在每次疊代的開始始終保持以下3個條件是不變的
- 節點z是紅節點
- 如果z.p是根節點，則z.p是黑節點
- 如果有任何紅黑樹性質貝破壞，則至多有一條被破壞，或是性質2，或是性質4(各個性質見紅黑樹性質總結)。如果性質2被破壞，則因為z是根節點且是紅節點。性質4被破壞則是因為z和z.p都是紅節點。
循環終止條件：
循環終止因為z.p是黑色的(如果z是根節點，則z.p是黑色哨兵節點)，這樣，在循環終止時并沒有違反性質4，唯一可能不成立的就是性質2，不過第16行(僞代碼中的行)恢複了這個性質。
循環保持條件：
循環保持有6中條件，其中3種和另外3種是對稱的，這取決于z的父節點z.p是z的祖父節點z.p.p的左孩子還是右孩子。情況1、2、3的差別就在于z 的父節點的兄弟節點(z的叔節點)的顔色不同，加入y指向z的叔節點，如果y的顔色是紅色的，則執行情況1，否則轉向情況2和3。在所有的3種情況中，z 的祖父節點z.p.p是黑色的，因為他的父節點z.p是紅色的，故性質4隻有在z和z.p之間被破壞了。
情況1：z的叔節點y是紅色的
此時對應Case1，将z.p和y都着成黑色，解決z和z.p都是紅色的問題，将z.p.p着成紅色保持性質5，然後把z.p.p作為新節點z來繼續進行while循環，指針z上移兩層
情況2：z的叔節點y是黑色的且z是一個右孩子
情況3：z的叔節點y是黑色的且z是一個左孩子
兩種情況中，y都是黑色的，通過z是左孩子還是右孩子來區分，情況2中可以通過一個左旋來轉化為情況3，此時z為左孩子。因為z和z.p都是紅節點，對黑 高(從某個節點出發，不含該節點，到達一個葉節點的任意一條簡答路徑上的黑色節點數為該節點的黑高)和性質5都無影響。在情況3中，改變某些節點顔色并做 一次右旋，保持性質5，這樣不在有兩個紅色節點相鄰，處理完畢，此時z.p是黑色的，是以無需再執行while循環了。
RB-INSERT-FIXUP的Java代碼實作
/**
* 插入節點後不滿足紅黑樹條件時來修複
* @param z 待插入的節點
*/
private void insertFixup(Node z) {
// y為z節點的叔叔節點
Node y = null;
while (z.parent.color == Node.RED) {
if (z.parent == z.parent.parent.left) {
y = z.parent.parent.right;
if (y.color == Node.RED) {
z.parent.color = Node.BLACK;
y.color = Node.BLACK;
z.parent.parent.color = Node.RED;
z = z.parent.parent;
} else {
if (z == z.parent.right) {
z = z.parent;
leftRotate(z);
}
z.parent.color = Node.BLACK;
z.parent.parent.color = Node.RED;
rightRotate(z.parent.parent);
}
} else {
y = z.parent.parent.left;
if (y.color == Node.RED) {
z.parent.color = Node.BLACK;
y.color = Node.BLACK;
z.parent.parent.color = Node.RED;
z = z.parent.parent;
} else {
if (z == z.parent.left) {
z = z.parent;
rightRotate(z);
}
z.parent.color = Node.BLACK;
z.parent.parent.color = Node.RED;
leftRotate(z.parent.parent);
}
}
}
root.color = Node.BLACK;
} 4、删除
删除操作與插入操作相比，略顯複雜，與插入操作一樣，也要花費O(log(n))時間。從紅黑樹中删除節點，需設計一個供TREE-DELETE調用的子過程TRANSPLANT，并應用到紅黑樹中，TRANSPLANT過程用來調整兩個節點的關系，其中的一個節點要替換掉另一個節點
TRANSPLANT過程
u節點表示将要被替換掉的節點，v節點是準備替換u節點的
RB-TRANSPLANT的Java代碼實作
/**
* 兩個節點的替換，newNode替換oldNode
* @param oldNode
* @param newNode
*/
private void transplant(Node oldNode, Node newNode) {
if (oldNode.parent == nil) {
root = newNode;
} else if (oldNode == oldNode.parent.left) {
oldNode.parent.left = newNode;
} else {
oldNode.parent.right = newNode;
}
newNode.parent = oldNode.parent;
} RB-DELETE過程
RB-DELETE中，z節點是要被删除的節點，其中記錄了節點y的蹤迹，y有可能導緻紅黑樹性質破壞，當想删除節點z，且z的子節點少于2個時，z從書中删除，并讓y稱為z。當z有兩個子節點時，y應該是z的後繼，并且将y移到z的位置。在節點被删除或者移動時，必須記住y的顔色，并且記錄節點x的蹤迹，将x移到y的原來的位置，因為節點x可能引起紅黑樹性質破壞。删除節點z後，RB-DELETE-FIXUP過程通過改變顔色和執行旋轉來恢複紅黑樹性質。
我們儲存節點x的蹤迹，使它移至節點y的原來位置。第4、7和11行的指派語句令x或指向y的唯一子節點或指向y哨兵T.nil(y沒有子節點的話)。 第5、8或14行調用RB-TRANSPLANT時，傳遞的第2個參數與x相同
如果y是黑色的，則有可能引入一個或多個破壞紅黑色的情況，是以在第22行調用RB-TRANSPLANT來恢複紅黑樹性質。如果y是紅色的，當y被删除或移動時，紅黑樹性質依然成立，因為(1) 樹中黑高沒有變化 (2) 不存在兩個相鄰的紅節點，因為y在樹中占據了z的位置，z的位置肯定不會違反紅黑樹性質的。另外，如果y是z的右孩子，則y的原右孩子x代替y，如果y是紅色的，則x一定是黑色的，一次用x替代y不會使兩個紅節點相鄰。 (3) 如果y是紅色的，就不會是根節點，是以根節點仍然是黑色的。
y為黑節點情況分析
RB-DELETE的Java代碼實作
/**
* 從紅黑樹中移除一個元素
* @param data 待移除的元素
*/
public void remove(int data) {
Node z = contains(data);
if (z == null) {
return;
}
Node x;
Node y = z;
int yOldColor = y.color;
if (z.left == nil) {
x = z.right;
transplant(z, x);
} else if (z.right == nil) {
x = z.left;
transplant(z, x);
} else {
y = z.right;
while (y.left != nil) {
y = y.left;
}
yOldColor = y.color;
x = y.right;
if (y.parent == z) {
x.parent = y;
} else {
transplant(y, y.right);
y.right = z.right;
y.right.right = y;
}
transplant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if (yOldColor == Node.BLACK) {
removeFixup(x);
}
} RB-DELETE-FIXUP過程
ps：圖檔上的情況層次關系對應不是很齊，可以看碼來的清楚
4種情況的轉換關系
- 1 -> 2、3、4
- 2 -> 1、2、3、4、修複 (隻有Case2是節點上移，所有有可能會使x=root)
- 3 -> 4
- 4 -> 修複
無論哪個Case，要麼是為了到達平衡兩個節點，路徑上黑色數目相同的目的，要麼是通過變形間接達到這個目的。
while循環的目标是将額外的黑色沿樹上移，直到：
- x指向紅黑節點，此時在第23行處将x着為(單個)黑色
- x指向根節點，此時可以簡單地移除額外的黑色
- 執行适當的旋轉和重新着色
代碼中的4種情況圖示
上圖給出了代碼中出現的四種情況，再具體研究每一個情況時，先看看如何證明每種情況中的變換保證性質5。關鍵思想是在每種情況下，從子樹的跟(包括跟)到每棵子樹之間的黑色節點個數(包括x的額外黑色)并不被變換改變，是以，如果性質5在變換之前成立，則在變換之後也成立。比如：在情況1中，在變換前後，根節點到子樹a或b之間的黑色節點數是3(因為x增加了一層黑色)，類似的，在變換前後根節點到其餘的4個子樹的葉節點中的任何一個的黑節點數是2。在圖13-7(b)中，計數是還要包括所示子樹的根節點的color屬性的值，它是RED或是BLACK，如果定義count(RED)=0以及count(BLACK)=1，那麼變換前後根節點至a的黑節點都為2+count(c)。在此情況下，變換之後新節點x具有color屬性的c，但是這個節點的顔色是紅黑(如果c=RED)或者雙重黑色的(如果c=BLACK)。其他情況可以類似加以驗證。
情況1：x的兄弟節點w是紅色的
情況1(見RB-DELETE-FIXUP的第5-8行和圖13-7(a))發生在節點x的兄弟節點w為紅色時。因為w必須有黑色子節點，所有可以改變w的x.p的顔色，然後對x.p做一次左旋而不違反紅黑樹的任何性質。現在x的新兄弟節點是旋轉之前w的某個子節點，其顔色為黑色。這樣，就将情況1轉變為了情況2、3或者4。
當節點w為黑色時，屬于情況2、3或者4；這些情況有w的子節點顔色來區分了。
情況2：x的兄弟節點w是黑色的，而且w的兩個子節點都是黑色的
在情況2(見RB-DELETE-FIXUP的第10-11行和圖13-7(b))，w的兩個子節點都是黑色的，因為w也是黑色的，是以從x和w上去掉一重黑色，使得x隻有一重黑色而w為紅色。為了補償從x和w中去掉的一重黑色，在原來是紅色或黑色的x.p上增加一重額外的黑色。通過将x.p作為新節點x來重複while循環。注意到，如果通過情況1進入到情況2，則新節點x就是紅黑色的，因為原來的x.p是紅色的，是以，新節點x的color屬性值為RED，并且在測試循環條件後循環終止。然後，在第23行處将新節點x着為(單一)黑色。
情況3：x的兄弟節點w是黑色的，w的左孩子是紅色的，w的右孩子是黑色的
情況3(見RB-DELETE-FIXUP的第13-16行和圖13-7(c))發生在w為黑色且其左孩子為紅色，右孩子為黑色時。可以交換w和其左孩子w.left的顔色，然後對w進行右旋而不違反紅黑樹的性質。現在x的新節點w是一個有紅色右孩子的黑色節點，這樣我們就從情況3轉換成了情況4。
情況4：x的兄弟節點w是黑色的，且w的右孩子是紅色的
情況4(見RB-DELETE-FIXUP的第17-21行和圖13-7(d))發生在節點x的兄弟節點w為黑色且w的右孩子為紅色時，通過進行某些顔色修改并對x.p做一次左旋，可以去掉x的額外黑色，進而使它變為單重黑色，而且不破壞紅黑樹性質。将x設為設為根root後，當while循環測試其循環條件時，循環終止。
RB-DELETE-FIXUP的Java代碼實作
/**
* 移除一個元素後紅黑樹不符合要求時的修複方法
* @param x
*/
private void removeFixup(Node x) {
Node y;
while (x != root && x.color == Node.BLACK) {
if (x == x.parent.left) {
y = x.parent.right;
if (y.color == Node.RED) { //情況1：x的兄弟節點w是紅色
y.color = Node.BLACK;
x.parent.color = Node.RED;
leftRotate(x.parent);
y = x.parent.right;
}
if (y.left.color == Node.BLACK && y.right.color == Node.BLACK) { //情況2:x的兄弟節點w是黑色，而且w的兩個子節點都是黑色的
y.color = Node.RED;
x = x.parent;
} else {
if (y.right.color == Node.BLACK) { //情況3：x的兄弟節點w是黑色的，w的左孩子是紅色的，w的右孩子是黑色的
y.left.color = Node.BLACK;
y.color = Node.RED;
rightRotate(y);
y = x.parent.right;
}
y.color = x.parent.color; //情況4：x的兄弟節點w是黑色的，且w的右孩子是紅色的
x.parent.color = Node.BLACK;
y.right.color = Node.BLACK;
leftRotate(x.parent);
x = root;
}
} else {
y = x.parent.left;
if (y.color == Node.RED) {
y.color = Node.BLACK;
x.parent.color = Node.RED;
rightRotate(x.parent);
y = x.parent.left;
}
if (y.left.color == Node.BLACK && y.right.color == Node.BLACK) {
y.color = Node.RED;
x = x.parent;
} else {
if (y.left.color == Node.BLACK) {
y.right.color = Node.BLACK;
y.color = Node.RED;
leftRotate(y);
y = x.parent.left;
}
y.color = x.parent.color;
x.parent.color = Node.BLACK;
y.left.color = Node.BLACK;
rightRotate(x.parent);
x = root;
}
}
}
x.color = Node.BLACK;
} 删除分析：
5、完整程式Java代碼實作
紅黑樹Rbtre.java檔案：
1 package tree;
2
3 /**
4 * 紅黑樹節點類
5 */
6 class Node {
7 // 紅黑節點顔色
8 public final static int RED = 0;
9 public final static int BLACK = 1;
10
11 // ------------------------------ Instance Variables
12
13 public Node left; // 左節點
14 public Node right; // 右節點
15 public Node parent; // 父節點
16 public int color; // 節點顔色
17 public int data; // 資料域，int型資料
18 }
19
20 /**
21 * 紅黑樹類
22 *
23 */
24 public class Rbtree {
25
26 // ------------------------------ Instance Variables
27
28 // 紅黑樹空節點
29 public Node nil;
30
31 // 紅黑樹根節點
32 public Node root;
33
34 // ------------------------------ Constructors
35
36 /**
37 * Init nil node and root node.
38 */
39 public Rbtree() {
40 nil = new Node();
41 nil.left = nil.right = nil.parent = nil;
42 nil.color = Node.BLACK;
43 root = nil;
44 }
45
46 // ------------------------------ Public methods
47
48 /**
49 * 往紅黑樹中插入一個元素
50 * @param data
51 */
52 public void insert(int data) {
53 Node y = nil;
54 Node x = root;
55
56 if (root == nil) {
57 root = newNode(data);
58 root.color = Node.BLACK;
59 } else {
60 while (x != nil) {
61 if (data < x.data) {
62 y = x;
63 x = x.left;
64 } else if (data > x.data) {
65 y = x;
66 x = x.right;
67 } else {
68 return;
69 }
70 }
71
72 Node z = newNode(data);
73 z.parent = y;
74 if (data < y.data) {
75 y.left = z;
76 } else {
77 y.right = z;
78 }
79 if (y.color == Node.RED) {
80 insertFixup(z);
81 }
82 }
83 }
84
85 /**
86 * 從紅黑樹中移除一個元素
87 * @param data 待移除的元素
88 */
89 public void remove(int data) {
90 Node z = contains(data);
91 if (z == null) {
92 return;
93 }
94
95 Node x;
96 Node y = z;
97 int yOldColor = y.color;
98 if (z.left == nil) {
99 x = z.right;
100 transplant(z, x);
101 } else if (z.right == nil) {
102 x = z.left;
103 transplant(z, x);
104 } else {
105 y = z.right;
106 while (y.left != nil) {
107 y = y.left;
108 }
109 yOldColor = y.color;
110 x = y.right;
111
112 if (y.parent == z) {
113 x.parent = y;
114 } else {
115 transplant(y, y.right);
116 y.right = z.right;
117 y.right.right = y;
118 }
119
120 transplant(z, y);
121 y.left = z.left;
122 y.left.parent = y;
123 y.color = z.color;
124 }
125
126 if (yOldColor == Node.BLACK) {
127 removeFixup(x);
128 }
129 }
130
131 /**
132 * 紅黑樹中是否包含data
133 * @param data
134 * @return
135 */
136 public Node contains(int data) {
137 Node node = root;
138
139 while (node != null) {
140 if (data < node.data) {
141 node = node.left;
142 } else if (data > node.data) {
143 node = node.right;
144 } else {
145 return node;
146 }
147 }
148 return null;
149 }
150
151 @Override
152 public String toString() {
153 StringBuilder buf = new StringBuilder();
154
155 if (root != nil) {
156 toStringInternal(root, buf);
157 }
158 return buf.toString();
159 }
160
161 // ------------------------------ Private methods
162
163 /**
164 * New a initialize node, default node's color is RED
165 */
166 private Node newNode(int data) {
167 Node node = new Node();
168
169 node.data = data;
170 node.color = Node.RED;
171 node.left = node.right = node.parent = nil;
172 return node;
173 }
174
175 private void toStringInternal(Node node, StringBuilder buf) {
176 if (node != nil) {
177 toStringInternal(node.left, buf);
178 buf.append(node.data + (node.color == Node.RED ? "-red " : "-black "));
179 toStringInternal(node.right, buf);
180 }
181 }
182
183 /**
184 * 兩個節點的替換，newNode替換oldNode
185 * @param oldNode
186 * @param newNode
187 */
188 private void transplant(Node oldNode, Node newNode) {
189 if (oldNode.parent == nil) {
190 root = newNode;
191 } else if (oldNode == oldNode.parent.left) {
192 oldNode.parent.left = newNode;
193 } else {
194 oldNode.parent.right = newNode;
195 }
196
197 newNode.parent = oldNode.parent;
198 }
199
200 /**
201 * 左旋操作
202 */
203 private void leftRotate(Node x) {
204 Node y = x.right;
205
206 x.right = y.left;
207 if (y.left != nil) {
208 y.left.parent = x;
209 }
210 y.parent = x.parent;
211 if (x.parent == nil) {
212 root = y;
213 } else if (x == x.parent.left) {
214 x.parent.left = y;
215 } else {
216 x.parent.right = y;
217 }
218
219 x.parent = y;
220 y.left = x;
221 }
222
223 /**
224 * 右旋操作
225 */
226 private void rightRotate(Node x) {
227 Node y = x.left;
228
229 x.left = y.right;
230 if (y.right != nil) {
231 y.right.parent = x;
232 }
233 y.parent = x.parent;
234 if (x.parent == nil) {
235 root = y;
236 } else if (x == x.parent.left) {
237 x.parent.left = y;
238 } else {
239 x.parent.right = y;
240 }
241
242 x.parent = y.parent;
243 y.right = x;
244 }
245
246 /**
247 * 插入節點後不滿足紅黑樹條件時來修複
248 * @param z 待插入的節點
249 */
250 private void insertFixup(Node z) {
251 // y為z節點的叔叔節點
252 Node y = null;
253
254 while (z.parent.color == Node.RED) {
255 if (z.parent == z.parent.parent.left) {
256 y = z.parent.parent.right;
257 if (y.color == Node.RED) { // Case1: x uncle node y is red
258 z.parent.color = Node.BLACK;
259 y.color = Node.BLACK;
260 z.parent.parent.color = Node.RED;
261 } else {
262 if (z == z.parent.right) { // Case2: x uncle node y is black, but x is right node
263 z = z.parent;
264 leftRotate(z);
265 }
266
267 z.parent.color = Node.BLACK; // Case3: x uncle node y is black, but x is left node
268 z.parent.parent.color = Node.RED;
269 rightRotate(z.parent.parent);
270 }
271 } else {
272 y = z.parent.parent.left;
273 if (y.color == Node.RED) {
274 z.parent.color = Node.BLACK;
275 y.color = Node.BLACK;
276 z.parent.parent.color = Node.RED;
277 } else {
278 if (z == z.parent.left) {
279 z = z.parent;
280 rightRotate(z);
281 }
282
283 z.parent.color = Node.BLACK;
284 z.parent.parent.color = Node.RED;
285 leftRotate(z.parent.parent);
286 }
287 }
288 }
289
290 root.color = Node.BLACK;
291 }
292
293 /**
294 * 移除一個元素後紅黑樹不符合要求時的修複方法
295 * @param x
296 */
297 private void removeFixup(Node x) {
298 Node y;
299
300 while (x != root && x.color == Node.BLACK) {
301 if (x == x.parent.left) {
302 y = x.parent.right;
303 if (y.color == Node.RED) { //情況1：x的兄弟節點w是紅色
304 y.color = Node.BLACK;
305 x.parent.color = Node.RED;
306 leftRotate(x.parent);
307 y = x.parent.right;
308 }
309
310 if (y.left.color == Node.BLACK && y.right.color == Node.BLACK) { //情況2:x的兄弟節點w是黑色，而且w的兩個子節點都是黑色的
311 y.color = Node.RED;
312 x = x.parent;
313 } else {
314 if (y.right.color == Node.BLACK) { //情況3：x的兄弟節點w是黑色的，w的左孩子是紅色的，w的右孩子是黑色的
315 y.left.color = Node.BLACK;
316 y.color = Node.RED;
317 rightRotate(y);
318 y = x.parent.right;
319 }
320
321 y.color = x.parent.color; //情況4：x的兄弟節點w是黑色的，且w的右孩子是紅色的
322 x.parent.color = Node.BLACK;
323 y.right.color = Node.BLACK;
324 leftRotate(x.parent);
325 x = root;
326 }
327 } else {
328 y = x.parent.left;
329 if (y.color == Node.RED) {
330 y.color = Node.BLACK;
331 x.parent.color = Node.RED;
332 rightRotate(x.parent);
333 y = x.parent.left;
334 }
335
336 if (y.left.color == Node.BLACK && y.right.color == Node.BLACK) {
337 y.color = Node.RED;
338 x = x.parent;
339 } else {
340 if (y.left.color == Node.BLACK) {
341 y.right.color = Node.BLACK;
342 y.color = Node.RED;
343 leftRotate(y);
344 y = x.parent.left;
345 }
346
347 y.color = x.parent.color;
348 x.parent.color = Node.BLACK;
349 y.left.color = Node.BLACK;
350 rightRotate(x.parent);
351 x = root;
352 }
353 }
354 }
355 x.color = Node.BLACK;
356 }
357 } View Code
測試用例程式Main.java檔案
1 package tree;
2
3 public class Main {
4 public static void main(String[] args) {
5 Rbtree tree = new Rbtree();
6
7 tree.insert(12);
8 tree.insert(12);
9 tree.insert(2);
10 tree.insert(23);
11 tree.insert(1);
12
13 System.out.println(tree);
14
15 tree.remove(1);
16 tree.remove(2);
17 tree.remove(12);
18 tree.remove(12);
19 tree.remove(23);
20 System.out.println(tree);
21 }
22 } 參考資料：
1、《算法導論》第13章 紅黑樹
2、紅黑樹了解 - 資料結構
3、更多資料結構實作代碼（C++版）