為實習準備的資料化結構（8）-- 傾心圖解紅黑樹

紅黑樹

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，
紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于 1，所以紅黑樹不是嚴格意義上的平衡二叉樹（AVL），但 對之進行平衡的代價較低， 其平均統計性能要強于 AVL ，
由于每一棵紅黑樹都是一顆二叉排序樹，因此，在對紅黑樹進行查找時，可以采用運用于普通二叉排序樹上的查找演算法，在查找程序中不需要顏色資訊，

紅黑樹的特征

紅黑樹是每個結點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色，在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

性質1. 結點是紅色或黑色，
性質2. 根結點是黑色，
性質3. 所有葉子都是黑色，（葉子是NULL結點）（這個性質我也不知道有什么用，最好配上上面的圖看，不然會暈）
性質4. 每個紅色結點的兩個子結點都是黑色，（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點）
性質5. 從任一節結點到每個葉子的所有路徑都包含相同數目的黑色結點

這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，
是性質4導致路徑上不能有兩個連續的紅色結點確保了這個結果，最短的可能路徑都是黑色結點，最長的可能路徑有交替的紅色和黑色結點，因為根據性質5所有最長的路徑都有相同數目的黑色結點，這就表明了沒有路徑能多于任何其他路徑的兩倍長，

紅黑樹自平衡的奧秘

紅黑樹能夠實作自平衡，靠的是三個法寶：左旋、右旋和變色，
對于旋轉我就不再多說了，前面的AVL樹要是不夠看可以再看看伸展樹，

左旋：以某個結點作為支點(旋轉結點)，其右子結點變為旋轉結點的父結點，右子結點的左子結點變為旋轉結點的右子結點，左子結點保持不變，
右旋：以某個結點作為支點(旋轉結點)，其左子結點變為旋轉結點的父結點，左子結點的右子結點變為旋轉結點的左子結點，右子結點保持不變，
變色：結點的顏色由紅變黑或由黑變紅，

紅黑樹的查找也不說了，它是二叉樹，所以二叉樹怎么查找，紅黑樹就怎么查找，

紅黑樹自平衡操作

插入節點

第一步: 將紅黑樹當作一顆二叉查找樹，將節點插入，
第二步：將插入的節點著色為"紅色"，為什么是紅色？你猜啊
（看一下性質五）
第三步: 通過一系列的旋轉或著色等操作，使之重新成為一顆紅黑樹，

第二步中，將插入節點著色為"紅色"之后，不會違背"特性(5)"，那它到底會違背哪些特性呢？
很顯然，只有性質4.（每個紅色結點的兩個子結點都是黑色，（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點））比較危險，
那接下來，想辦法使之"滿足性質4. "，就可以將樹重新構造成紅黑樹了，

昨天我躺在床上，輾轉反側，夢中頓悟，紅黑樹插入會有以下這么幾種情況：

1、被插入的節點是根節點，
	那最好辦，那說明是空樹，直接涂黑就好，
2、新插入節點的父節點是黑的（新插入的節點，不會有子節點存在，這個可以放心）
	這個更好辦，就插入就完了
3、新插入節點的父節點是紅的
	那就有意思了，具體情況下面討論

對于上面第三種情況的再分析：

1、新節點的父節點的兄弟節點是紅的
//以下兩種情況默認包含了父節點沒有兄弟的情況
2、新節點的父節點的兄弟節點是黑的，且當前節點是其父節點的 右 孩子
3、新節點的父節點的兄弟節點是黑的，且當前節點是其父節點的 左 孩子
（為什么要這樣分？不急慢慢看，我也納悶兒呢！！！）

上面三種情況處理問題的核心思路都是：將紅色的節點移到根節點；然后，將根節點設為黑色，下面對它們詳細進行介紹，

情況一：

策略：

(01) 將“父節點”設為黑色，
(02) 將“叔叔節點”設為黑色，
(03) 將“祖父節點”設為“紅色”，
(04) 將“祖父節點”設為“當前節點”(紅色節點)；即，之后繼續對“當前節點”進行操作，

這里需要說明一下，當祖父節點被染紅，它可能會和它自己的父節點起沖突，所以需要向上遞回，
就碧如這樣：

