# 紅黑樹
### 解析紅黑樹（ RED-BLACK TREE ）

- #### 概述
- RBtree 是一種特別的平衡樹，既然身為平衡樹它在新增、刪除、搜尋的複雜度都能維持在 O(log n)，而它的特別之處在於樹高 h 的定義與一般平衡樹不同(用的是 black height )，此特別之處讓紅黑樹在重新平衡所需的"代價"較其他平衡樹小
:::info
黑高度( black height) bh(x):從 x 到任何一個它的子孫葉子 leaf 的路徑上，遇到的 black node 個數(不包含自己）
:::
- #### 定義
- 
### 插入( Insertion )
- 以二元搜尋樹的方法新增節點，每次新增完後都需要在檢查整棵樹時否依然符合上述紅黑樹的性質，為了減少違反性質的可能，插入的節點均設定為"紅色"，此作法能使得插入節點後的 black height 不改變
- 以下將"插入"的情形歸納為五類，根據不同插入狀況紅黑樹需做不同的調整（圖中插入節點為 N ，N 的父節點為 P ，N 的祖父為 G ，N 叔叔為 U ）
1. 新節點 N 位於樹跟上
- 在這種情形下，我們只需把 N 改為黑色即可
2. 新節點父親 P 為黑色
- 在此情況下則不需要做任何調整
3. 父親 P 及 叔叔 U 均為紅色
- 在此情況下需把祖父 G 換成紅色，P 及 U 節點換成黑色，特別要注意的是 G 節點換成紅色後可能不符合紅黑樹性質，這時候應該將 G 當作新增節點丟回 case 1 重新驗證
4. 父節點 P 是紅色，叔叔 U 是黑色或缺少
- 此情況又可以在細分成四種兩兩對稱的情況，而其種兩類屬於 case 5 ，case 4 分別為 **1.** N 為 P 的右節點且 P 為 G 的左節點 **2.** N 為 P 的左節點且 P 為 G 的右節點
- 對 P 做左旋(右旋）
- case 4 的目的只是讓樹變成 case 5 的樣子，因此做完 case 4 後還尚未符合性質
5. 父節點 P 是紅色，叔叔 U 是黑色或缺少
##### a. N 為 P 的左子節點且 P 為 G 的左子節點
##### b. N 為 P 的右子節點且 P 為 G 的右子節點
對 G 做右旋(左旋），再將 P 、G 顏色對調

### 刪除（ Remove )
- 要刪除的節點原本分為三類
**a.** 有兩個非葉子兒子
**b.** 有一個非葉子兒子
**c.** 兩個兒子均為葉子
:::info
但實際操作上我們可以把情況 a. 視為情況 b.或者是情況 c. 。在情況 a. 中刪除某一個節點後要麼是拿該節點左分支中最大的節點 N 來補，否則就是拿該節點右分支中最小的節點 N 來補，我們只要將補上的節點顏色塗成和原本刪除的一樣，如此操作後就能將原本的刪除動作看成刪除補上的節點 N ，也因為刪除的節點 N 至多只有一個非葉子的兒子或者兩個兒子均為葉子，因此情況 a. 就被我們轉換成情況 b. 或情況 c. 。
:::
- ## 刪除帶有唯一兒子的節點
#### a. 刪除節點為紅色
- 若刪除的節點為紅色的，刪除後並不會影響樹的"黑高"，因此我們只需要把其兒子節點接上它的父親即可

#### b. 刪除的節點是黑色，而它唯一的兒子是紅色的
- 遇到此種情況我們只需要將其紅色兒子塗成黑色後接上被刪除的節點的父親即可
:::info
實際操作上部可能遇到刪除節點唯一非葉子兒子為黑的情行，若唯一非葉子兒子為黑，則刪除節點的兩分支高必定不相同
:::
- ## 刪除的節點帶有兩個葉子兒子（ N 表示刪除節點後補上的節點）
### 1. N 是新的根
- 在這種情況下不用做任何旋轉或換色
### 2. S 是紅色( P 則一定為黑色）
- 在這種情況下我們在 P 做左旋轉，並且把 S、P的顏色對調，完成後我使 N 的父親變為紅色，且 N 得兄弟變為黑色，做完這樣的調整之後可以接著在情況 4、5、6處理
### 3. P 是黑色且 S、S 的兒子均為黑色
- 在這種情況下我們簡單重繪 S 為紅色，這樣的操作使得對於 P 來說的所有路徑"黑高"相同，但經過 P 的路徑則並未調整，所以我很還需要將 P 遞迴帶進情況一重新檢查 
### 4. S 和 S 的兒子都是黑色，但 P 為紅色
- 在這種情況下我們只要簡單的交換 S 及 P 得顏色就能使得紅黑樹完整
:::info
情況二做的事就是為了使 N 有個紅色的父節點以及黑色的兄弟，進而在情況4、5、6調整
:::
### 5. S 是黑色，且 S的左兒子是紅色、右兒子是黑色， N 為 S 父親得左兒子
- 對 S 做右旋轉，且將 S 繪成紅色、 S 原本的左兒子塗成黑色
:::info
當 S 是黑色且 S 的兒子為一黑一紅時有兩個可能，分別為左兒子是黑色或者右兒子是黑色，情況五只是為了將這兩種狀況統一成一種，在情況六中才真的有調整紅黑樹並使其符合定義
:::
### 6. S 是黑色，且 S 的右兒子是紅色，而 N 為 S 父親的左兒子
- 對 S 的父親 P 做左旋轉，接著把 S 的右兒子塗成黑色，最後將 S 及 P 的顏色做交換。經過這些步驟可使得經過 N 的路徑都增加一個黑色節點，剛好可以抵銷刪除的黑色節點

> **參考** [維基百科](https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91)

### RBtree v.s AVLtree
- 相同點：兩者皆為平衡樹，因此新增、刪除所需時間複雜度均為 O(logN)
- 相異點：
1. AVLtree 需要額外 O(logN) 的位置去儲存紀錄平衡的變數，相較之下紅黑樹只需要一個 bit 去紀錄是紅色或者黑色，可以用其他變數的某個位置加以紀錄
2. RBtree 保證能在 O(1) 的時間內完成 rotation

### 解析程式碼
- 想要了解 rbtree.c 要先找到 .c 檔中用到的兩個標頭檔 rbtree.h 及 rbtree.augmented.h ， 讀懂 .c 檔中運用到的具集還有函式的定義，了解定義之後再去看 rbtree.c 會發現其實裡頭就只是實踐 rbtree 的新增、刪除等等，邏輯和前一部分解釋的都差不多，最難的還是了解 Linux 內核中為了增加效能所用的一些小技巧而這些小技巧大部分都實踐在標頭檔

- 首先我們先來看看紅黑樹中的節點在 Linux 內核中是如何定義的

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

觀察這段程式碼我們可以發現，它運用了三個參數紀錄了 re_node 必要的四樣資訊，其中它把 parent 和 color 的資訊紀錄在一個 unsigned long 型態的變數內， __rb _parent_color 的第 0 個 bit 紀錄的是顏色而其他紀錄的是 parent 所在的地址 詳細解說參考[這裡](http://tinylab.org/rbtree-part1/#%E5%89%8D%E8%A8%80%E4%B8%80%E6%9D%AF%E8%8C%B6%E6%82%A0%E9%97%B2%E7%9C%8B%E4%BB%A3%E7%A0%81)

- 另一個 rbtree 在 linux 核心比較特別的地方是 node 的變量 augment 不是在 node 的 struct 裡面的成員，因此在 .c 檔中定義的插入、刪除 node 的函式中都有關於 augment 的變數，也有很多針對 augment 作用的 function
:::warning
如果想要讀懂有關 augment 的函式還必須先看過其他標頭檔...
:::
### RBtree 在 Linux 上的應用
1. anticipatory、deadline、CFQ I/O 調度都是使用 RBtree 進行請求追蹤
2. CD/DVD 驅動、管理
3. 高精度計時器使用 RBtree 組織定時請求
4. EXT3 文件系統使用 RBtree 來管理目錄
5. 虛擬存儲管理系統也是用 RBtree 進行 VMAs 的管理
**參考** [這裡](https://blog.csdn.net/zhangchiytu/article/details/8471202)

###### tags: `OS`