## Linux 核心專題: 平衡二元搜尋樹的研究
> 執行人: ICARUSHERALD96500
[解說影片連結](https://youtu.be/3valbZZZ8gs)
## 任務簡介
研究 Linux 核心的 red-black tree 並探討相關的資料結構。
## TODO: 探討第 4 周測驗 3 的 XTree
> 第 4 周測驗 3 提到 XTree ，將其與紅黑樹 (Linux 核心風格)、AVL 樹進行比較: 量化分析 (含演算法分析: tree height, 要有對應的數學分析)
>
### 第四週測驗題 測驗 3
:::danger
不要急著列出程式碼並逐行解釋，你可能會淪為「舉燭」的下場。
你應該揣摩程式設計者的思維，羅列 XTree 的關鍵決策、特性，還有相關的取捨等等。
你是個研究生，就該用有效的研究方法來解釋工程領域的多項事務。
>Xtree 似乎在其他地方並沒有說明該樹的機制，因此原想透過解釋程式碼來說明其實作機制，但我應該用圖說明其左右旋後無法平衡樹高的問題，確實不該逐行解釋。
> $\to$ 提出數學分析，回去翻閱 The Art of Computer Programming 一類的經典著作
> $\to$ 若你因為無法 Google 搜尋到某個東西，然後就無從判斷，這樣還算具備理工素養嗎？我們之所以用高標準要求自己，就是在這樣未知的場合中，得以扎實地拆解、分析、判斷，從而提出改進方案。
> $\to$ 從平衡二元樹的理論開始回顧
:::
**Xtree** 是一種同時兼具 AVL 數與紅黑樹特性的自平衡二元樹樹狀結構，其中一項特點為刪除節點的速度較優，利用 hint 值評估樹平衡與否，且僅在 `xt_node` 被呼叫時更新。下列程式碼說明其移除解點機制
```c
static void __xt_remove(struct xt_node **root, struct xt_node *del)
{
if (xt_right(del)) {
struct xt_node *least = xt_first(xt_right(del));
if (del == *root)
*root = least;
xt_replace_right(del, AAAA);
xt_update(root, BBBB);
return;
}
if (xt_left(del)) {
struct xt_node *most = xt_last(xt_left(del));
if (del == *root)
*root = most;
xt_replace_left(del, CCCC);
xt_update(root, DDDD);
return;
}
if (del == *root) {
*root = 0;
return;
}
/* empty node */
struct xt_node *parent = xt_parent(del);
if (xt_left(parent) == del)
xt_left(parent) = 0;
else
xt_right(parent) = 0;
xt_update(EEEE, FFFF);
}
```
首先提及其中所使用的函式說明:
* `xt_root(r)` 找出節點 r 的父節點
* `xt_left(n)` 功能為找出節點 n 底下最小的節點，也就是最左邊的極點。巨集定義:`#define xt_left(n) (n->left)
`
* `xt_right(n)` 功能為找出節點 n 底下最大的節點，也就是最又邊的節點。巨集定義:`#define xt_right(n) (n->right)
`
* `xt_replace_right(n, r)` 使用右子樹的節點 r 來調換原本節點 n
* `xt_replace_right(n, l)` 使用左子樹的節點 l 來調換原本節點 n
* `xt_update(n, m)` 更新被節點操作後的樹，並根據 `hint` 判定該樹樹否平衡，而決定後續是否進行旋轉。雖然該機制與 AVL tree 雷同。但差異在於 xt_node 之計算方式為其左右節點 `hint` 最大值再 +1，並且僅有在 `xt_update(n,m)` 被呼叫時才更新。而每個節點的 hint 值雖用來判斷樹是否平衡，但是該值卻不用與實際上最長子節點的練長相同。如此一來，便可以減少在每次樹的節點操作後進行更镡時 `xt_update(n, m)` 所需重新計算高度的工作量。
* `xt_rotate_right`:
```c
static inline void xt_rotate_left(struct xt_node *n)
{
struct xt_node *l = xt_left(n), *p = xt_parent(n);
xt_parent(l) = xt_parent(n);
xt_left(n) = xt_right(l);
xt_parent(n) = l;
xt_right(l) = n;
if (p && xt_left(p) == n)
xt_left(p) = l;
else if (p)
xt_right(p) = l;
if (xt_left(n))
xt_lparent(n) = n;
}
```
```graphviz
digraph Tree {
graph[ordering=out]
p -> n
n -> l
n -> r
l -> A
l -> B
label=origin
}
```
```graphviz
digraph Tree {
graph[ordering=out]
p -> l
l -> A
l -> n
n -> B
n -> r
}
```
- `xt_rotate_left`:
```graphviz
digraph Tree {
graph[ordering=out]
p -> n
n -> l
n -> r
r -> A
r -> B
label=origin
}
```
```graphviz
digraph Tree {
graph[ordering=out]
p -> r
r -> n
r -> B
n -> l
n -> A
}
```
由上述的兩個操作發現，xtree 不論進行左旋或右旋都無法在情況下平衡樹高。
:::danger
提供相關的數學分析。
:::
XTree 的最壞情況樹高與普通的二元搜尋樹相似，取決於節點的插入順序。在沒有特殊的平衡措施下，最糟糕情況下可能形成一個高度接近於線性的右斜樹。例如，如果按照特定的插入順序導致每次插入的節點都比前一個節點大（或小），則最終形成的樹可能高度接近於 $𝑛$ ，等同於節點的數量。
### 與 AVL tree 、 rbtree 比較
**AVL tree** 為確保平衡，利用平衡因子判斷其子樹高差距，再決定是否旋轉。當為平衡時，必滿足以下條件：$左子樹高 - 右子樹高 \in \left(-1,0,1\right)$ 。xtree 與 AVL tree 類似，利用 `hint` 紀錄子樹高，在 `xt_update` 時計算高度差，當左右差異大於一時，進行旋轉。但從程式碼中可以發現，其僅對平衡因子 `b` 進行大於一或小於一的判斷，進而右旋或左旋。AVL tree 相較之下，有 LL、RR、LR、RL 四種旋轉方式。利用前面提及 xtree 單純使用左或右旋無法解決平衡樹高的情境下。僅需要使用右左或左右旋便可解決。
初始結構：
```graphviz
digraph Tree {
graph[ordering=out]
p->n
p->r
n->A
n->l
l->B
label=origin
}
```
先對 n 左旋：
```graphviz
digraph Tree {
graph[ordering=out]
p->l
p->r
l->n
l->B
n->A
}
```
再對 p 右旋：
```graphviz
digraph Tree {
graph[ordering=out]
l->n
l->p
n->a
p->b
p->r
}
```
如此一來，變完成樹高平衡。由於樹高對搜尋的效能有所影響，因此簡單討論 AVL tree 的樹高。在平衡的情況下，假設樹高為 h，n(h)為節點最少的情況下樹高與節點的數量關係：$n(h) = n(h-1)+n(h-2)+1$
在 AVL tree 樹高。可以發現該關係式與費氏數列相似，因此使用該特性推算第 k 項的數值：$\phi^k/\sqrt{5}$。基於該相似特性，推算 $n(h)$ 也是如此，只不過是把 $\sqrt5$ 代換為其他常數，$n(h)\approx k\phi^h$。即便再糟糕的情況下都滿足 $\phi ^h\leq n$，取對數後樹高即為 $h\leq log(n)/log(\phi)\approx1.44\times log(n)$。
**rbtree** 規則：
1. 節點只能是紅或黑色
2. 根節點必為黑色
3. 葉節點必為黑色
4. 紅色節點的子節點必為黑色
5. 從任一節點到其葉節點，途中路徑上的黑色節點數目相同
滿足上述規則的二元樹，相比一般的二元樹更能保持平衡性，往後套用二元樹的算法來查找資料時能更快速、方便地到達目的地，套用運算的時間複雜度為 O(log n)，這是因為紅黑樹保證最長路徑不會超過最短路徑的兩倍，最短路徑為葉節點到根節點路徑上全部的節點均為黑色，而最長路徑為黑紅相間。
為了 rbtree 在節點操作後，仍滿足 rbtree 的條件。因此，有'變色'與'旋轉'兩種操作。在樹高上，rbtree 與 AVL tree 西相比，因為後者使用平衡因子所以對樹高差異限制嚴格，樹高為 $1.44\times log(n)$。反觀 rbtree 平衡機制是利用上述的五條規則，因此樹高較高。因為最長的路徑，可以視為在最短路徑（即路徑上節點均為黑色）間隔插入紅色節點。在 rbtree 樹高上，假設黑高為 bh，那該數至少包含 $2^{bh}-1$ 個節點（即不存在紅色節點）。利用紅色節點不會連續的條件，可以視為紅色節點被間隔插入，故最高樹高為兩倍的黑高（$h=2 \times bh$）。假設一顆 rbtree 有 n 個節點，則 $2^{bh}-1\leq n$，重新整理後可得。 $bh \leq log(n+1)$，故在樹高在最糟的情況下 $h \leq 2 \times log(n+1)$。在 $n$ 極大的情況下便近似為 $2 \times log(n)$。
對比 rbtree 與 AVL tree 在樹高上的差異後，rbtree 因為平衡規則較寬鬆，樹高較高。所衍伸的缺點就是雖然在平均狀況下複雜度仍為 $log(n)$，但最糟的情況下畢竟樹高較高，搜尋的速度稍較 AVL tree 慢。
xtree 因為前面與 AVL tree 作比較時發現，其無法有效的利用程式碼原始的單純左右旋達到平衡樹高，容易出現歪斜的情況，從而增加樹高，減慢在最糟的情況下的搜尋速度。
## TODO: 提出 XTree 的改進方案
> 從資料結構的設計，探討其改進方案，融合 AVL 和 rbtree 的特性，提供對應的實驗
xtree 原始程式碼中，不如 AVL tree 有四種旋轉，僅存在兩種旋轉。在遭遇上述所提及的部份樹狀結構時，無法平衡樹狀結構。對以下程式碼修改，使的 xtree 同樣擁有 4 種旋轉：
```diff
if (b < -1)
{
/* leaning to the right */
+ if (xt_balance(xt_right(n)) > 0)
+ xt_rotate_left(xt_right(n));
if (n == *root)
*root = xt_right(n);
xt_rotate_right(n);
}
else if (b > 1)
{
/* leaning to the left */
+ if (xt_balance(xt_left(n)) < 0)
+ xt_rotate_right(xt_left(n));
if (n == *root)
*root = xt_left(n);
xt_rotate_left(n);
}
```
當從 `xt_balance` 回傳左右子樹高的差值 b，除了原始程式碼中判斷其是否在 -1 到 +1 之間外，還必須進一部判斷該節點的子樹是否需要先旋轉。例如當 `b<-1` 也就是左子樹高小於右子樹高的情況下，還需要進一步判定其右子樹是否需要先被旋轉。也就是 `xt_balance(xt_right(n))>0` 條件為'真'時，代表 `xt_right(n)` 的右子樹較高，需要先對其左旋。最後再對 n 右旋。反之亦然。
對於為什麼認為樹高不平衡對於 xtree 來說是缺點? 是以搜索的角度切入，若是一顆 complete binary tree 其搜索複雜度為 $O(log(n))$。對於原本的 xtree，其樹高會如同上面拿 xtree 與 AVL tree、rbtree 闡述的，隨節點插入，該樹會越發歪斜，而越深則搜索越慢。但若是為了如 AVL tree 為了維持子樹高平衡，就需要加入更多機制在插入節點時進行檢查與旋轉，操作的成本就會增加。而因為 xtree 這些機制較少，因此插入節點的成本較低。所以我推測 xtree 的設計初衷是為了因應需要進行大量節點插入/刪除操作，而捨棄搜索速度所做出的權衡。
:::danger
補上數學分析
:::
在上述的程式碼修改後，xtree 的樹高平衡機制幾乎無異於 AVL tree，差別僅在於 xtree 是透過在每一節點利用 `hint` 紀錄樹高，而不是在一開始就將左右子樹高的相差先計算好。並且僅在 `xt_node` 被呼叫時進行平衡狀態更新。有了以上對數高平衡的修正，xtree 的結後會趨近 complete binary tree，其中，對於該樹的第 $i$ 個節點會在第 $floor(\log_2(i))$ 層。而對於邊條數量計算上，深度為 $d$ 的節點從根結點到該節點會共有 $d$ 個邊條，也就是說可以透過計算第 $i$ 個節點的深度，推溯出跟節點到第 $i$ 節點的邊數為 $floor(\log_2(i))$。所以總共 $n$ 個節點就會有 $\sum^{n}_{i=1} floor(\log_2(i)) = O(n \times log(n))$ 個邊條。
下面圖解其機制，首先考慮初始狀態的 xtree
```graphviz
digraph Tree {
graph[ordering=out]
n->xt_left
n->xt_right
xt_left->A
xt_left->B
B->C
}
```
使用 `xt_balance(n)` 可以獲得左右子樹高的相差，即平衡因子，在這裡為 $3-1=2$，沒有落在正負 1 的範圍。引此 `b>1` 判斷式為真。進入 `xt_balance(xt_left(n)<0)` 的判斷當中。而 `xt_left` 節點的子樹高所得的平衡一因子為：$1-2＝-1$，該判斷式同為真。故觸發 `xt_rotate_right(xt_left)` 對 `xt_left` 進行左玄。完成該步驟的 xtree 如下：
```graphviz
digraph Tree {
graph[ordering=out]
n->B
n->xt_right
xt_left->A
B->xt_left
B->C
}
```
最後再進行 `xt_rotate_right(n)` n 右旋：
```graphviz
digraph Tree {
graph[ordering=out]
n->C
n->xt_right
xt_left->A
B->xt_left
B->n
}
```
這樣變可以完成與 AVL tree 相同的旋轉機制，以確保結構平衡。
Sign in with Wallet
Connect another wallet