紅黑樹屬于特殊的二叉搜尋樹，通過對任一條從根結點到葉子結點簡單路徑上的各個結點進行顔色限制，確定了沒有一條路徑會比其他路徑長出兩倍，是*乎*衡的。
- 有以下性質：
- 每個結點或是紅色，或是黑色；
- 根結點是黑色的；
- 每個葉結點是黑色的；
- 如果一個結點是紅色的，則其兩個子結點都是黑色的；
- 對于每個結點x，從該結點到其所有後代葉結點的簡單路徑上，均包含了相同數量的黑色結點（即 黑高，記為 bh(x) 相同 ）。
紅黑樹大量應用在底層資料結構中，主要用于存儲和查找。*日開發雖然很少自己去寫紅黑樹，但是深入了解資料結構和算法是非常必要的。
那紅黑樹都有哪些操作都是如何實作的……請看下文。
樹中每個結點均包含5個屬性：color、key、left、right、p
紅黑樹的插入、删除需要不斷的維護上述5個性質……如何實作？兩種操作：旋轉（左旋、右旋）、變色（在插入、删除中實作）；
旋轉操作
1、左旋：
1 LEFT-ROTATE(T, x)
2 y = x.right
3 x.right = y.left
4 if y.left != T.nil then
5 y.left.p = x
6 y.p = x.p
7 if x.p == T.nil then
8 T.root = y
9 else if x == x.p.left then
10 x.p.left = y
11 else
12 x.p.right = y
13 y.left = x
14 x.p = y 2、右旋：
1 RIGHT-ROTATE(T, y)
2 x = y.left
3 y.left = x.right
4 if x.right != T.nil then
5 x.right.p = y
6 x.p = y.p
7 if y.p == T.nil then
8 T.root = x
9 else if y == y.p.left then
10 y.p.left = x
11 else
y.p.right = x
12 x.right = y
13 y.p = x 插入操作
與普通二叉搜尋樹差異不大，唯二的差別是：需要維護紅黑樹的5個性質，插入的結點的初始顔色是紅色的（如果插入結點是黑色的，則将違反性質5）。
1、插入
1 RB-INSERT(T, x)
2 y = T.nil
3 z = T.root
4 while z != T.nil do
5 y = z
6 if x.key > y.key then
7 z = z.right
8 else
9 z = z.left
10 x.p = y
11 if y == T.nil then
12 T.root = x
13 else if y.key > x.key then
14 y.left = x
15 else
16 y.right = x
17 x.left = T.nil
18 x.right = T.nil
19 x.color = RED //插入點是紅色的
20 RB-INSERT-FIXUP(T, x) //維護紅黑樹性質 2、維護
插入結點為x，若x.p.color == BLACK，則完事大吉，不需要做任何處理；否則将違反性質4，故需要旋轉跳躍我閉着眼~
那如何旋轉、如何變色，将需要視情況而定：
情形一：結點x的父節點為左孩子且結點x為左孩子且結點x的叔結點為黑色（或不存在，指向黑色哨兵結點T.nil）。此時僅需①x.p.color = BLACK; x.p.p.color = RED + ②對x.p.p進行右旋操作
情形二：結點x的父節點為左孩子且結點x為右孩子且結點x的叔結點為黑色（或不存在，指向黑色哨兵T.nil）。此類情況經過一定的操作是可以轉換為情形一的。此時僅需①令x=x.p（為的是後續能複用情形一的代碼） + ②對x進行左旋 + ③對x.p與x.p.p變色 + ④對x.p.p進行右旋操作
情形三：結點x的父結點為右孩子且結點x為右孩子且結點x的叔結點為黑色（或不存在，指向哨兵結點T.nil）。此時僅需令①x.p.color = BLACK; x.p.p.color = RED + ②對x.p.p進行左旋
情形四：結點x的父結點為左孩子且結點x為左孩子且結點x的叔結點為黑色（或不存在，指向哨兵結點T.nil）。此時僅需①令x=x.p（為的是後續能複用情形三的代碼）+ ②對x進行右旋 + ③對x.p與x.p.p換色 + ④對x.p.p進行左旋
情形五：結點x的叔結點為紅色。此類情況僅需給結點變色即可，①x.p.color = x.p.p.right.color = BLACK; ②x.p.p.color = RED
具體操作如下：
1 RB-INSERT-FIXUP(T, x)
2 while x.p.color == RED do //違反了性質4（x.color亦為RED）
3 if x.p == x.p.p.left then
4 y = x.p.p.right //結點x的叔結點
5 if y.color == BLACK then
6 if x == x.p.right then //情形二
7 x = x.p
8 LEFT-ROTATE(T, x)
9 x.p.color = BLACK //情形一
10 x.p.p.color = RED
11 RIGHT-ROTATE(T, x.p.p)
12 else //y.color == RED //情形五
13 x.p.color = BLACK
14 y.color = BLACK
15 x.p.p.color = RED
16 x = x.p.p
17
18 else //x.p == x.p.p.right
19 y = x.p.p.left //結點x的叔結點
20 if y.color == BLACK then
21 if x == x.p.left then //情形四
22 x = x.p
23 RIGHT-ROTATE(T, x)
24 x.p.color = BLACK //情形三
25 x.p.p.color = RED
26 LEFT-ROTATE(T, x.p.p)
27 else //y.color == RED //情形五
28 x.p.color = BLACK
29 y.color = BLACK
30 x.p.p.color = RED
31 x = x.p.p
32 //while循環外部
33 T.root.color = BLACK 最值操作
擷取以結點x為根的子樹的值最大/最小的結點
1 //最小值結點
2 TREE-MINIMUM(x)
3 while x.left != T.nil do
4 x = x.left
5 return x
6
7
8 //最大值結點
9 TREE-MAXIMUM(x)
10 while x.right != T.nil do
11 x = x.right
12 return x 前驅&後繼操作
擷取以結點x為根結點的子樹的前驅結點與後繼結點
1 //後繼結點
2 TREE-SUCCESSOR(x)
3 if x.right != T.nil then
4 return TREE-MINIMUM(x)
5 y = x.p
6 while y != T.nil and x == y.right do
7 x = y
8 y = y.p
9 return y
10
11
12 //前驅結點
13 TREE-PRECESSOR(x)
14 if x.left != T.nil then
15 return TREE-MAXIMUM(x)
16 y = x.p
17 while y != T.nil and x == y.left do
18 x = y
19 y = y.p
20 return y 删除操作
同樣與普通二叉搜尋樹删除結點類似。
1、删除
删除結點x也需要技巧……如何維持搜尋二叉樹的正确性，也需要視情況而定：
情形一：即将删除的結點x無左子樹，此時僅需用結點x的右子樹補上即。注意：在删除結點x前需要：
- 緩存x的顔色，記為ori-color；//原因該結點即将被移除，如果是黑色的話，将導緻經過該結點的黑高減1，但另外一邊不變導緻，即破壞了紅黑樹的性質5
- 記錄替補結點y，y = x.right；//原因是如果真的破壞了紅黑樹的性質，将從替補結點y開始不斷修複顔色。（為什麼不将y.color變為x的原始顔色後，再修複？原因其一該情形僅判斷沒有左子樹，那可能也不存在右子樹，右孩子x.right直接指向哨兵結點T.nil，哨兵結點T.nil無法改變屬性~ ）故y永遠指向即将在樹内移動且不能變色的結點。
情形二：即将删除的結點x無右子樹，此時僅需用結點x的左子樹補上即可。注意：在删除結點x前需要 ：
- 緩存x的顔色，記為ori-color；//原因如情形一所述一緻
- 記錄替補結點y; //原因如情形一所述類似
情形三：即将删除的結點x擁有左右子樹，此時操作相對複雜，在删除結點x前需要：
- 找到x的後繼結點y；//擁有左右子樹的結點要删除的話，那肯定是找前驅或者後繼結點補上的……
- 記錄y的替補結點w = y.right；//記錄y.right，因為y的位置将有y.right頂替。為什麼是y.right ? ? y是結點x的後繼結點，那y肯定沒有左子樹…是以y的位置将有y.right（不管是否為T.nil）替補…
- 緩存y的顔色，記為ori-color；//y的位置将由w頂替，w不能變色（像情形一二所述，w可能為T.nil），故需要标記y的原始顔色，後續需要修複時也有依據
- 移植w到y的位置；
- 令y成為結點x右子樹根結點，移植y到結點x的位置；//結點y上任
- y.color = x.color；//y.color的顔色變為x.color。為甚？首先y肯定存在且不為T.nil（可改變顔色）；可減少變化量，即使移動破壞了紅黑樹的性質，那也隻需要從結點w開始修複即可…
- y = w；//純粹是想與情形一二保持一緻，y永遠指向在樹内移動又不能變色的結點~~
最後 if ori-color == BLACK then 肯定破壞了紅黑樹的性質，需要維護；為何ori-color為紅色的不需要？原因：（先假設ori-color的原始結點為A）1、A的黑高沒有改變；2、A肯定不是根結點，根節點還是黑色。沒有任何影響~
具體操作
1 TREE-TRANSPLANT(T, D, N)
2 //将結點N移植到結點D位置
3 if D.p == T.nil then
4 T.root = N
5 else if D == D.p.left then
6 D.p.left = N
7 else
8 D.p.right = N
9 N.p = D.p
10
11
12 //删除結點x
13 RB-DELETE(T, x)
14 ori-color = x.color //标記即将被移除的結點x的顔色，如果該結點為黑色，那麼移除後可能會引起黑高不一緻
15 if x.left == T.nil then
16 //情形一
17 y = x.right
18 TREE-TRANSPLANT(T, x, y)
19 else if x.right == T.nil then
20 //情形二
21 y = x.left
22 TREE-TRANSPLANT(T, x, y)
23 else
24 //情形三
25 y = TREE-MINIMUM(x.right)
26 ori-color = y.color
27 w = y.right //w即将被移動到結點y的位置，需要标記，目的是解決ori-color為黑色時，移動w到y的位置導緻的黑高不一緻問題
28 if y.p != x then
29 //将結點y更新為結點x右子樹的根結點。
30 TREE-TRANSPLANT(T, y, y.right)
31 y.right = x.right
32 y.right.p = y
33 TREE-TRANSPLANT(T, x, y)
34 y.left = x.left
35 y.left.p = y
36 y.color = x.color
37 y = w
38 if ori-color == BLACK then
39 //ori-color 為黑色，可能破壞了紅黑樹性質，需要調整維護；
40 RB-DELETE-FIXUP(T, y) 僅發生在ori-color為黑色的條件下。
既然移動結點y的操作破壞了紅黑樹的性質，那肯定需要從結點y開始不斷修複；如何操作，也同樣需要不同情況不同操作…
y：被移動的結點；w：結點y的兄弟結點（y.p肯定存在左右子樹，否則原樹将違反性質5）
情形一：y.color == RED。此時需：
- 令y.color = BLACK；//因為已知y.p的左子樹或者右子樹，比另一邊少了一個黑色結點，是以直接變色即可
情形二：y為左孩子，y的顔色為黑色，w的顔色為紅色。此時需：
- 令w.color = BLACK，y.p.color = RED；
- 對x.p進行左旋操作；
- 令w重新指向y的兄弟；
- 繼續判斷w的情況；
情形三：y為左孩子，y與w同為黑色，且w的左右孩子顔色亦為黑色。此時需：
- 改變w的顔色為紅色；
- 将y重定向為y的父結點；
- 開啟新一輪修複；
情形四：y為左孩子，y與w同為黑色，且w的右孩子為紅色。此時要：
- 改變w的顔色為y父結點顔色、w右孩子變成黑色、再将y父結點顔色變為黑色；
- 對y父結點進行左旋操作；
- 令y指向T.root（退出循環）
情形五：y為左孩子，y與w同為黑色，w的右孩子為黑色，w的左孩子為紅色。此時要：
- 改變w左孩子的顔色為黑色；
- 對w進行右旋；
- 令w重新指向y的兄弟結點；此時就可以用情形四的方法處理了
情形六：y為右孩子，y的顔色為黑色，w的顔色為紅色；此時要：
- 改變w的顔色為黑色，改變y.p的顔色為紅色；
- 對y.p進行右旋……
情形七：y為右孩子，y與w同為黑色，w的左右孩子均為黑色。此時要：
- 令y重定向為y.p；
- 重新檢測…
情形八：y為右孩子，y與w同為黑色，w的左孩子為紅色。此時要：
- 令w的顔色為y的父結點顔色，令w的左孩子為黑色，令y父結點為黑色；
- 對y父結點進行右旋操作；
情形九：y為右孩子，y與w同為黑色，w的左孩子為黑色，w的右孩子為紅色。此時要：
- 改變w的顔色為紅色，改變w右孩子為黑色；
- 對w進行左旋操作；
- 令w重新指向y的兄弟結點；
- 變為了情況八…
1 RB-DELETE-FIXUP(T, y)
2 while y != T.root and y.color == BLACK do
3 if y = y.p.left then
4 w = y.p.right
5 if w.color == RED then //情形二
6 y.p.color = RED
7 w.color = BLACK
8 LEFT-ROTATE(T, y.p)
9 w = y.p.right
10 if w.left.color == BLACK and w.right.color == BLACK then
11 //情形三
12 w.color = RED
13 y = y.p
14 else
15 if w.right.color == BLACK then
16 //情形四
17 //此時w.left.color必定為紅色，因為條件…
18 w.color = RED
19 w.left.color = BLACK
20 RIGHT-ROTATE(T, w)
21 w = y.p.right
22 //情形五
23 w.color = y.p.color
24 y.p.color = BLACK
25 w.right.color = BLACK
26 LEFT-ROTATE(T, y.p)
27 y = T.root
28 else // y == y.p.right
29 w = y.p.left
30 if w.color == RED then //情形六
31 w.color = BLACK
32 y.p.color = RED
33 RIGHT-ROTATE(T, y.p)
34 w = y.p.left
35 if w.right.color == BLACK and w.left.color == BLACK then
36 //情形七
37 w.color == RED
38 y = y.p
39 else
40 if w.left.color == BLACK then //情形八
41 //此時w.right.color肯定為紅色，條件限制…
42 w.color = RED
43 w.right.color = BLACK
44 LEFT-ROTATE(T, w)
45 w = y.p.left
46 //情形九
47 w.color = y.p.color
48 y.p.color = BLACK
49 w.left.color = BLACK
50 RIGHT-ROTATE(T, y.p)
51 y = T.root
52 //退出while循環…
53 y.color = BLACK //情形一…