[algorithms] Tree 樹 | 分享技術與生活

cover

Tree 是從「線性」到「階層」的跳躍，也是理解資料庫索引和檔案系統的入口。

左小右大，換來 O(log n)

BST（二元搜尋樹）靠「左小右大」的規則，把搜尋、插入、刪除都做到 O(log n)。但它有致命弱點——如果資料按順序插入，會退化成鏈表。所以才有了 AVL Tree 和 Red-Black Tree 這些自平衡變體。

樹的基本結構

        50          ← root
       /  \
      30    70      ← 子節點
     / \   / \
    20 40 60 80     ← leaf（葉節點）

每個節點有值、左子節點、右子節點。沒有子節點的叫 leaf。從 root 到最深 leaf 的距離叫 height。

BST 的核心規則：左小右大

Binary Search Tree 的每個節點都滿足：左子樹所有值 < 自己 < 右子樹所有值。

這個規則讓搜尋變得像翻字典——你不用從頭翻到尾，每次比較就能排除一半。

搜尋 40：
50 → 左（40 < 50）→ 30 → 右（40 > 30）→ 40 ✓
 
只比較了 3 次，而不是遍歷全部 7 個節點。

寫成程式碼，搜尋和插入其實就是「照著左小右大往下走」，短到有點可愛：

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; }
}
 
// 搜尋：比大小決定往左還往右，走到 null 就是沒有
Node search(Node root, int target) {
    if (root == null || root.val == target) return root;
    return target < root.val ? search(root.left, target)
                             : search(root.right, target);
}
 
// 插入：一路往下走到底，把新節點掛在該在的位置
Node insert(Node root, int val) {
    if (root == null) return new Node(val);
    if (val < root.val)      root.left  = insert(root.left, val);
    else if (val > root.val) root.right = insert(root.right, val);
    return root;   // 相等就當重複，不動它
}

這幾行漂亮歸漂亮，前提是樹長得夠均衡。一旦退化成鏈表（下面會講），這個 search 就從砍半變成一格一格走——同一段 code，效能天差地別。

BST 刪除：三種情況

刪除是 BST 操作裡最麻煩的。

刪 leaf：直接拔掉。

刪只有一個子節點的：讓子節點頂替自己。

刪有兩個子節點的：找右子樹的最小值來替代（in-order successor），然後刪掉那個最小值節點。

刪除 50：
    50              60（右子樹最小值頂替）
   /  \    →       /  \
  30    70        30    70
       /
      60

為什麼用右子樹最小值？因為它比左子樹所有值大、比右子樹其他值小，剛好滿足 BST 規則。

四種遍歷

        50
       /  \
      30    70

方式	順序	結果	重點用途
In-order	左→根→右	30, 50, 70	BST 排序輸出
Pre-order	根→左→右	50, 30, 70	序列化/複製樹
Post-order	左→右→根	30, 70, 50	刪除樹
Level-order	一層一層	50, 30, 70	BFS

最重要的是 In-order：BST 的 in-order traversal 會自動產生排序好的結果。這不是巧合，是 BST「左小右大」規則的直接結果。

退化問題：為什麼需要平衡

依序插入 1, 2, 3, 4, 5：

1
 \
  2
   \
    3      → 退化成鏈表
     \       搜尋變 O(n)
      4
       \
        5

這就是為什麼面試官問你「BST 最差情況的複雜度」，答案是 O(n) 不是 O(log n)。攤開來看，BST 三個操作的臉都是同一副：

操作	平均	最差（退化成鏈表）
搜尋	O(log n)	O(n)
插入	O(log n)	O(n)
刪除	O(log n)	O(n)

平均和最差差了一個數量級，差別只在「樹有沒有保持平衡」——這就是自平衡樹存在的全部理由。

解法：讓樹自動維持平衡。AVL Tree 嚴格要求高度差 ⇐ 1，Red-Black Tree 寬鬆一點但插入刪除更快。Java 的 TreeMap 和 TreeSet 底層就是 Red-Black Tree。

🎬 互動視覺化：BST 與 AVL 自平衡對照 — 依序插入 1,2,3,4,5，左邊看 BST 怎麼歪成一條鏈表，右邊看 AVL 每插一顆就旋轉把自己扳回平衡。

Tree 的實際應用

你可能以為 Tree 是學術玩具，但它無處不在：

資料庫索引：MySQL 的 InnoDB 用 B+ Tree，每次查詢都在走樹
檔案系統：目錄結構就是一棵樹
DOM：瀏覽器的 Document Object Model 是一棵樹
AST：編譯器把你的程式碼解析成抽象語法樹

Tree 是程式設計師認識「分治法」的第一站——把大問題劈成兩半，再劈成兩半，直到簡單到可以直接解。

接下來往哪走

AVL Tree 自平衡二元搜尋樹 — 解決 BST 退化成鏈表的第一種自平衡方案
Heap 堆積 — 另一種樹：不管左小右大，只保證根是極值
B+ Tree — 資料庫索引真正用的樹：一個節點放上百筆，減少磁碟 I/O

Terry Yao's Blog

目錄

Tree 樹