---
# System prepended metadata

title: 'Data Struct - Tree : Red Black Tree'
tags: [Data Struct - Tree]

---

# 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。
![](https://i.imgur.com/NFiTbop.png =400x)

#### 2. 解決方法
- $Step\ 1$ : 將parent，uncle塗黑。
- $Step\ 2$ : 將祖父塗紅。
- $Step\ 3$ : 對祖父進行fix。
![](https://i.imgur.com/fJDQT3M.png =300x)![](https://i.imgur.com/nn03rVx.png =300x)

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

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

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

#### 2. 問題二 ： 通用性
- 證明 ： $case \ 1$通用
  - 上為轉動前。
  - 下為轉動後。 
 ![](https://i.imgur.com/KEAIE8D.png =300x)![](https://i.imgur.com/hNJdxOq.png =300x)


- 證明 ： $case \ 2$通用
  - 上為轉動前。
  - 下為轉動後。 
![](https://i.imgur.com/hn1TXJr.png =300x)![](https://i.imgur.com/ppAfr6G.png =300x)


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

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




  
