Try   HackMD

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

執行人: ICARUSHERALD96500
解說影片連結

任務簡介

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

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

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

第四週測驗題 測驗 3

不要急著列出程式碼並逐行解釋,你可能會淪為「舉燭」的下場。
你應該揣摩程式設計者的思維,羅列 XTree 的關鍵決策、特性,還有相關的取捨等等。

你是個研究生,就該用有效的研究方法來解釋工程領域的多項事務。

Xtree 似乎在其他地方並沒有說明該樹的機制,因此原想透過解釋程式碼來說明其實作機制,但我應該用圖說明其左右旋後無法平衡樹高的問題,確實不該逐行解釋。

提出數學分析,回去翻閱 The Art of Computer Programming 一類的經典著作
若你因為無法 Google 搜尋到某個東西,然後就無從判斷,這樣還算具備理工素養嗎?我們之所以用高標準要求自己,就是在這樣未知的場合中,得以扎實地拆解、分析、判斷,從而提出改進方案。
從平衡二元樹的理論開始回顧

Xtree 是一種同時兼具 AVL 數與紅黑樹特性的自平衡二元樹樹狀結構,其中一項特點為刪除節點的速度較優,利用 hint 值評估樹平衡與否,且僅在 xt_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, 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:
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;
}







Tree

origin


p

p



n

n



p->n





l

l



n->l





r

r



n->r





A

A



l->A





B

B



l->B











Tree



p

p



l

l



p->l





A

A



l->A





n

n



l->n





B

B



n->B





r

r



n->r





  • xt_rotate_left:






Tree

origin


p

p



n

n



p->n





l

l



n->l





r

r



n->r





A

A



r->A





B

B



r->B











Tree



p

p



r

r



p->r





n

n



r->n





B

B



r->B





l

l



n->l





A

A



n->A





由上述的兩個操作發現,xtree 不論進行左旋或右旋都無法在情況下平衡樹高。

提供相關的數學分析。

XTree 的最壞情況樹高與普通的二元搜尋樹相似,取決於節點的插入順序。在沒有特殊的平衡措施下,最糟糕情況下可能形成一個高度接近於線性的右斜樹。例如,如果按照特定的插入順序導致每次插入的節點都比前一個節點大(或小),則最終形成的樹可能高度接近於

𝑛 ,等同於節點的數量。

與 AVL tree 、 rbtree 比較

AVL tree 為確保平衡,利用平衡因子判斷其子樹高差距,再決定是否旋轉。當為平衡時,必滿足以下條件:

(1,0,1) 。xtree 與 AVL tree 類似,利用 hint 紀錄子樹高,在 xt_update 時計算高度差,當左右差異大於一時,進行旋轉。但從程式碼中可以發現,其僅對平衡因子 b 進行大於一或小於一的判斷,進而右旋或左旋。AVL tree 相較之下,有 LL、RR、LR、RL 四種旋轉方式。利用前面提及 xtree 單純使用左或右旋無法解決平衡樹高的情境下。僅需要使用右左或左右旋便可解決。

初始結構:







Tree

origin


p

p



n

n



p->n





r

r



p->r





A

A



n->A





l

l



n->l





B

B



l->B





先對 n 左旋:







Tree



p

p



l

l



p->l





r

r



p->r





n

n



l->n





B

B



l->B





A

A



n->A





再對 p 右旋:







Tree



l

l



n

n



l->n





p

p



l->p





a

a



n->a





b

b



p->b





r

r



p->r





如此一來,變完成樹高平衡。由於樹高對搜尋的效能有所影響,因此簡單討論 AVL tree 的樹高。在平衡的情況下,假設樹高為 h,n(h)為節點最少的情況下樹高與節點的數量關係:

n(h)=n(h1)+n(h2)+1
在 AVL tree 樹高。可以發現該關係式與費氏數列相似,因此使用該特性推算第 k 項的數值:
ϕk/5
。基於該相似特性,推算
n(h)
也是如此,只不過是把
5
代換為其他常數,
n(h)kϕh
。即便再糟糕的情況下都滿足
ϕhn
,取對數後樹高即為
hlog(n)/log(ϕ)1.44×log(n)

rbtree 規則:

  1. 節點只能是紅或黑色
  2. 根節點必為黑色
  3. 葉節點必為黑色
  4. 紅色節點的子節點必為黑色
  5. 從任一節點到其葉節點,途中路徑上的黑色節點數目相同

