Linux 核心專題: 平衡二元搜尋樹的研究

執行人: rain20010126
解說影片連結

任務簡介

研究 Linux 核心的 red-black tree 並探討相關的資料結構。

TODO: 探討第 4 周測驗 3 的 XTree

第 4 周測驗 3 提到 XTree ，將其與紅黑樹 (Linux 核心風格)、AVL 樹進行比較: 量化分析 (含演算法分析: tree height, 要有對應的數學分析)

程式碼原理

首先可以看到 XTree 的結構組成如下，hint 可由程式碼推測出其紀錄該節點的子樹高

struct xt_node {
    short hint;
    struct xt_node *parent;
    struct xt_node *left, *right;
};

void xt_destroy(struct xt_tree *tree) : 遞迴呼叫 __xt_destroy() 將整棵樹刪除

struct xt_node *xt_first(struct xt_node *n) : 尋找節點 n 子樹中最左側的節點

struct xt_node *xt_last(struct xt_node *n) : 尋找節點 n 子樹中最右側的節點

static inline void xt_rotate_left(struct xt_node *n) : 對節點 n 進行左旋

static inline void xt_rotate_right(struct xt_node *n) : 對節點 n 進行右旋

1. 假設對 n 節點進行右旋

2. 接著進行以下操作
   ​xt_parent(r) = xt_parent(n);
   ​​​​xt_right(n) = xt_left(r);
   

3. 接著進行以下操作
   ​​​​xt_parent(n) = r;
   ​​​​xt_left(r) = n;
   

   並進行最後調整，如果 p 存在並且 n 是 p 的左子節點，則設定 l 為 p 的左子節點，反之則設定為右節點

static inline int xt_balance(struct xt_node *n) : 計算節點 n 的左右子樹差值

static inline void xt_update(struct xt_node **root, struct xt_node *n) : 計算節點 n 的左右子樹的樹高差值 hint 後，當小於負一時對其進行右旋，大於一時進行左旋，最後當 hint 值有改變或是差值為 0 ，則繼續對 n 的親代節點執行 xt_update

int xt_insert(struct xt_tree *tree,void *key) : 建立一個新節點並賦值為 key ，首先利用 __xt_find 找尋是否已經有相同 key 的節點，若有則取消插入，若不存在，則繼續判斷樹是否為空，若非空可則由 __xt_find 回傳找到 key 應擺放的位置進行插入並使用 xt_update 進行更新，若樹為空則建立一個樹並將新節點設定為根節點

int xt_remove(struct xt_tree *tree, void *key) : 此為刪除值為 key 的節點，首先利用 xt_find 呼叫 __xt_find2 找出該節點位置，接著利用 __xt_remove 來移除該節點，以下為 __xt_remove 的說明

當要刪除的節點存在右子樹時，會先找到右子樹的最左節點，並使用 xt_replace_right 來替代 del 的位置，若右子樹不存且左子樹存在時，則找到左子樹中最右邊的節點，並使用 xt_replace_left 來替代 del ，若 del 為 leaf node 則直接刪除。

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, least);
        xt_update(root, xt_right(least));
        return;
    }

    if (xt_left(del)) {
        struct xt_node *most = xt_last(xt_left(del));
        if (del == *root)
            *root = most;

        xt_replace_left(del, most);
        xt_update(root, xt_left(most));
        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(root, parent);
}

原始 XTree 與紅黑樹及 AVL 樹比較

AVl Tree 的基本定義 :

$|\mathrm{左}\mathrm{子}\mathrm{樹}\mathrm{高}\mathrm{度}-\mathrm{右}\mathrm{子}\mathrm{樹}\mathrm{高}\mathrm{度}|\le 1$

AVL tree 保證左右子樹的高度差距不大於 1，與 Xtree 相同，不同的是 AVL tree 透過平衡因子（左子樹高度減去右子樹高度）判斷，而 Xtree 則是透過結構體中的 hint 儲存子樹高度，再分別利用左子樹及右子樹的 hint 來計算高度差，最後在高度差的絕對值大於一時對二元樹進行旋轉，恢復二元樹的平衡，而此兩種二元樹在插入並進行平衡時，至多皆不大於兩次旋轉，不同的地方是，AVL tree 在旋轉後只須更新受影響節點的平衡因子，而 Xtree 則須更新該節點的親代節點至根節點的樹高，AVL tree 在搜尋、插入以及刪除節點的時間複雜度皆為

$O(\log n)$

紅黑樹的基本定義如下

1. 所有節點非黑即紅
2. 根節點(root) 為黑色
3. 所有葉節點 (leaf) 一定要為黑色的空值 (NULL)
4. 紅色節點的子節點必須為黑色
5. 從任何節點出發，其下至葉節點所經過的黑色節點數目要相同

以上性質確保了從根節點到任何葉節點的最常路徑步超過最短路徑的兩倍，另外根據 Red-Black Trees ，紅黑樹在插入的時間複雜度表現中，尋找、插入以及刪除節點的複雜度皆為

