紅黑樹
引子
前幾天看java TreeMap源碼，發現TreeMap是有序的map集合，是以很感興趣他是怎麼實作的，原來是用了紅黑樹來實作。
相關知識介紹
二叉排序樹：中序周遊即得有序序列（大的放右邊，小的放左邊）
Avl樹/平衡二叉樹：左右子樹高度差不超過一的二叉排序樹
紅黑樹：不太嚴格的平衡二叉樹（做了限制）
紅黑樹介紹
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。
它是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。後來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。
紅黑樹和AVL樹類似，都是在進行插入和删除操作時通過特定操作保持二叉查找樹的平衡，進而獲得較高的查找性能。
它雖然是複雜的，但它的最壞情況運作時間也是非常良好的，并且在實踐中是高效的： 它可以在O(log n)時間内做查找，插入和删除，這裡的n 是樹中元素的數目。
紅黑樹限制
紅黑樹是每個節點都帶有顔色屬性的二叉查找樹，顔色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:
性質1. 節點是紅色或黑色。
性質2. 根節點是黑色。
性質3 每個葉節點（NIL節點，空節點）是黑色的。
性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。(從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長)
性質三意思是NIL節點是黑色的，比如203節點其實有兩個NIL黑色子節點
紅黑樹左旋右旋
左旋
了解為，對X左旋，X的右孩子當爸爸，X變成原來右孩子的左節點
算法導論：
LEFT-ROTATE(T, x) 01 y ← right[x] // 前提：這裡假設x的右孩子為y。下面開始正式操作 02 right[x] ← left[y] // 将 “y的左孩子” 設為 “x的右孩子”，即 将β設為x的右孩子 03 p[left[y]] ← x // 将 “x” 設為 “y的左孩子的父親”，即 将β的父親設為x 04 p[y] ← p[x] // 将 “x的父親” 設為 “y的父親” 05 if p[x] = nil[T] 06 then root[T] ← y // 情況1：如果 “x的父親” 是空節點，則将y設為根節點 07 else if x = left[p[x]] 08 then left[p[x]] ← y // 情況2：如果 x是它父節點的左孩子，則将y設為“x的父節點的左孩子” 09 else right[p[x]] ← y // 情況3：(x是它父節點的右孩子) 将y設為“x的父節點的右孩子” 10 left[y] ← x // 将 “x” 設為 “y的左孩子” 11 p[x] ← y // 将 “x的父節點” 設為 “y” 右旋
了解為：對Y右旋，Y的左孩子當爸爸，Y變成原來左孩子的右節點
RIGHT-ROTATE(T, y) 01 x ← left[y] // 前提：這裡假設y的左孩子為x。下面開始正式操作 02 left[y] ← right[x] // 将 “x的右孩子” 設為 “y的左孩子”，即 将β設為y的左孩子 03 p[right[x]] ← y // 将 “y” 設為 “x的右孩子的父親”，即 将β的父親設為y 04 p[x] ← p[y] // 将 “y的父親” 設為 “x的父親” 05 if p[y] = nil[T] 06 then root[T] ← x // 情況1：如果 “y的父親” 是空節點，則将x設為根節點 07 else if y = right[p[y]] 08 then right[p[y]] ← x // 情況2：如果 y是它父節點的右孩子，則将x設為“y的父節點的左孩子” 09 else left[p[y]] ← x // 情況3：(y是它父節點的左孩子) 将x設為“y的父節點的左孩子” 10 right[x] ← y // 将 “y” 設為 “x的右孩子” 11 p[y] ← x // 将 “y的父節點” 設為 “x” 紅黑樹插入
三個步驟：
1：将紅黑樹當成普通的二叉排序樹，插入新節點
2：将新節點渲染為紅色
為什麼不渲染成黑色，假設渲染成黑色，那麼就違背了性質5，渲染成紅色可能違背性質4
3：insert fixup()
RB-INSERT(T, z) 01 y ← nil[T] // 建立節點“y”，将y設為空節點。 02 x ← root[T] // 設“紅黑樹T”的根節點為“x” 03 while x ≠ nil[T] // 找出要插入的節點“z”在二叉樹T中的位置“y” 04 do y ← x 05 if key[z] < key[x] 06 then x ← left[x] 07 else x ← right[x] 08 p[z] ← y // 設定 “z的父親” 為 “y” 09 if y = nil[T] 10 then root[T] ← z // 情況1：若y是空節點，則将z設為根 11 else if key[z] < key[y] 12 then left[y] ← z // 情況2：若“z所包含的值” < “y所包含的值”，則将z設為“y的左孩子” 13 else right[y] ← z // 情況3：(“z所包含的值” >= “y所包含的值”)将z設為“y的右孩子” 14 left[z] ← nil[T] // z的左孩子設為空 15 right[z] ← nil[T] // z的右孩子設為空。至此，已經完成将“節點z插入到二叉樹”中了。 16 color[z] ← RED // 将z着色為“紅色” 17 RB-INSERT-FIXUP(T, z) // 通過RB-INSERT-FIXUP對紅黑樹的節點進行顔色修改以及旋轉，讓樹T仍然是一顆紅黑樹 RB-INSERT-FIXUP(T, z) 01 while color[p[z]] = RED // 若“目前節點(z)的父節點是紅色”，則進行以下處理。 02 do if p[z] = left[p[p[z]]] // 若“z的父節點”是“z的祖父節點的左孩子”，則進行以下處理。 03 then y ← right[p[p[z]]] // 将y設定為“z的叔叔節點(z的祖父節點的右孩子)” 04 if color[y] = RED // Case 1條件：叔叔是紅色 05 then color[p[z]] ← BLACK ▹ Case 1 // (01) 将“父節點”設為黑色。 06 color[y] ← BLACK ▹ Case 1 // (02) 将“叔叔節點”設為黑色。 07 color[p[p[z]]] ← RED ▹ Case 1 // (03) 将“祖父節點”設為“紅色”。 08 z ← p[p[z]] ▹ Case 1 // (04) 将“祖父節點”設為“目前節點”(紅色節點) 09 else if z = right[p[z]] // Case 2條件：叔叔是黑色，且目前節點是右孩子 10 then z ← p[z] ▹ Case 2 // (01) 将“父節點”作為“新的目前節點”。 11 LEFT-ROTATE(T, z) ▹ Case 2 // (02) 以“新的目前節點”為支點進行左旋。 12 color[p[z]] ← BLACK ▹ Case 3 // Case 3條件：叔叔是黑色，且目前節點是左孩子。(01) 将“父節點”設為“黑色”。 13 color[p[p[z]]] ← RED ▹ Case 3 // (02) 将“祖父節點”設為“紅色”。 14 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 // (03) 以“祖父節點”為支點進行右旋。 15 else (same as then clause with "right" and "left" exchanged) // 若“z的父節點”是“z的祖父節點的右孩子”，将上面的操作中“right”和“left”交換位置，然後依次執行。 16 color[root[T]] ← BLACK 我了解的insert fixup僞碼：
While（目前節點z的父節點是紅色的話）{ If(z的父節點是z祖父節點的左孩子){ Case1（父紅，叔紅） 父黑，叔黑，祖父紅，祖父設為目前節點。 Break； Case2（父紅，叔黑，目前節點是右孩子） 父節點設為目前節點，以目前節點為支點左旋 Break； Case3（父紅，叔黑，目前節點是左孩子） 父黑，祖父紅，以祖父為支點右旋。 Break； }else{ Case4（父紅，叔紅） 父黑，叔黑，祖父紅，祖父設為目前節點。 Break； Case5（父紅，叔黑，目前節點是左孩子） 父節點設為目前節點，以目前節點為支點右旋 Break； Case6（父紅，叔黑，目前節點是右孩子） 父黑，祖父紅，以祖父為支點左旋。 Break； }}color[root[T]] ← BLACK 例子：
上圖的情況就屬于case6
新插入的節點是668，左圖是未fixup，有圖經過fixup之後
668的父節點是668祖父節點的右孩子，進入else，668的父親是紅色，叔父是NIL也就是黑色，且目前節點668是右節點，是以把父親設為黑色，祖父設為紅色，以祖父為支點左旋。得到右圖。現在目前節點是668，不滿足while，跳出循環。Fixup完畢.下面再加入531
上圖的情況就屬于case1
新插入的節點是531，左圖是未fixup，有圖經過fixup之後
531的父節點是531祖父節點的左孩子，進入if，531的父親是紅色，叔父是紅色，是以把父親和叔父改為黑色，祖父改為紅色，祖父設為目前節點。此時目前節點沒有父親，跳出while，把根節點606設為黑色。Fixup完畢。下面加入496
上圖的情況就屬于case5
新插入的節點是496，左圖是未fixup，有圖經過fixup之後
496的父節點是496祖父節點的右孩子，進入else，496父親是紅色，叔父是黑色，且目前節點496是左孩子，是以父親設為目前節點，以目前節點為支點右旋。得到右圖，得到右圖之後直接進入case6.如下面所示
現在目前節點是531,531的父節點是531的祖父節點的右孩子，進入else，531的父親是紅色，叔父是黑色，并且目前節點531是右孩子，是以進入case6，父親496設為黑色，祖父489設為紅色，以祖父節點為支點左旋得到右圖。現在目前節點是531，不滿足while，跳出循環。Fixup完畢。
其他情況自己試試吧，http://sandbox.runjs.cn/show/2nngvn8w
紅黑樹删除
參考文獻
算法導論
js紅黑樹
skywang12345