深度解析排序二叉樹：從基礎操作到紅黑樹平衡機制

排序二叉樹：有序數據結構的基石

在掌握了 HashMap（哈希表）與 HashSet 之後，我們發現它們雖然查找極快（O(1)），卻無法保持元素順序。當業務需要「有序遍歷」「範圍查詢」「查找最值」時，排序二叉樹及其平衡變體（AVL 樹、紅黑樹）便成為首選。本文系統梳理其核心概念、基本算法與工程化演進。

一、核心概念

1. 樹的基本術語

• 根節點：樹的起點（計算機中樹「向下生長」）
• 孩子節點：節點的直接後繼；葉子節點：無孩子的節點
• 高度/深度：根到最遠葉子的節點數

2. 二叉樹與排序二叉樹 (BST)

• 二叉樹：每節點最多兩個孩子（左/右）
• 排序二叉樹 (BST)：在二叉樹基礎上加兩條鐵律：
  1. 左子樹非空 ⇒ 所有節點值 < 當前節點值
  2. 右子樹非空 ⇒ 所有節點值 > 當前節點值
  推論：中序遍歷即得有序序列；最小值在最左葉子，最大值在最右葉子。

二、四大基本操作算法

1. 查找 —— 類二分，效率 O(h)

從根節點開始：
  若目標值 == 當前節點值 → 找到
  若目標值 < 當前節點值 → 進左子樹
  若目標值 > 當前節點值 → 進右子樹
  直到找到或走到 null

若樹平衡（h ≈ log₂N），查找極快；若退化成鏈表（h = N），效率驟降。

2. 遍歷 —— 遞歸中序得有序序列

inOrder(node):
  if node == null: return
  inOrder(node.left)
  visit(node)      // 1 → 3 → 4 → 6 → 7 → 8 → 9
  inOrder(node.right)

非遞歸後繼算法（用於迭代器實現）：

• 有右孩子 → 右子樹最小節點
• 無右孩子 → 向上找「第一個非右孩子」的父節點

3. 插入 —— 先找父節點，再掛左/右

步驟與查找幾乎相同，只是在「應該插入卻發現 null」的位置掛上新節點。

4. 刪除 —— 三種情況分治

1. 葉子節點：直接斷開父節點引用
2. 單孩子節點：孩子頂替被刪節點位置
3. 雙孩子節點：核心技巧——找後繼（右子樹最小，必無左孩子），用後繼值覆蓋被刪節點，再刪除後繼（轉化為情況 1 或 2）
   

三、平衡問題與工程解法

退化風險

若插入序列有序（如 1,3,4,6,7,8,9），BST 退化為鏈表，查找/插入/刪除全變 O(N)。

AVL 樹：嚴格高度平衡

• 定義：任意節點左右子樹高度差 ≤ 1
• 機制：插入/刪除後通過旋轉（單旋/雙旋）恢復平衡
• 優點：查找極快；缺點：維護成本高，旋轉頻繁

紅黑樹：工程界的「大致平衡」首選

• 約束：節點染紅/黑，滿足 5 條著色規則（根黑、葉黑、紅不連紅、路徑黑高一致等）
• 核心保證：任意根到葉路徑，最長不超過最短的 2 倍
• 權衡：犧牲「絕對平衡」換取「較少旋轉」，綜合統計性能優於 AVL
• 應用：JDK TreeMap、TreeSet、Linux 內核 CFS 調度器、數據庫索引（B+樹變體）

四、核心複雜度總結

五、思維遷移：哈希 vs 樹

不需要順序 → 優先哈希（O(1)）
需要順序/範圍查詢 → 選樹（O(log N)）

這正是 HashMap vs TreeMap、數據庫 Hash 索引 vs B+樹索引 的本質區別。理解 BST，是通往高性能存儲引擎的敲門磚。

下一站預告

下兩節將深入剖析 TreeMap 與 TreeSet 源碼，揭秘紅黑樹在 JDK 中的工程化實現細節。敬請期待！