平衡樹

動機

對一棵 search tree 進行查詢/新增/刪除 等動作, 所花的時間與樹的高度 h 成比例, 並不與樹的容量 n 成比例。 如果可以讓樹維持矮矮胖胖的好身材, 也就是讓 h 維持在 O(lg n), 上述工作就很省時間。 能夠一直維持好身材, 不因新增刪除而長歪的搜尋樹, 叫做 balanced search tree 平衡樹。

旋轉 -- 不破壞左小右大特性的小手術

平衡樹有很多種, 其中有幾類樹維持平衡的方法, 都是靠整形小手術:

                y                       x
               / \                     / \
              x   C     <==>          A   y
             / \                         / \
            A   B                       B   C

圖中 x 與 y 為 nodes; A, B, C 為一整串的 subtrees。 試想: 如果 x 原來是 y 的 left child; 現在想將 x 變成 parent, 則樹的其他部分應如何變化? y 必須變成 right child, 這樣才能維持 BST 的特性 -- 左小右大。 至於 x 與 y 以下的其他部分, 可以整串 subtree 一起處理: x 原來的 left subtree (A), 調整後還是 x 的 left subtree; y 原來的 right subtree (C), 調整後還是 y 的 right subtree; 而 x 原來的 right subtree (B), 調整後很自然只有一個地方可以放: 變成 y 的 left subtree。 這些規則都不需要記, 因為如果你希望調整後還維持 BST 左小右大的特性, 這是唯一的答案。 把 x,y 兩個值及 A,B,C 三棵 subtrees 內的三串值畫在數線上看更清楚:

        --------- x --------- y ---------
            A           B           C

這個動作, 稱為 right rotation 向右旋轉, 或稱為順時針旋轉 (clockwise)。 原來的 parent (y) 叫做 pivot, 原來的 child (x) 叫做 rotator。

把上圖反過來看, 如果原來的樹長得像右圖, 想將它改成左圖, 則稱為 left rotation 向左旋轉, 或稱為逆時針旋轉 (counter-clockwise)。 原來的 parent (x) 叫做 pivot, 原來的 child (y) 叫做 rotator。

數一下舊的 parent 左 subtree 有多少 ndoes? 右 subtree 有多少 nodes? 旋轉後新的 parent 左右 subtrees 又各有多少 nodes? 發現右旋的效果會讓樹的重心往右移; 而左旋的效果則是讓樹的重心往左移。 如果你的樹經歷過許多 insert/remove 等等歲月的滄桑, 越長越歪, 在適當的時候對它進行一下旋轉手術, 不就可以將它變回矮矮胖胖四平八穩的美麗模樣嗎? 所以左旋與右旋是幾種平衡樹共同採用的基本手術; 只不過不同的平衡樹, 選擇不同的時機/條件來動手術而已。

Red-Black Tree

Red-Black Tree 紅黑樹 是一種 balanced tree。 它基本上是一棵 binary search tree, 但每個 node 還漆上了顏色 -- 可以是紅色或黑色。

  1. 從一個 node x 往下走, 每一條通往 leaf 的路徑上遇到的黑色 nodes 都一樣多. 這個固定的數目叫做 x 的 black-height。
  2. 紅色的 node 不可連續兩代。

直覺解釋: 希望定義出一棵 (黑色的) full 或 complete binary tree (每個 leaf 所在的深度最多只差 1); 但這個條件顯然太嚴格, 太缺乏彈性, 無法達成, 所以允許有紅色的 nodes 穿插其間。 把紅色的 nodes 想像成是雜質, 希望雜質不要太多, 以免破壞樹的平衡。

因為它根本就是一棵 BST, 所以查詢資料很簡單