為什么采用這個策略？

“當前節點”和“父節點”都是紅色，違背“性質4. ”，所以，將“父節點”設定“黑色”以解決這個問題，
但是，將“父節點”由“紅色”變成“黑色”之后，違背了“性質5. ”：因為，包含“父節點”的分支的黑色節點的總數增加了1，
解決這個問題的辦法是：將“祖父節點”由“黑色”變成紅色，同時，將“叔叔節點”由“紅色”變成“黑色”，
這里為什么要將“叔叔節點”也變黑？思考思考，不難理解的，
理解不了的話對著上面那張圖去數性質5.

這里需要再說明一下，當祖父節點被染紅，它可能會和它自己的父節點起沖突，所以需要向上遞回，

情況二：

策略：

(01) 將“父節點”作為“新的當前節點”，
(02) 以“新的當前節點”為支點進行左旋，

草率了，，，
哎，看圖吧：

吶，弄完之后，變成了第三種情況了，

情況三：

策略：

(01) 將“父節點”設為“黑色”，
(02) 將“祖父節點”設為“紅色”，
(03) 以“祖父節點”為支點進行右旋，

為什么采用這個策略？

為了便于說明，我們設定“當前節點”為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為支點進行右旋”來解決，

對于紅黑樹的節點插入，我講明白了嗎？
關注點贊收藏，我們繼續往下，

洗掉節點

相較于插入操作，紅黑樹的洗掉操作則要更為復雜一些，洗掉操作首先要確定待洗掉節點有幾個孩子，如果有兩個孩子，不能直接洗掉該節點，而是要先找到該節點的前驅（該節點左子樹中最大的節點）或者后繼（該節點右子樹中最小的節點），然后將前驅或者后繼的值復制到要洗掉的節點中，最后再將前驅或后繼洗掉，

第一步：將紅黑樹當作一顆二叉查找樹，將節點洗掉，
第二步：通過"旋轉和重新著色"等一系列來修正該樹，使之重新成為一棵紅黑樹，

在第一步中"將紅黑樹當作一顆二叉查找樹，將節點洗掉"后，可能違反"性質(2)、(4)、(5)"三個性質，第二步需要解決上面的三個問題，進而保持紅黑樹的全部特性，

洗掉一個紅色節點，并不會有什么不適，
所以我們將目光聚焦在洗掉一個黑色節點上，

洗掉一個節點有以下四種情況：

1.洗掉的節點沒有孩子
2.洗掉的節點只有左子樹
3.洗掉的節點只有右子樹
*4.洗掉的節點擁有左子樹和右子樹

其實只有上面前三種情況，對于第四種情況，可以找到待洗掉節點的直接后繼節點，用這個節點的值替代待洗掉節點，接著情況轉變為洗掉這個直接后繼節點，情況也變為前三種之一，（前驅和后繼至多只有一個孩子節點）

1.洗掉的節點只有左子樹或只有右子樹：

2.洗掉的節點沒有孩子

1）待洗掉節點是紅色的，直接刪去這個節點，
2）父節點P是紅色節點
　解決方案：把P節點染成黑色，兄弟節點染成紅色，洗掉節點D，

3）兄弟節點S是紅色節點

解決方案：把P染成紅色，S染成黑色，然后以P為軸做相應的旋轉操作（D為P的左子樹則左旋，否則右旋）

4）節點D的遠親侄子為紅色節點的情況（父節點P可紅可黑）

解決方案：交換P和S的顏色，然后把遠親侄子節點SR/SL設定為黑色，再已P為軸做相應的旋轉操作（D為P的左子樹則左旋，否則右旋），洗掉節點D，

5）節點D的近親侄子為紅色節點的情況（父節點P可紅可黑）

解決方案：把S染成紅色，把近親侄子節點SR/SL染成黑色，然后以節點S為軸做相應的旋轉操作（D為P的左子樹則右旋，否則左旋），變成了情況4，按照情況4進行操作，

6）節點D，P，S均為黑色節點

解決方案：把D刪去，然后把節點S染成紅色，

①從節點P往上依然是全黑的情況

②從節點P往上是其他情況

哇，累，