大神的世界

插入 (插入的顏色預設為紅色)

插入的位置是 root 直接塗黑 結束

parent 是紅色？

不是 ok (結束)

是

uncle 是紅色?

是

grandparent 塗紅，parent 和 uncle 塗黑 重新考慮 grandparent  (將 grandparent 視作新插入節點)

不是

先調整成一直線 (註1)

若插入節點在左邊，則對 grandparent 右旋

若插入節點在右邊，則對 grandparent 左旋

parent 和 grandparent 顏色互換 

參考網址：https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

註1

請參考網址插入之情形 4 和 情形 5 的圖

須注意調整後，parent 的位置不變 ( N 仍舊是 leaf )

刪除

參考網址（圖示）：http://alrightchiu.github.io/SecondRound/red-black-tree-deleteshan-chu-zi-liao-yu-fixupxiu-zheng.html

因為紅黑樹屬於 BST 所以刪除時會拿左邊最大或右邊最小的 node 替代

因此任意 node 刪除，皆可視為 leave node 刪除 (這邊我們用右邊最小替代）

以參考網址之圖六 (a) 為例

刪除 36 相當於刪除 39

刪除 16 相當於刪除 19

刪除 48 相當於刪除 51

刪除 45 相當於刪除 45

可能情形 (假設 current 為刪除的 node)

case 0 :
current 有紅色 child ，直接將該 child 塗成黑色     ( 圖六 ( j ) ) 註1 

case 1:

sibling 是紅的，parent 是黑的，兩個顏色互換對 parent 做左旋

case 2:

sibling 是黑的且 sibling 兩 child 都是黑的

把 sibling 塗紅，看 parent

若 parent 是紅的  , 把 parent 塗黑 結束

若 parent 是黑的，將 current 移到 parent 重新判斷  ( 看 parent 的 sibling 是黑的還紅的決定 case 1 還 2，但這次沒有刪除只有調整 )

case 3:

sibling 是黑的且 sibling 左邊是紅的右邊是黑的

讓 sibling 跟自己的 leftchild 顏色互換，再右旋進入 case 4

case 4:

sibling 是黑的且 sibling 右邊是紅的 (左邊隨便)

sibling 塗成 parent 的顏色，parent 和 sibling 的右邊塗黑，並對 parent 左旋

將 current 移至 root ，把 root 塗黑

以上皆為 sibling 在 current 右邊的作法

若 sibling 在 current 左邊，則左右互換 ( 左旋 -> 右旋 , leftchild -> rightchild 等)

若沒 sibling 直接刪除 ( case 5 ??)

註1

current 不可能有 2 紅, 因為右邊最小所以 leftchild 一定是 nil

如果右邊沒有，則拿左邊替代