新增資料時如何保持 red-black tree 的特性? 先當做一般的 BST, 一路往下找到新資料 x 的落點, 並把 x 塗上紅色。 這樣的變化, 不會破壞 "black height 原則", 但可能破壞 "不可連紅原則", 所以可能需要一路往上整修樹:

  1. 如果 x 的父親是黑色的, 就太完美了, 完全不需要整修。 結束。
  2. 不然的話, x 的父親既是紅色, x 的祖父一定是黑色的 -- 有以下三種狀況要考慮:
    1. 叔叔也是紅色的: 讓祖/父兩輩「紅黑變色」. 現在 x 是沒有問題了, 但祖父可能變成紅色, 因而產生問題。 所以讓祖父扮演 x 的角色, 繼續往上整修。
    2. 叔叔是黑色的, x 到祖父的路上沒有轉彎: 以祖父為 pivot, 父親為 rotator 旋轉, 並調整顏色。 結束。
    3. 叔叔是黑色的, x 到祖父的路上有轉彎: 先以父親為 pivot, x 為 rotator 旋轉, 變成上個狀況, 再依上個狀況處理。

很複雜嗎? 與其記這些規則, 不如注意幾個原則:

  1. 紅色 nodes 很多的地方, 表示很沉重。 應該藉旋轉來平衡; 或者如果兩邊都很沉重, 旋轉也沒有用, 只好將問題往上丟。
  2. 著色時, 永遠要維持 red-black tree 的特性。

以 case 2.2 為例, 祖父的左右兩棵 subtrees 一黑一紅, 表示紅色那邊太沉重; 而黑色那邊應該還有空間可以容納更多 nodes。 這表示: (1) 可以把紅色的 node (也就是 x 的父親) 轉上來 (2) 轉完以後, 不需要將問題繼續向上丟。 轉完以後要如何著色, 問題才不會繼續向上丟呢? 既然祖父是黑色, 曾祖父有可能是紅色。 父親變成整棵 subtree 的 root 之後, 勢必要變成黑色, 以免與曾祖父產生衝突。 祖父與 x 都必須變成紅色, 不然整棵 subtree 的 black height 會增加, 就破壞了 red-black tree 的第一個特性。 這樣會否與下方的紅色 nodes 產生衝突呢? 不會的, 因為底下所有 subtrees 的 root 本來就全部都是黑色。 (包含 x 原來的兩個 subtrees, 及叔叔所帶領的 subtree 都是如此。)

瞭解原則之後, 再注意到兩個剛才刻意省略的細節:

  1. 不論如何調整, 最後總是可以將 root 塗成黑色。
  2. 其實叔叔除了可能是黑色或紅色之外, 還可能不存在! 但是如果你瞭解著色的用意 (而不是流於記憶瑣碎的細節), 就知道這種情況表示隔壁那棵 subtree 很空曠, 所以可以按照 "叔叔是黑色" 的狀況來處理。

這是一棵 red-black tree -- 請檢查它的兩個特性。

[原始 red black tree]

新增 483, 進行 case 2.1:

[新增 483 之後]

新增 990, 進行 case 2.2:

[新增 990 之後]

新增 608, 進行 case 2.3:

[新增 608 之後]

新增 966, 進行 case 2.1:

[新增 966 之後]

再看一個比較複雜的例子: 上述的樹, 回到它只有 27 個元素時, 長得像這樣:

[27 個元素時的長相]

新增 777, 進行 case 2.1, 祖父 756 變成紅色, 再進行 case 2.1, 高祖父 592 變成紅色, 最後進行 case 2.3: 先以 789 為 pivot 右旋, 再以 420 為 pivot 左旋。

[新增 777 之後]

n 個 nodes 的紅黑樹 (可以存放 n 筆資料), 它的高度為 Theta(lg n), 所以它是一棵 balanced tree。 結論: 不論是增刪查改, 所需時間皆為 O(lg (n))

以下未整理.

