---
title: 'Red-Black Tree'
disqus: hackmd
---
[TOC]

## Red-Black Tree

* **Def**
1. 本身是一顆 Balanced Binary Search Tree
2. Node 的顏色非紅及黑
3. Root、Null 為黑色
4. 每個紅色 Node 都有兩個黑色 Nodes
5. 任意 Node 到每個 Leaf 經過的黑 Nodes 皆一樣多 (RBT 的 Balanced 定義)

<br><br>
* 用紅黑樹的原因：在 BST 中最佳的搜尋時間為 $O(log_2n)$，最差為 $O(n)$，
假設 n = 128 最佳時間為：7 ，相差了數十倍之遠

* 而在紅黑樹中利用 **紅色** 及 **黑色** 能夠使 `最長路徑` 不會超過 `最短路徑` 的兩倍

---

## 變色規則
* 還不懂 [Rotation 操作](https://hackmd.io/kUkJBb2TSrCrA3eYzsjcyQ#Rotation---%E6%97%8B%E8%BD%89)的同學

#### ==Single Left Rotation 左單旋轉==
* 左單旋轉完不須變色，待右旋轉完在變色即可

#### ==Right Rotation 右旋轉==
* A Node 轉下來後變為紅色，B Node 變為黑色，C Node 保持紅色不變

---

#### ==Single Right Rotation 右單旋轉==
* 右單旋轉完不須變色，待左旋轉完在變色即可

#### ==Left Rotation 左旋轉==
* A Node 轉下來後變為紅色，B Node 變為黑色，C Node 保持紅色不變
<br><br><br>
* 相異點 A、B Node 就不標註


---

## Insertion - 插入
* 某些圖因為語法關係，單一子點無法顯示左右方向，為清楚解釋會在新增 New Node 時一起畫出另一邊的 Null Node，而其餘的 Null Node 非必要將不繪製

* 判斷方法為：插入後觀察顏色在旋轉

#### ==1. 長輩變色==
* 此情況是唯一不需要旋轉的變色情況
* 若插入一個新 Node 之後發現
* Parent 為紅色
* Uncle 為紅色

digraph graphname{
    1[label="Uncle" fontcolor=red color=red]
    2[label="Grandparent"]
    3[label="Parent" fontcolor=red color=red]
    2->3
    2->1
    0[label="Null" style=dashed]
    3->0
    4[label="New" fontcolor=red color=red]
    3->4
    
}

* 則我們將 Parent、Uncle 改為黑色，Grandparent 改為紅色

digraph graphname{
    1[label="Uncle" ]
    2[label="Grandparent" fontcolor=red color=red]
    3[label="Parent" ]
    2->3
    2->1
    0[label="Null" style=dashed]
    3->0
    4[label="New" fontcolor=red color=red]
    3->4
    
}

* 如果 Grandparent 為 Root 則再改為黑色

digraph graphname{
    1[label="Uncle" ]
    2[label="Grandparent"]
    3[label="Parent" ]
    2->3
    2->1
    0[label="Null" style=dashed]
    3->0
    4[label="New" fontcolor=red color=red]
    3->4
    
}

---

#### ==2. Single Right Rotation 右單旋轉 -> Left Rotation 左旋轉==
* 若插入一個新 Node 之後發現

* Parent 為紅色
* Uncle 為黑色
* New Node 在 Left Child

digraph graphname{
    1[label="Uncle"]
    2[label="Grandparent"]
    3[label="Parent"  color=red fontcolor=red]
    2->3
    2->1
    
    0[label="New" fontcolor=red color=red]
    3->0
    4[label="Null" style=dashed]
    3->4
    
}

* 則我們先進行 Single Right Rotation (右單旋轉)

digraph graphname{
    1[label="Uncle"]
    2[label="Grandparent"]
    3[label="New"  color=red fontcolor=red]
    2->3
    2->1
    
    0[label="Null" style=dashed]
    3->0
    4[label="Parent" fontcolor=red color=red]
    3->4
    
}

* 在進行 Left Rotation (左旋轉)

digraph graphname{
    1[label="Uncle"]
    2[label="Grandparent"]
    3[label="New"  color=red fontcolor=red]
    
    2->1
    
    0[label="Null" style=dashed]
    3->2
    4[label="Parent" fontcolor=red color=red]
    3->4
    2->0
}

* 變色處理

digraph graphname{
    1[label="Uncle"]
    2[label="Grandparent" color=red fontcolor=red]
    3[label="New"  ]
    
    2->1
    
    0[label="Null" style=dashed]
    3->2
    4[label="Parent" fontcolor=red color=red]
    3->4
    2->0
}

---

#### ==3. Single Left Rotation 左單旋轉 -> Right Rotation 右旋轉==
* 若插入一個新 Node 之後發現

* Parent 為紅色
* Uncle 為黑色
* New Node 在 Right Child

digraph graphname{
    0[label="Null" style=dashed]
    1[label="Parent" color=red fontcolor=red]
    2[label="Grandparent"]
    3[label="Uncle"]
    4[label="New"  fontcolor=red color=red]
    2->3
    2->1
    1->4
    1->0
    
}

* 則我們先進行 Single Left Rotation (左單旋轉)

digraph graphname{
    0[label="Parent" color=red fontcolor=red]
    1[label="Null"  style=dashed]
    2[label="Grandparent"]
    4[label="New"  fontcolor=red color=red]
    3[label="Uncle"]
    
    2->4
    2->3
    4->0
    4->1
}

* 在進行 Right Rotation (右旋轉)

digraph graphname{
    0[label="Parent" color=red fontcolor=red]
    1[label="Null"  style=dashed]
    2[label="Grandparent"]
    4[label="New"  fontcolor=red color=red]
    3[label="Uncle"]
    
    4->0
    4->2
    2->1
    2->3
}

* 變色處理

digraph graphname{
    0[label="Parent" color=red fontcolor=red]
    1[label="Null"  style=dashed]
    2[label="Grandparent"   fontcolor=red color=red]
    4[label="New"]
    3[label="Uncle"]
    
    4->0
    4->2
    2->1
    2->3
}

---

## Deletion - 刪除

to becontinued

---

## Reference - 參考資料

* [Second Round](http://alrightchiu.github.io/SecondRound/red-black-tree-introjian-jie.html)
* [Wikipedia](https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91)
* [Algorithm Visualizations](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)

###### tags: `Data Structure`