一、紅黑樹介紹
1、定義
- 每個結點或者為黑色或者為紅色
- 根結點為黑色
- 每個葉結點(實際上就是NULL指針)都是黑色的
- 如果一個結點是紅色的，那麼它的兩個子節點都是黑色的（也就是說，不能有兩個相鄰的紅色結點）
- 對于每個結點，從該結點到其所有子孫葉結點的路徑中所包含的黑色結點數量必須相同
2、二叉樹和AVL樹比較
1、二叉樹
- 任意節點左子樹不為空,則左子樹的值均小于根節點的值.
- 任意節點右子樹不為空,則右子樹的值均大于于根節點的值.
- 任意節點的左右子樹也分别是二叉查找樹
-
沒有鍵值相等的節點.
由二叉查找樹的性質可知，構成二叉樹的結構和插入資料的順序有關，存在不穩定性。最好情況可以建構成平衡二叉樹查找效率O(lgn)，最壞情況也有可能構造成線性樹(查找效率O(n))
紅黑樹實作原理 2、AVL樹
AVL樹是帶有平衡條件的二叉查找樹,一般是用平衡因子內插補點判斷是否平衡并通過旋轉來實作平衡。
左右子樹樹高不超過1,和紅黑樹相比,它是嚴格的平衡二叉樹,平衡條件必須滿足(所有節點的左右子樹高度差不超過1)。
AVL樹的插入 删除元素必須保持絕對的平衡，是以從插入删除元素起，要一直進行旋轉操作一直到根節點，是以
插入/删除/查找操作比較穩定，時間複雜度是O(logn)
紅黑樹實作原理 3、紅黑樹
紅黑樹也是一種平衡二叉樹，但是它與AVL樹相比是一種相對寬松的平衡，平衡因子是從任意非葉子節點到其所有葉子節點的路徑上黑色節點保持一緻(紅黑樹性質5)，是以當非葉子節點A到其一條路徑的葉子節點包含n個黑色節點，則A到其他路徑的所有節點最多隻能為2n個，以此來保證易中動态平衡。
這種平衡與AVL樹相比能減少 增加和删除節點時的時間消耗，因為紅黑樹性質保證了新增删除節點複雜度介于O(1)到O(logn)之間;
查找時，紅黑樹時間複雜度也為O(logn)，相比AVL樹的O(logn)隻是多了一點系數，相對會慢一點。
但是綜合增加、删除和查找性能看，紅黑樹還是優于AVL樹的。
二、紅黑樹實作
1、左旋、右旋
在紅黑樹中新加節點和删除節點時，如果需要調整紅黑樹時就會涉及到節點的左旋和右旋。
左旋和右旋是一組對稱的操作
1.1、左旋
左旋靜态實作
動态實作
如上圖，E-S軸指向右下方，向左旋轉E-S軸時其指向右上方
1.2、右旋
靜态實作
動态實作
E-S軸向右旋轉
2、插入節點
2.1、插入過程
1)首先找插入位置。這個和二叉樹流程一樣，從根開始周遊到葉子結點找到該插入的位置。
2) 插入值節點(紅色)
3) 确認插入值是否影響紅黑樹性質，影響就要做調整操作。
/*插入僞代碼*/
B-INSERT(T, z)
/*找待插入位置*/
y ← nil
x ← T.root
while x ≠ T.nil
do y ← x
if z.key < x.key
then x ← x.left
else x ← x.right
/*插入元素*/
z.p ← y
if y == nil[T]
then T.root ← z
else if z.key < y.key
then y.left ← z
else y.right ← z
z.left ← T.nil
z.right ← T.nil
z.color ← RED
/*調整紅黑樹*/
RB-INSERT-FIXUP(T, z)
插入節點的顔色選黑色，必定會破壞性質5(黑色節點增加)，可能需要一層一層調整紅黑樹 ,而插入顔色選紅色，則有一半幾率破壞性質4(父子節點都為紅), 而且性質4調整比5調整更加簡單，是以插入顔色選擇紅色。
2.2、插入調整
如果待插入節點的父節點為黑，則插入紅色不破壞紅黑樹性質，不需要調整，是以需要調整必然情況必然是父節點為紅色。
RB-INSERT-FIXUP(T, z)
while z.p.color == RED
do if z.p == z.p.p.left
then y ← z.p.p.right
if y.color == RED
then z.p.color ← BLACK ▹ Case 2
y.color ← BLACK ▹ Case 2
z.p.p.color ← RED ▹ Case 2
z ← z.p.p ▹ Case 2
else if z == z.p.right
then z ← z.p ▹ Case 3
LEFT-ROTATE(T, z) ▹ Case 3
z.p.color ← BLACK ▹ Case 4
z.p.p.color ← RED ▹ Case 4
RIGHT-ROTATE(T, z.p.p) ▹ Case 4
else (same as then clause with "right" and "left" exchanged)
T.root.color ← BLACK
現分以插入節點的父節點是左子樹的幾種情況(右子樹同理):
1、如果樹是空樹，則插入的是根。
調整方案: 則直接顔色塗黑(終态)。
2、父節點是紅，叔叔節點是紅。
調整方案: 則父節點和叔叔節點都塗黑，祖父節點圖紅(将紅從父輩轉嫁到祖輩)，将祖父節點設為待插入節點繼續遞推(調整為初始态)。
調整前:N為插入元素
調整後:
3、父節點是紅，叔叔節點是黑，待插入節點是右子樹。
調整方案:将目前節點的父節點作為新的目前節點，以新目前節點左旋（調整為狀态4）。
調整前:
調整後:
4、父節點是紅，叔叔節點是黑，待插入節點是左子樹。
調整方案: 将祖父節點設為紅,父節點設為黑，以祖父節點右旋，相當于把父節點這邊的多餘紅色轉移到了叔叔節點那一側，修複了紅黑樹性質(終态)。
調整前:
調整後:
3、删除節點
定義: 删除節點是D, 删除節點的父節點是P, 删除節點的叔叔節點是U, 删除節點的孩子節點是X
3.1、删除過程
1、定位删除節點并删除
- 删除節點D沒有子節點，直接删除。
- 删除的節點隻有一個子節點，則删除。
- 删除的節點有兩個子節點，則找到這個結點的後繼結點（successor），也就是它的右子樹中最小的那個結點。然後我們将這兩個節點中的資料元素互換，将後繼節點作為待删除節點删除。(後繼節點必然沒有左子樹，是以将情況轉換成2)
2、調整删除節點的父節點P和子節點X的位置
- 如果删除節點D沒有孩子節點，且他是根，則置樹為空，否則D的父節點P指向D的指針置空。
- 如果删除節點D有孩子節點X，且他是根，則将X置為根節點，否則調整父節點P的孩子指針， 由原來指向D的指針指向X
删除節點
/*确定删除節點y，如果删除節點z有左右子樹則找z的後繼節點，否則z作為待删除節點y*/
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
/*确定待删除節點y的子節點x*/
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
/*x替代待删除的y節點*/
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p[y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
/*如果y是z的後繼節點，則需要把y的資料拷貝到原待删除節點z上*/
13 if y ≠ z
14 then key[z] ← key[y]
15 copy y's satellite data into z
/*如果待删除節點y是黑色的，則需要做調整*/
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x)
18 return y
3.2、紅黑樹調整
因為删除了一個D節點，如果D節點是紅色的話，不影響紅黑樹任何性質，是以可以不做調整，但是如果D是黑色，則D這一支子樹就會少一個黑節點,影響性質5，而且P的顔色和X的顔色如果都是紅色也會影響性質4，是以需要調整。是以調整時預設D是黑色，後面假設條件不做說明。
是以我們的思路是 可以将删除的D節點的黑色标記附加在X上，把X節點叫做标記節點，顔色可以說成是紅+黑或者黑+黑，暫時保證性質5，然後我們在慢慢調整，将X上附加的顔色一層層往上推，最終調整紅黑樹保持平衡。
紅黑樹删除調整，必然是X節點為黑(額外帶了删除的黑節點，即黑+黑), 而關鍵點在于兄弟節點U和U的兩個兒子Ul,Ur的顔色情況。
case1: X是紅， 調整結束；
case2: X是(黑+黑), U是紅(由已知條件得出 Ul=Ur=黑), 則想辦法讓X的兄弟變黑，即U置黑，P置紅，P點左旋，然後Ul就變成了X的兄弟U，然後新U的兒子情況最終就隻能變成4種(黑黑，紅黑， 紅紅, 黑紅),然後衍生出了 剩下的case3、case4、case5(Ur為紅即可)
case3: X是(黑+黑)，U,Ul, Ur是黑，則将U置紅，X向上推進到P，這是能推進的情況，最終走向case1或者case5結束調整；
case4: X是(黑+黑), U是黑，Ul紅，Ur黑, 這種情況隻能演變為Ur是紅 即case5，即 U變紅，Ul變黑，然後以U右旋；
case5：X是(黑+黑), U是黑，Ul任意，Ur紅, 這種最終能走向調整結束，即把U的黑色給Ur,P的顔色給U，P再繼承X上多餘的黑色，然後以U左旋讓U代替P的位置，Ul變為P的右結點，最終達到平衡。
1 while x ≠ root[T] and color[x] = BLACK
2 do if x = left[p[x]]
3 then w ← right[p[x]]
4 if color[w] = RED
5 then color[w] ← BLACK ▹ Case 2
6 color[p[x]] ← RED ▹ Case 2
7 LEFT-ROTATE(T, p[x]) ▹ Case 2
8 w ← right[p[x]] ▹ Case 2
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ▹ Case 3
11 x ← p[x] ▹ Case 3
12 else if color[right[w]] = BLACK and color[left[w]] = RED case 4
13 then color[left[w]] ← BLACK ▹ Case 4
14 color[w] ← RED ▹ Case 4
15 RIGHT-ROTATE(T, w) ▹ Case 4
16 w ← right[p[x]] ▹ Case 4
17 color[w] ← color[p[x]] ▹ Case 5
18 color[p[x]] ← BLACK ▹ Case 5
19 color[right[w]] ← BLACK ▹ Case 5
20 LEFT-ROTATE(T, p[x]) ▹ Case 5
21 x ← root[T] ▹ Case 5
22 else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK Case1
1、如果标記節點X是紅+黑或者X是根節點。
調整: 直接将X設定成黑色，然後調整結束。
- 因為X若是紅色，則可以把标記附加色設定進來，則D子樹的黑色節點數沒變，保證了性質5，同時也避免了X和P同時為紅的情況保證了性質4。
- 因為X若是根節點，則不管X原色是啥，都必須直接置黑，同時因為已經遞推到了根，必然已經保證了性質5，是以附加的黑節點可以直接丢棄。
***後面幾種情況都是讨論X是葉子節點的情形(D無子節點) 即 X是黑色，且X不是根結點。因為D隻有一個子節點或者沒有子節點，是以由性質5知 black_num(P->D->X) = black)num(P->D->nil)，是以X必為葉子節點 ***
2、如果标記節點X是黑+黑，且叔叔節點U是紅色,叔叔節點U必有左右孩子且為黑色。
調整:将父節點P設成紅色，叔叔節點U設為黑色，然後以P為節點左旋，之後U的左孩子作為P的右孩子替代U，且U為黑色。這樣調整主要是讓U節點滿足黑色條件，然後繼續進入調整流程。
調整前:
調整後:
3、如果标記節點X是黑+黑，且叔叔節點U是黑色，叔叔節點的孩子節點全是黑色。
調整: 将叔叔節點U置成紅色，同時X上的附加黑色上移到P節點，然後以P節點作為目前節點，繼續執行調整操作。
因為将U節點置成紅色，則保證了P的左右子樹黑色總數一緻，然後以P為目前節點繼續推進，但叔叔節點U置成紅色的前提是2個孩子節點都是黑色。
調整前:（其中的X左邊的黑色為附加色）
調整後:
4、如果标記節點X是黑+黑，且叔叔節點U是黑色，叔叔節點的左孩子是紅色，右孩子是黑色。
調整: 将叔叔節點U置成紅色，U的左孩子置成黑色，然後以U為節點右旋，最終U的左孩子變成U節點且為黑色，U的右孩子為紅色。然後重新進入調整算法。
調整前:
調整後:
5、如果标記節點X是黑+黑，且叔叔節點U是黑色，右孩子是紅色色，左孩子是任意色。
調整: 将U的右子節點設定成黑色，叔叔節點U的顔色設定成父節點P的顔色，父節點P的顔色置黑(X上的附加黑色設定到P),然後以P為節點左旋。這種調整實際上将U子樹多餘的紅節點移入到X子樹，保證了性質5，最終整個紅黑樹保持平衡，到達終态。
調整前:
調整後:
參考:
1、紅黑樹(red-black tree)算法
2、教你初步了解紅黑樹
3、左右旋圖參考