<style>
* {
letter-spacing: 0.02em;
text-align:justify
}
p.part {
text-indent: 2em;
line-height: 2em;
}
.keyword {
color: red;
}

.variable {
color: red;
border-radius: 10%;
margin: 1px;
padding: 1px 5px;
background: #f5f5f5;
font-weight: 480;
}

.not-indent{
text-indent: 0;
line-height: 0;
}
p .small {
text-indent: 0em;
line-height: 0em;
}
</style>

# **Red Black Tree**

## **Introduction**

隨著Binary Search Tree節點成長BST容易產生偏重一邊形成skewed tree，使得資料搜尋時間複雜度變為$O(n)$。為了解決上述問題，現今已有不同的資料結構維持BST平衡，如：AVL Tree、Red Black Tree擁有各自獨特的規則使得BST不會產生歪斜情況發生，而本篇將著重介紹台綜大111考古題出現的Red Black Tree

## **AVL Tree Review**
---
### Case1-LL

### Case2-RR


### Case3-RL

### Case4-LR


## **Red Black Tree**

### **Rule**
---

1. 每個節點只有兩種顏色==紅==或==黑==
2. 根節點(root)和外部節點(external node or NIL)一定是==黑色==
3. 所有從根節點(Root)至外部節點的路徑(Path)所包含的==黑色==節點數量==相同==
4. ==不存在==兩個==紅色節點==彼此==相連== $\equiv$ ==紅色節點==必有兩個==黑色子節點==

Red black Tree為各個節點上色，並增加了NIL(Null)節點的概念，其代表著(Leaf node)，目的是為了維持rule成立，為了方便通常省略表示。
### **Rotation**
---

### **Insert**
---
1. 將資料新增至原本的Binary search tree
2. 將==新節點==塗成==紅色==
3. 查看新節點是否違反rule 4，若違反則進行調整

### **Case 1 - Uncle節點是紅色 (LLr , RRr , LRr , RLr)**


> current node (new node)為z、parent為pz、grandparent為gz、uncle為y

1. 將黑色傳給grandparent下一Level (parent and uncle)自身改為紅色
2. 如果grandparent是root節點，強制改為黑色
3. 將z pointer指向grandparent使其成為下一個修正觀察點

#### example - ***LLr***


### **Case 2 - Uncle節點是黑色 (LLb , RRb , LRb , RLb)**


> 根據LL、RR、LR、RL Case進行旋轉修正

> Case 2實際上還要區分另外一個Case (實作上需要)，但紙筆測驗只記一個Case處理比較快

#### example - ***LRb*** (不含指標操作僅代表數值)

#### example - Case 1 ~ Case 2 (含指標操作)


### **Delete**
---
Red Black Tree刪除如同BST一樣，只是多了顏色的限制
> Review BST delete
> 1. 如果刪除節點只有左子節點，則左子節點取代刪除節點
> 2. 如果刪除節點只有右子節點，則右子節點取代刪除節點
> 3. 如果刪除節點有兩個子節點，則可以選擇左子樹最大值或者右子樹最小值取代

如果刪除是==黑色節點==，則RBT完成初步刪除後要進行調整，$x$代表取代上來的節點(current node)，而$w$代表兄弟節點

> x represent current node and w represent x's sibling
### **Case 1 - sibling $w$ 是紅色**

1. 將sibling $w$ 改成==黑色==
2. 將$x$的parent 改成==紅色==
3. $x$'s parent node 向==左旋轉==
4. $w$指向$x$'s parent node右節點
5. 進到Case 2 or 3 or 4


### **Case 2 - sibling $w$ 是黑色，且$w$兩個子節點也是黑色**


1. 將sibling $w$改成==紅色==
2. $x$指向$x$'s parent node重新判斷Case

> 下圖B為任意顏色，以淺紅色表示，Case 2處理完要繼續循環處理B直到沒有違反規則

### **Case 3 - sibling $w$ 是黑色，且$w$左子節點是紅色、右子節點是黑色**

1. $w$左子節點改為==黑色==
2. $w$自己改為==紅色==
3. $w$進行==右旋(Right Rotation)==
4. $w$指向$x$'s parent右子節點
5. 進到Case 4


### **Case 4 - sibling $w$ 是黑色，且$w$右子節點是紅色**

1. $w$改為==parent node顏色==
2. parent nodee改為==黑色==
3. $w$右子節點顏色改為==黑色==
4. parent nodee進行==左旋(Left Rotation)==
5. $x$指向Root，並將Root改為==黑色==


### **Flow Chart**
---

> Reference: Red Black Tree: Delete(刪除資料)與Fixup(修正)

## 考古題
---
### 111 台綜大 A06


> Insert 10


> Insert 100


> Insert 30


> Insert 80


> Insert 50


> Remove 10


> Insert 60


> Insert 70


> Insert 40


> Remove 80 (找左子樹最大取代，Root改成黑色)


> 詳解




## Reference
[1] [Red Black Tree: Delete(刪除資料)與Fixup(修正)](https://alrightchiu.github.io/SecondRound/red-black-tree-deleteshan-chu-zi-liao-yu-fixupxiu-zheng.html)

[2] Introduction to Algorithm (Fourth Edition), Cambridge, Massachusetts London, England

[3] [Red/Black Tree Visualization](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)

>[name=Sky]

###### tags: `資料結構`