2-3-4 Tree and B-Tree

  1. 使用 balanced tree (平衡樹) 的目的: 要讓樹長得矮矮胖胖, 不要 skew, 以節省增刪查改資料的時間 (因為這些運算所花的時間, 通常和樹的高度成正比).
  2. (複習 m 元搜尋樹 m-ary search tree)
    1. 它是一棵樹.
    2. 每個 node 至多有 m 個 children
    3. 一個 node 若有 k 個 children, 則應有 k-1 筆資料.
    4. 一個 node V 內的 k-1 筆資料 a(1), a(2), ... a(k-1) 應按順序排好, (正好把所有可能發生的資料值分成 k 個區間) 而 V 的第 i 棵 subtree 內所有的資料都必須介於 a(i-1) 和 a(i) 之間.
    5. 搜尋/新增/刪除一筆資料所需的時間皆為 O(h), 其中 h 為樹的高度.
  3. 一般 m-ary search tree 的問題: 樹的高度 h 與整棵樹內所存的資料筆數 n 沒有固定的關係. 運氣好的時候 (樹為 balanced) h 可以小到 Theta(lg n); 運氣不好的時候 (樹為 skewed) h 可以大到 Theta(n).
  4. Balanced 2-3-4 tree (以下簡稱 234 tree) 是一種特殊的 4-ary search tree, 它的設計使它永遠保持在 balanced 的狀態, 如此可以確保所有搜尋/新增/刪除一筆資料所需的時間必為 O(lg n).
  5. 234 tree T 的定義:
    1. T 是一棵 4-ary search tree.
    2. 每個 internal node 至少有 2 個 children.
    3. 所有的 leaves 都在同一層.
  6. 一棵高度為 h 的 234 tree,
    至少有 1+2+4...+2^(h-1) = 2^h-1 個 nodes, 2^h-1 個 keys;
    至多有 1+4+16...+4^(h-1) = (4^h-1)/3 個 nodes, 4^h-1 個 keys;
    反過來說, 存放 n 個 keys 的 234 tree, 其高度為 Theta(log(n)).
  7. 在 234 tree 當中搜尋資料很簡單, 其實就是在一般的 4-ary search tree 當中搜尋.
  8. 新增資料時如何保持 234 tree 的特性?
    1. 由上而下尋找新資料的落點過程當中, 一路上每遇到一個 full node (就是有 3 筆資料, 4 棵 subtrees 的 node), 便將它拆開 (split), 這樣可以確保最後新資料要放進去的 node 至少還有一個空位可以放.
    2. 如何拆開一個 full node? 把它拆成兩個 2-nodes (共 2 筆資料, 4 棵 subtrees). 原來最中間那筆資料怎麼辦? 把它往上提到 parent node 去. parent node 增加了一個 child, 自然也應該多一筆資料 (區間個數永遠等於資料筆數加 1).
    3. 那如果在 split 時, 發現 parent node 也滿了怎麼辦? 不可能的, 因為我們一路往下走的過程當中, 已確保祖先都不是 full nodes 了.
  9. 刪除資料比較麻煩, 但原則相同: 必須確保 234 tree 的特性.
  10. B-tree T 的定義:
    1. T 是一棵 (2t)-ary search tree.
    2. 每個 internal node 至少有 t 個 children. root 例外, 它至少要有 2 個 children.
    3. 所有的 leaves 都在同一層.
    容易驗証: 高度為 h 的 B tree 至少有 2*t^h-1 個 nodes, 所以高度 h 屬於 Theta(lg n).
  11. 234 tree 是 B-tree 的一個例子 (t=2). 234 tree 通常用於記憶體內; 一般的 B-tree (t 值很大) 通常用於檔案系統內.
  12. 新增資料時如何保持 B tree 的特性?
    1. 由上而下尋找新資料的落點過程當中, 一路上每遇到一個 full node (就是有 2t-1 筆資料, 2t 棵 subtrees 的 node), 便將它拆開 (split).
    2. 如何拆開一個 full node? 把它拆成兩個 t-nodes (共 2t-2 筆資料, 2t 棵 subtrees). 同樣地, 把原來最中間那筆資料給往上提到 parent node 去.