跳轉到

6.2 紅黑樹的原理#

概念說明#

紅黑樹（red-black tree） 是實務界最受歡迎的自平衡 BST：C++ 的 std::map/std::set、Java 的 TreeMap、Linux 核心的排程器與虛擬記憶體管理都用它。它不像 AVL 追求「高度差 ≤ 1」，而是用五條性質保證較寬鬆的上界：最長的根到葉路徑不超過最短者的兩倍，因此樹高仍是 O(log n)，只是常數較大。

五條性質：

  1. 每個節點是紅色或黑色。
  2. 根是黑色。
  3. 葉（NIL 空位）視為黑色。
  4. 紅節點的兩個小孩都是黑的（不允許相鄰紅紅）。
  5. 任一節點到其所有後代葉的路徑上，黑節點數相同（黑高一致）。

性質 4、5 聯手封頂樹高：一條路徑黑節點數固定，紅節點又不能相鄰，故紅至多與黑一樣多，路徑長度 ≤ 2×黑高。插入/刪除後的修復目標，就是重新滿足這五條性質——能「重新著色」解決就不旋轉，必要時才旋轉，因此旋轉次數比 AVL 少，修改更便宜。

插入修復的思路#

新節點一律染紅（染黑會破壞黑高）。之後只需處理「父親也是紅色」的紅紅衝突，三種情況：

  1. 叔叔是紅色：把父與叔改黑、祖父改紅，衝突上移兩層，繼續修。
  2. 叔叔是黑色（三角型）：旋轉一次把三角拉直，轉成情況 3。
  3. 叔叔是黑色（直線型）：父與祖父換色 + 旋轉一次，修復完成。

每種情況至多 2 次旋轉，故插入至多 2 次旋轉；刪除較繁瑣（至多 3 次），本節示範插入，刪除請見練習延伸。

Python 實作#

RED, BLACK = 0, 1
NIL = None                        # 簡化：以 None 當黑葉

class RBNode:
    def __init__(self, val):
        self.val, self.color = val, RED
        self.left = self.right = self.parent = None

class RBTree:
    def __init__(self):
        self.root = None

    def _rotate_left(self, x):
        y = x.right
        x.right = y.left
        if y.left: y.left.parent = x
        y.parent = x.parent
        if x.parent is None:       self.root = y
        elif x is x.parent.left:   x.parent.left = y
        else:                      x.parent.right = y
        y.left = x
        x.parent = y

    def _rotate_right(self, x):
        y = x.left
        x.left = y.right
        if y.right: y.right.parent = x
        y.parent = x.parent
        if x.parent is None:       self.root = y
        elif x is x.parent.right:  x.parent.right = y
        else:                      x.parent.left = y
        y.right = x
        x.parent = y

    def insert(self, val):
        parent, cur = None, self.root
        while cur:
            parent = cur
            cur = cur.left if val < cur.val else cur.right
        node = RBNode(val)
        node.parent = parent
        if parent is None:            self.root = node
        elif val < parent.val:        parent.left = node
        else:                         parent.right = node
        self._fix(node)

    def _fix(self, z):
        while z.parent and z.parent.color == RED:
            p = z.parent
            g = p.parent
            uncle = g.right if p is g.left else g.left
            if uncle and uncle.color == RED:          # 情況1：換色上移
                p.color = uncle.color = BLACK
                g.color = RED
                z = g
            else:
                if p is g.left and z is p.right:      # 情況2：三角→直線
                    z, p = p, z
                    self._rotate_left(z)
                elif p is g.right and z is p.left:
                    z, p = p, z
                    self._rotate_right(z)
                p.color, g.color = BLACK, RED         # 情況3：直線
                if p is g.left: self._rotate_right(g)
                else:           self._rotate_left(g)
                return
        self.root.color = BLACK                        # 根恆黑

    def in_order(self):
        out = []
        def walk(n):
            if n:
                walk(n.left); out.append(n.val); walk(n.right)
        walk(self.root)
        return out

t = RBTree()
for x in [10, 20, 30, 15, 25, 5, 1, 40, 50]:
    t.insert(x)
print(t.in_order())          # [1, 5, 10, 15, 20, 25, 30, 40, 50]
print("根:", t.root.val, "黑色" if t.root.color == BLACK else "紅色")

def black_height(n):         # 驗證黑高一致
    if n is None:
        return 1
    lb, rb = black_height(n.left), black_height(n.right)
    assert lb == rb, "黑高不一致"
    return lb + (1 if n.color == BLACK else 0)
black_height(t.root)
print("紅黑性質檢查通過")

複雜度分析#

搜尋 O(log n)（樹高 ≤ 2·log₂(n+1)）；插入刪除 O(log n)，其中旋轉至多常數次，其餘成本在換色。與 AVL 相比：紅黑樹稍高（查詢略慢）但修改便宜，適合「改動頻繁」的工作負載。記憶體上每節點多 1 位元顏色資訊。

練習#

  1. 依序插入 1..10（升冪），畫出每步插入後的樹形與顏色，觀察為什麼不會退化。
  2. 實作紅黑樹的 delete（提示：刪黑節點造成「雙黑」，需借兄弟，共四種情況；建議搭配圖解逐步實作）。
  3. 對比實驗：隨機資料下，AVL 與紅黑樹各插入 10 萬筆再搜尋 10 萬次，比較總時間；再改成「邊插邊搜」交錯工作負載，結論是否改變？