$O(\log n)$

由以上結果可以得知紅黑樹和 AVL tree 平均時間複雜度都是

$O(\log n)$，其中 AVl tree（左右子樹的高度相差不超過 1）較紅黑樹（最長路徑

$\le$ 2 倍最短路徑）平衡，在搜尋以樹高作為上限的操作下，AVL 樹會比紅黑樹略快，但由於 AVL 樹比紅黑樹要平衡，因此在平衡自身所花費的時間上 AVL 樹所花費的時間較多，所以在插入以及移除的操作下紅黑樹的表現較優，紅黑樹的優點在平衡自己時達到

$O(1)$（最多 3 次旋轉） 的複雜度

為了將 XTree 與紅黑樹以及 AVL 樹進行比較，我選擇先參考 var-x 完成的部份程式碼，包含新增 Linux 核心 red-black tree 以及修改測試程式碼 treeeint.c

commit ee87959

接著我加入了以 AVL Tree Program in C 作為 AVL tree 的實作程式，新增了判斷樹高的函式，修改其 insert 的方法，其中遇到已經存在的數值則放棄該次的插入，並新增搜尋和刪除節點的函式

commit 664f66d

Linux 核心 red-black tree 與原始 XTree 的比較結果如下，我做了 1000 個與 100 個循序輸入以及亂序輸入進行較，但在 1000 個亂序輸入中，我實作的 AVL tree 會因為過多遞迴呼叫造成 segmentation fault ，因此沒有紀錄該項結果，以下為比較實驗結果的比較

$ ./treeint 100 0
Red-Black Tree
Average insertion time : 73.230000
Average find time : 25.210000
Average remove time : 23.460000

XTree
Average insertion time : 163.420000
xtree root hint: 7
Average find time : 67.720000
Average remove time : 93.920000

AVLTree
Average insertion time : 134.070000
AVL Tree height : 7
Average find time : 54.790000
Average remove time : 17.480000

$ ./treeint 100 1
Red-Black Tree
Average insertion time : 489.770000
Average find time : 179.150000
Average remove time : 182.860000

XTree
Average insertion time : 798.090000
xtree root hint: 7
Average find time : 397.570000
Average remove time : 568.260000

AVLTree
Average insertion time : 801.780000
AVL Tree height : 7
Average find time : 320.740000
Average remove time : 89.760000

$ ./treeint 1000 0
Red-Black Tree
Average insertion time : 56.809000
Average find time : 24.193000
Average remove time : 20.390000

XTree
Average insertion time : 170.880000
xtree root hint: 10
Average find time : 151.556000
Average remove time : 128.427000

AVLTree
Average insertion time : 199.649000
AVL Tree height : 10
Average find time : 99.862000
Average remove time : 15.601000

$ ./treeint 1000 1
Red-Black Tree
Average insertion time : 60.134000
Average find time : 56.318000
Average remove time : 38.448000

XTree
Average insertion time : 189.222000
xtree root hint: 11
Average find time : 178.042000
Average remove time : 152.549000

另外我新增了 find_rbtree_height.c 來判斷循序和亂序輸入 100 和 1000 個節點的最短路徑和最長路徑，其中亂序輸入所得到的輸入順序是藉由測試程式碼 treeint.c 所得到的，與其他二元樹的輸入相同

commit d044842

Minimum depth of the red-black tree for sequential input 100 nodes: 6
Maximum depth of the red-black tree for sequential input 100 nodes: 11
Maximum depth of the red-black tree for random input 100 nodes: 7
Minimum depth of the red-black tree for random input 100 nodes: 5

Minimum depth of the red-black tree for sequential input 1000 nodes: 9
Maximum depth of the red-black tree for sequential input 1000 nodes: 17
Minimum depth of the red-black tree for random input 1000 nodes: 7
Maximum depth of the red-black tree for random input 1000 nodes: 11

可以觀察到結果與前面所提到的優缺點有衝突，我推測是因為 Linux 核心的紅黑樹較一般紅黑樹少了一層的間接操作，並擁有更好的 cache locality，而我簡單實作的 AVL tree 上有很大的改進空間，造成實際測試無法呈現出 AVL tree 的優勢

利用 perf 分析，留意其 tracepoint event。

以下我分別對紅黑樹、 AVL 樹及 Xtree 利用 perf 分析循序輸入及亂序輸入的結果

紅黑樹

Performance counter stats for './treeint 1000 0':

         1,316,162      cpu_core/cpu-cycles/                                        
             6,240      cpu_core/cache-misses/                                      

       0.002292869 seconds time elapsed

       0.002213000 seconds user
       0.000000000 seconds sys

 Performance counter stats for './treeint 1000 1':

         1,511,320      cpu_core/cpu-cycles/                                        
            16,237      cpu_core/cache-misses/                                      

       0.002588125 seconds time elapsed

       0.002529000 seconds user
       0.000000000 seconds sys

