# Linux 核心的紅黑樹程式碼解讀
閱讀 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E7%B4%85%E9%BB%91%E6%A8%B9%E5%AF%A6%E4%BD%9C)的過程中遇到了一些理解上的困難，於是以下去讀了 Linux 核心中的程式碼：
- [lib/rbtree.c](https://github.com/torvalds/linux/blob/master/lib/rbtree.c)
- [linux/include/linux/rbtree_augmented.h](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_augmented.h)
並且在閱讀過程中發現了註解的問題，向 Linux 核心提交了 [patch](https://lkml.org/lkml/2025/4/3/677)，看起來沒有回應
以下有些地方，我判斷程式碼並沒有幫助理解就只留註解。
## 刪除節點
### `rb_erase`
傳入要刪除的節點 `node` 和根，首先會呼叫 `__rb_erase_augmented`，並且它會回傳不平衡的節點，如果是平衡的就回傳 `NULL`。如果需要平衡會呼叫 `____rb_erase_color`。
```cpp
void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *rebalance;
rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
if (rebalance)
____rb_erase_color(rebalance, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase);
```
### `__rb_erase_augmented`
它分成以下幾種情況：
- `case 1`：`node` 有一個以下的子節點
- `case 2`：`node` 的 successor（中序中的下一個）是他的右子節點
- `case 3`：`node` 的 successor 不是他的右子節點（它右子樹中的最左邊的節點不是他的右子節點）
以下逐段解釋：
`child` 是 `node` 的右子節點，`tmp` 是他的左子節點。如果 `tmp` 是 `NULL` 的話，代表它一定是只有右子節點或者是沒有子節點（`case 1`）。所以會將右子節點提上來代替掉 `node`。並且，如果 `node` 的右子節點不是 `NULL` 的話，那因為 `node` 沒有左子節點，所以 `node` 的右子節點一定是紅色，而 `node` 一定是黑色。因為右子節點被提上來之後顏色會被設定成 `node` 原本的顏色，所以是平衡的。另一種情況是當 `node` 的右子節點是 `NULL` 的情況，那如果 `node` 本來是紅色就是平衡，如果它本來是黑色的話就不平衡，回傳他的親代節點。
這裡要題的一點是，linux 中紅黑樹的實作上，節點的顏色和親代的節點是一起存的，放在 `__rb_parent_color`。
```cpp
struct rb_node *child = node->rb_right;
struct rb_node *tmp = node->rb_left;
struct rb_node *parent, *rebalance;
unsigned long pc;
if (!tmp) {
/*
* Case 1: node to erase has no more than 1 child (easy!)
*
* Note that if there is one child it must be red due to 5)
* and node must be black due to 4). We adjust colors locally
* so as to bypass __rb_erase_color() later on.
*/
pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, child, parent, root);
if (child) {
child->__rb_parent_color = pc;
rebalance = NULL;
} else
rebalance = __rb_is_black(pc) ? parent : NULL;
tmp = parent;
}
```
接下來是只有左子節點的情況，也是 `case 1`。同樣把左子節點提上來。而根據上面的討論，它一定是平衡的。
```cpp
else if (!child) {
/* Still case 1, but this time the child is node->rb_left */
tmp->__rb_parent_color = pc = node->__rb_parent_color;
parent = __rb_parent(pc);
__rb_change_child(node, tmp, parent, root);
rebalance = NULL;
tmp = parent;
}
```
接下來是一個很長的 else，我們把裡面的東西分開來講：
這裡首先講一下以下這個 if-else 會達成的結果，`node` 會被他的 successor 替代， `successor` 會是 `node` 的 successor，而 `child2` 會是 `successor` 原本的右子結點，`parent` 會是 `child2` 再做完操作後的親代節點（如果 `child2` 是 `NULL` 的話，不精準的來說就是把它視為一個節點的話它被設為誰的子節點）。
如果 `node` 的右子節點的左子節點是 `NULL` 的話，那代表他的 successor 是他的右子節點（`case 2`），於是將它提上來。這個時候，會發現 `child2` 的親代節點是 `successor`，而 `parent` 被設成 `successor`。
```cpp
struct rb_node *successor = child, *child2;
tmp = child->rb_left;
if (!tmp) {
/*
* Case 2: node's successor is its right child
*
* (n) (s)
* / \ / \
* (x) (s) -> (x) (c)
* \
* (c)
*/
parent = successor;
child2 = successor->rb_right;
augment->copy(node, successor);
}
```
接下來，會先在右子樹中一直往左走，最後 `successor` 會是 `node` 的 successor，而 `parent` 會是他的親代節點，`child2` 則是 `successor` 的右子節點。然後會把 `child2` 變成 `parent` 的左子節點，然後把 `successor` 填到 `node` 的位置，並且把他的右子樹變成 `successor` 的右子樹。
```cpp
else {
/*
* Case 3: node's successor is leftmost under
* node's right child subtree
*
* (n) (s)
* / \ / \
* (x) (y) -> (x) (y)
* / /
* (p) (p)
* / /
* (s) (c)
* \
* (c)
*/
do {
parent = successor;
successor = tmp;
tmp = tmp->rb_left;
} while (tmp);
child2 = successor->rb_right;
WRITE_ONCE(parent->rb_left, child2);
WRITE_ONCE(successor->rb_right, child);
rb_set_parent(child, successor);
augment->copy(node, successor);
augment->propagate(parent, successor);
}
```
接下來是上面那個 if-else 外面的東西，是兩邊都要有的操作：
首先是一些共同的細節操作，然後值得是，如果 `child2` 不是 `NULL` 的話，因為它沒有平輩節點，所以它一定是紅色的，這代表 `successor` 一定是黑色的，所以當我用 `successor` 填補了 `node` 的空格後，再把 `child2` 設為黑色，那它一定是平衡的（它正好填補了失去 `successor` 而減少的那個黑色）。而如果 `child2` 是 `NULL` 的話，如果 `successor` 是紅色就是平衡的，如果 `successor` 是黑色就會少一個黑色，所以回傳 `parent`。
```cpp
tmp = node->rb_left;
WRITE_ONCE(successor->rb_left, tmp);
rb_set_parent(tmp, successor);
pc = node->__rb_parent_color;
tmp = __rb_parent(pc);
__rb_change_child(node, successor, tmp, root);
if (child2) {
rb_set_parent_color(child2, parent, RB_BLACK);
rebalance = NULL;
} else {
rebalance = rb_is_black(successor) ? parent : NULL;
}
successor->__rb_parent_color = pc;
tmp = successor;
```
最後回傳 `rebalence`。
### `____rb_erase_color`
這個函式最重要的兩個變數是 `node` 和 `parent`，代表著是現在處理的節點和他的親代節點，`node` 下面的所有路徑都比其他路徑少一個黑色。然後 `node` 一開始設為 `NULL`，之後會進行分析。
```cpp
struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
```
接下來，使用一個 `while (true)` 一直執行到中止。然後我們來分析迴圈中的內容。首先，它會依照 `node` 是 `parent` 的左子節點還是 `parent` 的右子節點分成兩類（`NULL` 分在左子節點那類），然後右子節點的操作和左子節點只是倒反過來而已，這裡只解釋左子節點的部份：
首先，`sibling` 是 `node` 的平輩節點。
以下會分成 4 種情況：
- `case 1`：`sibling` 是紅色的
- `case 2`：`sibling` 是黑色的，且 `sibling` 的兩個子節點都是黑色或 `NULL`
- `case 3`：`sibling` 是黑色的，且 `sibling` 右子節點是黑色或 `NULL`，且 `sibling` 的左子節點是紅色的
- `case 4`：`sibling` 是黑色的，且 `sibling` 的右子節點是紅色的
以下把 `sibling` 的左子節點叫做 `sl`，而右子節點叫做 `sr`，而原始註解中使用大小寫來代表顏色，我判斷在我可以多做說明的情況下這對理解沒有益處，所以不使用這種標示。
首先是 `case 1`，因為 `sibling` 是紅色的，所以 `sr` 和 `sr` 必然是黑色的且 `parent` 必然是黑色。我們對 `parent` 和 `sibling` 做左旋操作，並且把 `parent` 設為紅色，`sibling` 設為黑色（相當於在 2-3-4 樹上做左旋），然後 `node` 的平輩節點會變成黑色的，變成其他的幾種情況。
```cpp
/*
* Case 1 - left rotate at parent
*
* P S
* / \ / \
* N s --> p Sr
* / \ / \
* Sl Sr N Sl
*/
```
然後是 `case 2`，`sibling` 和 `sl`、`sr` 都是黑色或 `NULL`，於是就把 `sibling` 變成紅色，讓右子樹也少一個黑色。接下來，如果 `parent` 是紅色的話就把它變黑色，結束迴圈。如果 `parent` 是黑色的話，就把 `node` 變成 `parent`，`parent` 變成他的親代節點，繼續下個迴圈。
```cpp
/*
* Case 2 - sibling color flip
* (p could be either color here)
*
* (p) (p)
* / \ / \
* N S --> N s
* / \ / \
* Sl Sr Sl Sr
*
* This leaves us violating 5) which
* can be fixed by flipping p to black
* if it was red, or by recursing at p.
* p is red when coming from Case 1.
*/
```
然後 `case 3`，`sl` 一定是紅色的，而 `sr` 是黑色或 `NULL`，這個時候對 `sl` 和 `sibling` 進行右旋操作。這裡的註解雖然沒有提及，但是我的判斷是這裡我們可以想像 `sl` 被變成了黑色、`sibling` 變成了紅色，只是因為在 `case 4` 的操作結果上會造成相同的結果，所以這裡可以不用變顏色。且這樣同時也符合在 2-3-4 樹上的右旋操作。
```cpp
/*
* Case 3 - right rotate at sibling
* (p could be either color here)
*
* (p) (p)
* / \ / \
* N S --> N sl
* / \ \
* sl sr S
* \
* sr
*
```
在這裡，我發現 `sr` 一定會是黑色的，但是註解中卻使用小寫的 `sr`，於是提交了 [patch](https://lkml.org/lkml/2025/4/3/677)。
完成上面這個操作後，`parent` 的右子節點會變成新的 `sibling`，並且進入 `case 4`。
最後是 `case 4`，代表 `sr` 是紅色的狀況，這個時候對 `parent` 和 `sibling` 做左旋操作，把 `sibling` 變成 `parent` 原本的顏色，把 `parent` 變成黑色，並且把 `sr` 變成黑色。
```cpp
/*
* Case 4 - left rotate at parent + color flips
* (p and sl could be either color here.
* After rotation, p becomes black, s acquires
* p's color, and sl keeps its color)
*
* (p) (s)
* / \ / \
* N S --> P Sr
* / \ / \
* (sl) sr N (sl)
*/
```
Sign in with Wallet
Connect another wallet