滿足上述規則的二元樹,相比一般的二元樹更能保持平衡性,往後套用二元樹的算法來查找資料時能更快速、方便地到達目的地,套用運算的時間複雜度為 O(log n),這是因為紅黑樹保證最長路徑不會超過最短路徑的兩倍,最短路徑為葉節點到根節點路徑上全部的節點均為黑色,而最長路徑為黑紅相間。

為了 rbtree 在節點操作後,仍滿足 rbtree 的條件。因此,有'變色'與'旋轉'兩種操作。在樹高上,rbtree 與 AVL tree 西相比,因為後者使用平衡因子所以對樹高差異限制嚴格,樹高為

1.44×log(n)。反觀 rbtree 平衡機制是利用上述的五條規則,因此樹高較高。因為最長的路徑,可以視為在最短路徑(即路徑上節點均為黑色)間隔插入紅色節點。在 rbtree 樹高上,假設黑高為 bh,那該數至少包含
2bh1
個節點(即不存在紅色節點)。利用紅色節點不會連續的條件,可以視為紅色節點被間隔插入,故最高樹高為兩倍的黑高(
h=2×bh
)。假設一顆 rbtree 有 n 個節點,則
2bh1n
,重新整理後可得。
bhlog(n+1)
,故在樹高在最糟的情況下
h2×log(n+1)
。在
n
極大的情況下便近似為
2×log(n)

對比 rbtree 與 AVL tree 在樹高上的差異後,rbtree 因為平衡規則較寬鬆,樹高較高。所衍伸的缺點就是雖然在平均狀況下複雜度仍為

log(n),但最糟的情況下畢竟樹高較高,搜尋的速度稍較 AVL tree 慢。

xtree 因為前面與 AVL tree 作比較時發現,其無法有效的利用程式碼原始的單純左右旋達到平衡樹高,容易出現歪斜的情況,從而增加樹高,減慢在最糟的情況下的搜尋速度。

TODO: 提出 XTree 的改進方案

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

xtree 原始程式碼中,不如 AVL tree 有四種旋轉,僅存在兩種旋轉。在遭遇上述所提及的部份樹狀結構時,無法平衡樹狀結構。對以下程式碼修改,使的 xtree 同樣擁有 4 種旋轉:

     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 的設計初衷是為了因應需要進行大量節點插入/刪除操作,而捨棄搜索速度所做出的權衡。

補上數學分析

在上述的程式碼修改後,xtree 的樹高平衡機制幾乎無異於 AVL tree,差別僅在於 xtree 是透過在每一節點利用 hint 紀錄樹高,而不是在一開始就將左右子樹高的相差先計算好。並且僅在 xt_node 被呼叫時進行平衡狀態更新。有了以上對數高平衡的修正,xtree 的結後會趨近 complete binary tree,其中,對於該樹的第

i 個節點會在第
floor(log2(i))
層。而對於邊條數量計算上,深度為
d
的節點從根結點到該節點會共有
d
個邊條,也就是說可以透過計算第
i
個節點的深度,推溯出跟節點到第
i
節點的邊數為
floor(log2(i))
。所以總共
n
個節點就會有
i=1nfloor(log2(i))=O(n×log(n))
個邊條。
下面圖解其機制,首先考慮初始狀態的 xtree







Tree



n

n



xt_left

xt_left



n->xt_left





xt_right

xt_right



n->xt_right





A

A



xt_left->A





B

B



xt_left->B





C

C



B->C





使用 xt_balance(n) 可以獲得左右子樹高的相差,即平衡因子,在這裡為

31=2,沒有落在正負 1 的範圍。引此 b>1 判斷式為真。進入 xt_balance(xt_left(n)<0) 的判斷當中。而 xt_left 節點的子樹高所得的平衡一因子為:
121
,該判斷式同為真。故觸發 xt_rotate_right(xt_left)xt_left 進行左玄。完成該步驟的 xtree 如下:







Tree



n

n



B

B



n->B





xt_right

xt_right



n->xt_right





xt_left

xt_left



B->xt_left





C

C



B->C





A

A



xt_left->A





最後再進行 xt_rotate_right(n) n 右旋:







Tree



n

n



C

C



n->C





xt_right

xt_right



n->xt_right





xt_left

xt_left



A

A



xt_left->A





B

B



B->n





B->xt_left





這樣變可以完成與 AVL tree 相同的旋轉機制,以確保結構平衡。