# Data Struct - Tree : Red Black Tree
###### tags: `Data Struct - Tree`

## 一 . Red Black Tree
### (一) . 定義
1. 定義一 ： 顏色要求
- 每一個node必須不是黑色就是紅色。
- root必是黑色，external node必須是黑色。
- 剛開始新增的node為紅色。
2. 定義二 ： 相連要求
- 兩個紅色不可以相連。
- 紅色的node若有子，必須是黑色。
3. 定義三 ： 路徑要求。
- 在任何node，到節點以下的樹葉點，的黑色路徑都相同。
- 黑色路徑 ： 一個node到樹葉點的黑色點數目。

### (二) . 性質
1. 性質一 ： 滿足二元搜尋樹。(BST)
3. 性質二 ： 若nllptr存在，則其視為黑色。
- 所以，所有的樹葉點都視為nullptr的黑色節點。

## 二 . 動態操作 - 搜尋
## 三 . 動態操作 - 左右旋

## 四 . 動態操作 - 加入
### (一) . 方法與分析：
#### 1. 加入方法 ：
- $Step\ 1$ : 用BST的方法加入。
- $Step\ 2$ : 檢查是否滿足紅黑樹的顏色特性。

#### 2. 分析方法 ：
- 分析加入時的情況 ：
- 加入的必是紅子。
- 加入的必是leaf node。
- 分析合不合法的情況 ：
- 父節點是紅色時，必不合法。
- 因為加入的也是紅色，所以父節點是紅色下，必不合法。
- 相對，父節點為黑色下，必合法。
- 不合法的情況 ：
- $case \ 1$ : uncle為紅色。
- $case \ 2$ : uncle為黑色，加入的為父的左子。
- $case \ 3$ : uncle為黑色，加入的為父的右子。

### (二) . $Case\ 1$
#### 1. 形成情況 ：
- 加入的是樹葉點 ： cur指標必沒有子節點。
- 加入前滿足紅黑樹 ：
- parent、uncle為紅下。
- parent本為leaf(才可以被加入)。
- 呈上，因為parent是樹葉，又為了對祖父要滿足紅黑樹，uncle必為leaf。

#### 2. 解決方法
- $Step\ 1$ : 將parent，uncle塗黑。
- $Step\ 2$ : 將祖父塗紅。
- $Step\ 3$ : 對祖父進行fix。

### (三) . $Case\ 2$
#### 1. 形成情況 ：
- 加入的是樹葉點 ： cur指標必沒有子節點。
- 加入前滿足紅黑樹 ：
- parent為紅，uncle為黑下。
- parent本為leaf(才可以被加入)。
- 呈上，因為parent是樹葉，又為了對祖父要滿足紅黑樹，uncle必為nullptr。
#### 2. 解決方法
- $Step\ 1$ : 將祖父右旋。
- $Step\ 2$ : 將parent塗黑。
- 必滿足紅黑樹 ： 對原本的祖先
- 接口位置和顏色一樣 ： 只是祖父變成parent。
- 整個子樹高度一樣 ： 對祖先節點，這個區域的黑色路徑相同。

### (四) . $Case\ 3$
#### 1. 形成情況 ：
- 加入的是樹葉點 ： cur指標必沒有子節點。
- 加入前滿足紅黑樹 ：
- parent為紅，uncle為黑下。
- parent本為leaf(才可以被加入)。
- 呈上，因為parent是樹葉，又為了對祖父要滿足紅黑樹，uncle必為nullptr。
#### 2. 解決方法
- $Step\ 1$ : 將父左旋。
- $Step\ 2$ : 再將parent(此時變cur的child)進行fix。
- 註 ： case 3只是將其變成case 2。

### (五) . 遞迴測試
#### 1. 問題一 ： 無限迴圈
- $case\ 2和3$ ： 都可以在1-2次內修正。
- $case\ 1$ ： 可能造成由祖父開始一直不滿足，造成一直進入到case1 ?

#### 2. 問題二 ： 通用性
- 證明 ： $case \ 1$通用
- 上為轉動前。
- 下為轉動後。

- 證明 ： $case \ 2$通用
- 上為轉動前。
- 下為轉動後。

## 五 . 動態操作 - 刪除
#### 1. 加入方法 ：
- $Step\ 1$ : 用BST的方法刪除。
- $Step\ 2$ : 檢查是否滿足紅黑樹的顏色特性。

#### 2. 分析方法 ：
- 分析刪除時的情況 ：
- 刪除有三種可能 ： 有一子、有二子、無子。
- 刪除二子的方法可以視為刪除一子或無子。
- 分析合不合法的情況 ：
- 刪除是黑色 : 必違法。
- 刪除是紅色 : 不用修正，因為紅紅本來就不相連，且紅色不影響黑色路徑。
- 不合法的情況 ：
- 總結 ： 由上兩點可以知道刪除一個節點違法，必為**黑色、且為一子或無子**。
- 由紅黑樹的定義為他圖上顏色，且確保刪除的事黑色下 ：