AVL 樹

 Performance counter stats for './treeint 1000 0':

         1,964,602      cpu_core/cpu-cycles/                                        
            17,099      cpu_core/cache-misses/                                      

      10.003360952 seconds time elapsed

       0.003077000 seconds user
       0.000000000 seconds sys

 Performance counter stats for './treeint 1000 1':

         1,502,094      cpu_core/cpu-cycles/                                        
            20,350      cpu_core/cache-misses/                                      

      10.101805193 seconds time elapsed

       0.001742000 seconds user
       0.000000000 seconds sys

Xtree

 Performance counter stats for './treeint 1000 0':

        14,400,138      cpu_core/cpu-cycles/                                        
            18,970      cpu_core/cache-misses/                                      

      10.008784256 seconds time elapsed

       0.008610000 seconds user
       0.000000000 seconds sys


 Performance counter stats for './treeint 1000 1':

         2,074,569      cpu_core/cpu-cycles/                                        
            17,032      cpu_core/cache-misses/                                      

      10.003112233 seconds time elapsed

       0.002830000 seconds user
       0.000000000 seconds sys

TODO: 提出 XTree 的改進方案

從資料結構的設計，探討其改進方案，融合 AVL 和 rbtree 的特性，提供對應的實驗

改進 XTree

由結構上的相似度判斷，XTree 較接近 AVL tree，XTree 利用 hint 來評估樹是否要旋轉，在AVL tree 中，為了判斷二元樹的平衡程度，這時可以利用平衡因子判別是左傾或右傾 ，計算方式為左子樹高度減去右子樹高度(深度)，當平衡因子小於 -2 或大於 2 時，需要進行旋轉，共有四種旋轉方式分別為: LL、RR、LR、RL ，而我們可以觀察到在 XTree 中只有兩種旋轉方式，可以看到下面的說明，在插入節點 n 後會由節點 n 往上檢查左右子樹相差有無大於 1 ，檢查到節點 a 時發現其左子樹高較右子樹高 2，因此會對節點 a 進行右旋

對節點 a 進行旋轉後如下，可以發現節點 a 的左右子樹差沒有減少

因為 XTree 同樣是利用一個節點的左右子樹差來進行旋轉，使用 AVL Tree 的旋轉方式可以解決以上問題，也就是分成不平衡的類型 RR, RL, LR, LL 四種，並按照不同的情況進行相對應的旋轉，以下是修改的差異

     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);
     }

接著我使用與先前相同的實驗方式對修正後的 XTree 進行比較，以下是比較的結果呈現

$ ./treeint 100 0
XTree
Average insertion time : 481.930000
xtree root hint: 7
Average find time : 292.390000
Average remove time : 531.520000

$ ./treeint 100 1
XTree
Average insertion time : 182.860000
xtree root hint: 6
Average find time : 264.140000
Average remove time : 115.140000

$ ./treeint 1000 0
XTree
Average insertion time : 181.901000
xtree root hint: 10
Average find time : 89.020000
Average remove time : 99.623000

$ ./treeint 1000 1
XTree
Average insertion time : 199.487000
xtree root hint: 10
Average find time : 114.791000
Average remove time : 150.443000

補上數學分析。

數學分析
AVL tree 在樹高的表現上優於紅黑樹是由於 AVL 樹保證了左右子樹高度差最多相差一，也就是說一個具有 n 個節點的 AVL　樹，其高度最高為

$O(\log n)$ ，而紅黑樹並沒有以上較嚴格的限制，其核心性質是保證沒有兩個連續的紅色節點，並且對於每個節點到其葉子節點的黑色節點數量相同，因此紅黑樹的高度會較 AVL 樹來的更高，一個有 n 個節點的紅黑樹的高度最高為

$2({\log }_2(n+1))$

至於 紅黑樹在插入以及刪除節點的表現下會優於 AVL tree 的原因是由於 AVL tree 的限制較嚴格，因此會需要花費較多的旋轉次數來達到左右子樹相差不超過一的要求

最後從以上亂數輸入的實驗結果中可以發現，相比於修改前的結果，修改過後的 Xtree 在樹高部份（Xtree hint）都有減少，在亂序輸入 100 個節點中 hint 從 7 下降為 6 ，而在亂序輸入 1000 個節點中 hint 從 11 下降為 10 ，另外我實際建立一個 Xtree 來更好的比較修改前及修改後樹的自平衡能力，其中我依序插入以下節點 [1000, 500, 300, 0, 400, 350, 450, 425, 475, 460]後

修正前的 XTree 結構如下

修改後的結構如下

修改前的樹高：6
修改後的樹高：4

透過以上結果可以發現解決了先前我們所提到的無效旋轉的問題，使 XTree 更加平衡，同時因為樹高的減少，在搜尋所花費的時間上也有大幅下降