【理论】红黑树的实现原理
紅黑樹
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。
紅黑樹是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。
紅黑樹是一種特化的AVL樹（平衡二叉樹），都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。
它雖然是復雜的，但它的最壞情況運行時間也是非常良好的，并且在實踐中是高效的： 它可以在O(log n)時間內做查找，插入和刪除，這里的n 是樹中元素的數目。
介紹
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。若一棵二叉查找樹是紅黑樹，則它的任一子樹必為紅黑樹.
紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于 1，所以紅黑樹不是嚴格意義上的平衡二叉樹（AVL），但 對之進行平衡的代價較低， 其平均統計性能要強于 AVL 。
由于每一顆紅黑樹都是一顆二叉排序樹，因此，在對紅黑樹進行查找時，可以采用運用于普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息。
特性
紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹增加了如下的額外要求:
- 性質1. 節點是紅色或黑色。
- 性質2. 根節點是黑色。
- 性質3. 所有葉子都是黑色。（葉子是NUIL節點）
- 性質4. 每個紅色節點的兩個子節點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）
- 性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
是性質4導致路徑上不能有兩個連續的紅色節點確保了這個結果。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。
因為紅黑樹是一種特化的二叉查找樹，所以紅黑樹上的只讀操行與普通二叉查找樹相同。
紅黑樹基本操作
紅黑樹的基本操作是添加、刪除。在對紅黑樹進行添加或刪除之后，都會用到旋轉方法。為什么呢？道理很簡單，添加或刪除紅黑樹中的結點之后，紅黑樹的結構就發生了變化，可能不滿足紅黑樹的5條性質，也就不再是一顆紅黑樹了，而是一顆普通的樹。而通過旋轉和變色，可以使這顆樹重新成為紅黑樹。簡單點說，旋轉和變色的目的是讓樹保持紅黑樹的特性：自平衡二叉樹。
旋轉包括兩種：左旋 和 右旋。下面分別對它們進行介紹：
- 左旋：以某個結點作為支點(旋轉結點)，其右子結點變為旋轉結點的父結點，右子結點的左子結點變為旋轉結點的右子結點，其左子結點保持不變。如圖2。
- 右旋：以某個結點作為支點(旋轉結點)，其左子結點變為旋轉結點的父結點，左子結點的右子結點變為旋轉結點的左子結點，其右子結點保持不變。如圖3。
變色：結點的顏色由紅變黑或由黑變紅。
左旋
左旋的偽代碼《算法導論》
右旋
右旋的偽代碼《算法導論》
RIGHT-ROTATE(T, y) x ← left[y] // 前提：這里假設y的左孩子為x。下面開始正式操作left[y] ← right[x] // 將 “x的右孩子” 設為 “y的左孩子”，即 將β設為y的左孩子p[right[x]] ← y // 將 “y” 設為 “x的右孩子的父親”，即 將β的父親設為yp[x] ← p[y] // 將 “y的父親” 設為 “x的父親”if p[y] = nil[T] then root[T] ← x // 情況1：如果 “y的父親” 是空節點，則將x設為根節點else if y = right[p[y]] then right[p[y]] ← x // 情況2：如果 y是它父節點的右孩子，則將x設為“y的父節點的左孩子”else left[p[y]] ← x // 情況3：(y是它父節點的左孩子) 將x設為“y的父節點的左孩子”right[x] ← y // 將 “y” 設為 “x的右孩子”p[y] ← x // 將 “y的父節點” 設為 “x”區分 左旋 和 右旋
仔細觀察上面"左旋"和"右旋"的示意圖。我們能清晰的發現，它們是對稱的。無論是左旋還是右旋，被旋轉的樹，在旋轉前是二叉查找樹，并且旋轉之后仍然是一顆二叉查找樹。
左旋示例圖(以x為節點進行左旋)：
zx / / \ --(左旋)--> xy z /y 對x進行左旋，意味著，將“x的右孩子”設為“x的父親節點”； 即，將 x變成了一個左節點(x成了為z的左孩子)！。 因此，左旋中的“左”，意味著“被旋轉的節點將變成一個左節點”。右旋示例圖(以x為節點進行右旋)：
yx \ / \ --(右旋)--> xy z \z 對x進行右旋，意味著，將“x的左孩子”設為“x的父親節點”； 即，將 x變成了一個右節點(x成了為y的右孩子)！ 因此，右旋中的“右”，意味著“被旋轉的節點將變成一個右節點”。插入操作
將一個節點插入到紅黑樹中，需要執行哪些步驟呢？首先，將紅黑樹當作一顆二叉查找樹，將節點插入；然后，將節點著色為紅色；最后，通過旋轉和重新著色等方法來修正該樹，使之重新成為一顆紅黑樹
將插入的節點著色為"紅色" — 將插入的節點著色為紅色，不會違背"特性(5)"！少違背一條特性，就意味著我們需要處理的情況越少。
將插入節點著色為"紅色"之后，不會違背"特性(5)"。那它到底會違背哪些特性呢？
- 對于"特性(1)"，顯然不會違背了。因為我們已經將它涂成紅色了。
- 對于"特性(2)"，顯然也不會違背。在第一步中，我們是將紅黑樹當作二叉查找樹，然后執行的插入操作。而根據二叉查找數的特點，插入操作不會改變根節點。所以，根節點仍然是黑色。
- 對于"特性(3)"，顯然不會違背了。這里的葉子節點是指的空葉子節點，插入非空節點并不會對它們造成影響。
- 對于"特性(4)"，是有可能違背的！
那接下來，想辦法使之"滿足特性(4)"，就可以將樹重新構造成紅黑樹了。
添加操作的偽代碼《算法導論》
RB-INSERT(T, z) y ← nil[T] // 新建節點“y”，將y設為空節點。x ← root[T] // 設“紅黑樹T”的根節點為“x”while x ≠ nil[T] // 找出要插入的節點“z”在二叉樹T中的位置“y”do y ← x if key[z] < key[x] then x ← left[x] else x ← right[x] p[z] ← y // 設置 “z的父親” 為 “y”if y = nil[T] then root[T] ← z // 情況1：若y是空節點，則將z設為根else if key[z] < key[y] then left[y] ← z // 情況2：若“z所包含的值” < “y所包含的值”，則將z設為“y的左孩子”else right[y] ← z // 情況3：(“z所包含的值” >= “y所包含的值”)將z設為“y的右孩子” left[z] ← nil[T] // z的左孩子設為空right[z] ← nil[T] // z的右孩子設為空。至此，已經完成將“節點z插入到二叉樹”中了。color[z] ← RED // 將z著色為“紅色”RB-INSERT-FIXUP(T, z) // 通過RB-INSERT-FIXUP對紅黑樹的節點進行顏色修改以及旋轉，讓樹T仍然是一顆紅黑樹RB-INSERT-FIXUP(T, z)while color[p[z]] = RED // 若“當前節點(z)的父節點是紅色”，則進行以下處理。do if p[z] = left[p[p[z]]] // 若“z的父節點”是“z的祖父節點的左孩子”，則進行以下處理。then y ← right[p[p[z]]] // 將y設置為“z的叔叔節點(z的祖父節點的右孩子)”if color[y] = RED // Case 1條件：叔叔是紅色then color[p[z]] ← BLACK ? Case 1 // (01) 將“父節點”設為黑色。color[y] ← BLACK ? Case 1 // (02) 將“叔叔節點”設為黑色。color[p[p[z]]] ← RED ? Case 1 // (03) 將“祖父節點”設為“紅色”。z ← p[p[z]] ? Case 1 // (04) 將“祖父節點”設為“當前節點”(紅色節點)else if z = right[p[z]] // Case 2條件：叔叔是黑色，且當前節點是右孩子then z ← p[z] ? Case 2 // (01) 將“父節點”作為“新的當前節點”。LEFT-ROTATE(T, z) ? Case 2 // (02) 以“新的當前節點”為支點進行左旋。color[p[z]] ← BLACK ? Case 3 // Case 3條件：叔叔是黑色，且當前節點是左孩子。(01) 將“父節點”設為“黑色”。color[p[p[z]]] ← RED ? Case 3 // (02) 將“祖父節點”設為“紅色”。RIGHT-ROTATE(T, p[p[z]]) ? Case 3 // (03) 以“祖父節點”為支點進行右旋。else (same as then clause with "right" and "left" exchanged) // 若“z的父節點”是“z的祖父節點的右孩子”，將上面的操作中“right”和“left”交換位置，然后依次執行。color[root[T]] ← BLACK根據被插入節點的父節點的情況，可以將"當節點z被著色為紅色節點，并插入二叉樹"劃分為三種情況來處理。
被插入的節點是根節點。
- 處理方法：把插入結點作為根結點，并把結點設置為黑色。
被插入的節點的父節點是黑色。
- 處理方法：什么也不需要做。節點被插入后，仍然是紅黑樹。
被插入的節點的父節點是紅色。
- 處理方法：
- 該情況與紅黑樹的“特性(5)”相沖突。這種情況下，被插入節點是一定存在非空祖父節點的；
- 進一步的講，被插入節點也一定存在叔叔節點(即使叔叔節點為空，我們也視之為存在，空節點本身就是黑色節點)。
- 理解這點之后，我們依據"叔叔節點的情況"，將這種情況進一步劃分為3種情況。
叔叔結點存在并且為紅結點
現象說明：當前節點(即，被插入節點)的父節點是紅色，且當前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。
處理策略：
- 將“父節點”設為黑色。
- 將“叔叔節點”設為黑色。
- 將“祖父節點”設為“紅色”。
- 將“祖父節點”設為“當前節點”(紅色節點)；即，之后繼續對“當前節點”進行操作。
為什么要這樣處理：
- “當前節點”和“父節點”都是紅色，違背“特性(4)”。所以，將“父節點”設置“黑色”以解決這個問題。
- 但是，將“父節點”由“紅色”變成“黑色”之后，違背了“特性(5)”：因為，包含“父節點”的分支的黑色節點的總數增加了1。
- 解決這個問題的辦法是：將“祖父節點”由“黑色”變成紅色，同時，將“叔叔節點”由“紅色”變成“黑色”。關于這里，說明幾點：
- 第一，為什么“祖父節點”之前是黑色？這個應該很容易想明白，因為在變換操作之前，該樹是紅黑樹，“父節點”是紅色，那么“祖父節點”一定是黑色。
- 第二，為什么將“祖父節點”由“黑色”變成紅色，同時，將“叔叔節點”由“紅色”變成“黑色”；能解決“包含‘父節點’的分支的黑色節點的總數增加了1”的問題。這個道理也很簡單。“包含‘父節點’的分支的黑色節點的總數增加了1”同時也意味著“包含‘祖父節點’的分支的黑色節點的總數增加了1”，既然這樣，我們通過將“祖父節點”由“黑色”變成“紅色”以解決“包含‘祖父節點’的分支的黑色節點的總數增加了1”的問題；但是，這樣處理之后又會引起另一個問題“包含‘叔叔’節點的分支的黑色節點的總數減少了1”，現在我們已知“叔叔節點”是“紅色”，將“叔叔節點”設為“黑色”就能解決這個問題。所以，將“祖父節點”由“黑色”變成紅色，同時，將“叔叔節點”由“紅色”變成“黑色”；就解決了該問題。
按照上面的步驟處理之后：當前節點、父節點、叔叔節點之間都不會違背紅黑樹特性，但祖父節點卻不一定。若此時，祖父節點是根節點，直接將祖父節點設為“黑色”，那就完全解決這個問題了；若祖父節點不是根節點，那我們需要將“祖父節點”設為“新的當前節點”，接著對“新的當前節點”進行分析。
叔叔結點為黑，插入結點是其父結點的右子結點
現象說明：當前節點(即，被插入節點)的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的右孩子
處理策略
- 將“父節點”作為“新的當前節點”。
- 以“新的當前節點”為支點進行左旋。
為什么要這樣處理：
- 首先，將“父節點”作為“新的當前節點”；接著，以“新的當前節點”為支點進行左旋。 為了便于理解，我們先說明第(2)步，再說明第(1)步；
- 為了便于說明，我們設置“父節點”的代號為F(Father)，“當前節點”的代號為S(Son)。
- 為什么要“以F為支點進行左旋”呢？根據已知條件可知：S是F的右孩子。而之前我們說過，我們處理紅黑樹的核心思想：將紅色的節點移到根節點；然后，將根節點設為黑色。既然是“將紅色的節點移到根節點”，那就是說要不斷的將破壞紅黑樹特性的紅色節點上移(即向根方向移動)。而S又是一個右孩子，因此，我們可以通過“左旋”來將S上移！
按照上面的步驟(以F為支點進行左旋)處理之后：若S變成了根節點，那么直接將其設為“黑色”，就完全解決問題了；若S不是根節點，那我們需要執行步驟(1)，即“將F設為‘新的當前節點’”。
那為什么不繼續以S為新的當前節點繼續處理，而需要以F為新的當前節點來進行處理呢？這是因為“左旋”之后，F變成了S的“子節點”，即S變成了F的父節點；而我們處理問題的時候，需要從下至上(由葉到根)方向進行處理；也就是說，必須先解決“孩子”的問題，再解決“父親”的問題；所以，我們執行步驟(1)：將“父節點”作為“新的當前節點”。
叔叔結點為黑，插入結點是其父結點的左子結點
現象說明：當前節點(即，被插入節點)的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的左孩子
處理策略
- 將“父節點”設為“黑色”。
- 將“祖父節點”設為“紅色”。
- 以“祖父節點”為支點進行右旋。
為什么要這樣處理：
- 為了便于說明，我們設置“當前節點”為S(Original Son)，“兄弟節點”為B(Brother)，“叔叔節點”為U(Uncle)，“父節點”為F(Father)，祖父節點為G(Grand-Father)。
- S和F都是紅色，違背了紅黑樹的“特性(4)”，我們可以將F由“紅色”變為“黑色”，就解決了“違背‘特性(4)’”的問題；
- 但卻引起了其它問題：違背特性(5)，因為將F由紅色改為黑色之后，所有經過F的分支的黑色節點的個數增加了1。
- 那我們如何解決“所有經過F的分支的黑色節點的個數增加了1”的問題呢？ 我們可以通過“將G由黑色變成紅色”，同時“以G為支點進行右旋”來解決。
刪除操作
將紅黑樹內的某一個節點刪除。需要執行的操作依次是：首先，將紅黑樹當作一顆二叉查找樹，將該節點從二叉查找樹中刪除；然后，通過"旋轉和重新著色"等一系列來修正該樹，使之重新成為一棵紅黑樹。紅黑樹的刪除操作包括兩部分工作：
- 第一步：查找目標結點，將紅黑樹當作一顆二叉查找樹，將節點刪除。這和"刪除常規二叉查找樹中刪除節點的方法是一樣的"。分3種情況：
- 被刪除節點沒有兒子，即為葉節點。那么，直接將該節點刪除就OK了。
- 被刪除節點只有一個兒子。那么，直接刪除該節點，并用該節點的唯一子節點頂替它的位置。
- 被刪除節點有兩個兒子。那么，先找出它的后繼節點；然后把“它的后繼節點的內容”復制給“該節點的內容”；之后，刪除“它的后繼節點”。在這里，后繼節點相當于替身，在將后繼節點的內容復制給"被刪除節點"之后，再將后繼節點刪除。這樣就巧妙的將問題轉換為"刪除后繼節點"的情況了，下面就考慮后繼節點。在"被刪除節點"有兩個非空子節點的情況下，它的后繼節點不可能是雙子非空。既然"的后繼節點"不可能雙子都非空，就意味著"該節點的后繼節點"要么沒有兒子，要么只有一個兒子。若沒有兒子，則按"情況1"進行處理；若只有一個兒子，則按"情況2"進行處理。
- 第二步：刪除結點后自平衡，通過"旋轉和重新著色"等一系列來修正該樹，使之重新成為一棵紅黑樹。
- 因為"第一步"中刪除節點之后，可能會違背紅黑樹的特性。所以需要通過"旋轉和重新著色"來修正該樹，使之重新成為一棵紅黑樹。
告訴大家一種找前繼和后繼結點的直觀的方法：把二叉樹所有結點投射在X軸上，所有結點都是從左到右排好序的，所有目標結點的前后結點就是對應的前繼和后繼結點。如圖所示。
刪除操作的偽代碼《算法導論》
將"刪除紅黑樹中的節點"大致分為兩步，在第一步中"將紅黑樹當作一顆二叉查找樹，將節點刪除"后，可能違反"特性(2)、(4)、(5)"三個特性。第二步需要解決上面的三個問題，進而保持紅黑樹的全部特性。
為了便于分析，我們假設"x包含一個額外的黑色"(x原本的顏色還存在)，這樣就不會違反"特性(5)"。為什么呢？
- 通過RB-DELETE算法，我們知道：刪除節點y之后，x占據了原來節點y的位置。 既然刪除y(y是黑色)，意味著減少一個黑色節點；那么，再在該位置上增加一個黑色即可。這樣，當我們假設"x包含一個額外的黑色"，就正好彌補了"刪除y所丟失的黑色節點"，也就不會違反"特性(5)"。
因此，假設"x包含一個額外的黑色"(x原本的顏色還存在)，這樣就不會違反"特性(5)"。
現在，x不僅包含它原本的顏色屬性，x還包含一個額外的黑色。即x的顏色屬性是"紅+黑"或"黑+黑"，它違反了"特性(1)"。
現在，我們面臨的問題，由解決"違反了特性(2)、(4)、(5)三個特性"轉換成了"解決違反特性(1)、(2)、(4)三個特性"。RB-DELETE-FIXUP需要做的就是通過算法恢復紅黑樹的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是：將x所包含的額外的黑色不斷沿樹上移(向根方向移動)，直到出現下面的姿態：
- x指向一個"紅+黑"節點。此時，將x設為一個"黑"節點即可。
- x指向根。此時，將x設為一個"黑"節點即可。
- 非前面兩種姿態。
x是“紅+黑”節點。
- 處理方法： 直接把x設為黑色，結束。此時紅黑樹性質全部恢復。
x是“黑+黑”節點，且x是根。
- 處理方法：什么都不做，結束。此時紅黑樹性質全部恢復。
x是“黑+黑”節點，且x不是根。
- 處理方法：這種情況又可以劃分為4種子情況。
x是"黑+黑"節點，x的兄弟節點是紅色
現象說明：x是"黑+黑"節點，x的兄弟節點是紅色。(此時x的父節點和x的兄弟節點的子節點都是黑節點)。
處理策略
- 將x的兄弟節點設為“黑色”。
- 將x的父節點設為“紅色”。
- 對x的父節點進行左旋。
- 左旋后，重新設置x的兄弟節點。
為什么要這樣處理：
- 這樣做的目的是將其轉換為下面三種情況，從而進行進一步的處理。對x的父節點進行左旋；左旋后，為了保持紅黑樹特性，就需要在左旋前“將x的兄弟節點設為黑色”，同時“將x的父節點設為紅色”；左旋后，由于x的兄弟節點發生了變化，需要更新x的兄弟節點，從而進行后續處理。
x是"黑+黑"節點，x的兄弟節點是黑色，x的兄弟節點的兩個孩子都是黑色
現象說明：x是“黑+黑”節點，x的兄弟節點是黑色，x的兄弟節點的兩個孩子都是黑色。
處理策略
- 將x的兄弟節點設為“紅色”。
- 設置“x的父節點”為“新的x節點”。
為什么要這樣處理：
- 這個情況的處理思想：
- 是將“x中多余的一個黑色屬性上移(往根方向移動)”。 x是“黑+黑”節點，我們將x由“黑+黑”節點 變成 “黑”節點，多余的一個“黑”屬性移到x的父節點中，即x的父節點多出了一個黑屬性(若x的父節點原先是“黑”，則此時變成了“黑+黑”；若x的父節點原先時“紅”，則此時變成了“紅+黑”)。
- 此時，需要注意的是：所有經過x的分支中黑節點個數沒變化；但是，所有經過x的兄弟節點的分支中黑色節點的個數增加了1(因為x的父節點多了一個黑色屬性)！為了解決這個問題，我們需要將“所有經過x的兄弟節點的分支中黑色節點的個數減1”即可，那么就可以通過“將x的兄弟節點由黑色變成紅色”來實現。
經過上面的步驟(將x的兄弟節點設為紅色)，多余的一個顏色屬性(黑色)已經跑到x的父節點中。我們需要將x的父節點設為“新的x節點”進行處理。
- 若“新的x節點”是“黑+紅”，直接將“新的x節點”設為黑色，即可完全解決該問題；
- 若“新的x節點”是“黑+黑”，則需要對“新的x節點”進行進一步處理。
x是“黑+黑”節點，x的兄弟節點是黑色；x的兄弟節點的左孩子是紅色，右孩子是黑色的
現象說明：x是“黑+黑”節點，x的兄弟節點是黑色；x的兄弟節點的左孩子是紅色，右孩子是黑色的。
處理策略
- 將x兄弟節點的左孩子設為“黑色”。
- 將x兄弟節點設為“紅色”。
- 對x的兄弟節點進行右旋。
- 右旋后，重新設置x的兄弟節點。
為什么要這樣處理：
- 我們處理其的目的是為了將其進行轉換，轉換成下面的情況,從而進行進一步的處理。轉換的方式是對x的兄弟節點進行右旋；為了保證右旋后，它仍然是紅黑樹，就需要在右旋前“將x的兄弟節點的左孩子設為黑色”，同時“將x的兄弟節點設為紅色”；右旋后，由于x的兄弟節點發生了變化，需要更新x的兄弟節點，從而進行后續處理。
x是“黑+黑”節點，x的兄弟節點是黑色；x的兄弟節點的右孩子是紅色的，x的兄弟節點的左孩子任意顏色
現象說明：x是“黑+黑”節點，x的兄弟節點是黑色；x的兄弟節點的右孩子是紅色的，x的兄弟節點的左孩子任意顏色。
處理策略
- 將x父節點顏色 賦值給 x的兄弟節點。
- 將x父節點設為“黑色”。
- 將x兄弟節點的右子節設為“黑色”。
- 對x的父節點進行左旋。
- 設置“x”為“根節點”。
為什么要這樣處理：
- 去掉x中額外的黑色，將x變成單獨的黑色。處理的方式是“：進行顏色修改，然后對x的父節點進行左旋。下面，我們來分析是如何實現的。
- 為了便于說明，我們設置“當前節點”為S(Original Son)，“兄弟節點”為B(Brother)，“兄弟節點的左孩子”為BLS(Brother’s Left Son)，“兄弟節點的右孩子”為BRS(Brother’s Right Son)，“父節點”為F(Father)。
- 我們要對F進行左旋。但在左旋前，我們需要調換F和B的顏色，并設置BRS為黑色。為什么需要這里處理呢？因為左旋后，F和BLS是父子關系，而我們已知BLS是紅色，如果F是紅色，則違背了“特性(4)”；為了解決這一問題，我們將“F設置為黑色”。 但是，F設置為黑色之后，為了保證滿足“特性(5)”，即為了保證左旋之后：
- 第一，“同時經過根節點和S的分支的黑色節點個數不變”。
若滿足“第一”，只需要S丟棄它多余的顏色即可。因為S的顏色是“黑+黑”，而左旋后“同時經過根節點和S的分支的黑色節點個數”增加了1；現在，只需將S由“黑+黑”變成單獨的“黑”節點，即可滿足“第一”。
- 第一，“同時經過根節點和S的分支的黑色節點個數不變”。
- 第二，“同時經過根節點和BLS的分支的黑色節點數不變”。
若滿足“第二”，只需要將“F的原始顏色”賦值給B即可。之前，我們已經將“F設置為黑色”(即，將B的顏色"黑色"，賦值給了F)。至此，我們算是調換了F和B的顏色。 - 第三，“同時經過根節點和BRS的分支的黑色節點數不變”。
在“第二”已經滿足的情況下，若要滿足“第三”，只需要將BRS設置為“黑色”即可。
經過，上面的處理之后。紅黑樹的特性全部得到的滿足！接著，我們將x設為根節點，就可以跳出while循環(參考偽代碼)；即完成了全部處理。
總結
以上是生活随笔為你收集整理的【理论】红黑树的实现原理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【源码解析】hashMap源码跟进
- 下一篇： 【源码解析】HashMap源码跟进（红黑