二叉排序樹與平衡二叉樹：動態查找的樹形結構演進

從有序表到二叉排序樹的動機

有序線性表查找快（O(log n)），但插入/刪除需移動大量元素（O(n)）。鏈表雖插刪 O(1) 但查找退化 O(n)。二叉排序樹 (BST) 結合兩者優勢：鏈式存儲（插刪無需移動）+ 有序性（查找 O(h)）。

二叉排序樹 (BST) 定義與性質

• 空樹，或滿足：
  1. 左子樹非空 → 所有節點值 < 根節點值
  2. 右子樹非空 → 所有節點值 > 根節點值
  3. 左右子樹皆為 BST
• 中序遍歷 BST → 遞增有序序列。
• 查找/插入/刪除時間複雜度：O(h)，h 為樹高。

BST 構造示例

數組 {9, 1, 5, 8, 3, 7, 4, 6, 2} 依次插入構造 BST。若輸入有序 {1,2,3,4,5}，樹退化為右斜鏈表，樹高 h = n，查找退化 O(n)。

平衡二叉樹 (AVL) 解決退化問題

定義

平衡二叉樹是 BST 的子集，附加條件：任意節點左、右子樹高度差 |bf| ≤ 1（平衡因子 Balance Factor = 左高 - 右高）。

四種失衡與旋轉調整

調整原則

1. 插入節點後，沿路徑向根回溯更新高度/平衡因子。
2. 發現首個 |bf| = 2 的節點（最小不平衡子樹）。
3. 根據其子樹 bf 判斷類型，執行對應旋轉。
4. 旋轉後子樹高度恢復，整樹平衡，無需繼續向上調整。

BST vs AVL 核心對比

工程延伸：紅黑樹與 B+ 樹

• 紅黑樹：放寬平衡條件（黑高平衡），旋轉次數少於 AVL，插刪效能更優，C++ STL map/set、Java TreeMap、Linux 內核 rb_tree 採用。
• B+ 樹：多路平衡樹，節點對應磁盤頁，極大降低樹高，範圍查詢友好，MySQL InnoDB、PostgreSQL、MongoDB 核心索引結構。

總結

BST 確立「鏈式存儲 + 有序性」的動態查找範式；AVL 以嚴格平衡保證最壞 O(log n)；紅黑樹以工程友好的「近似平衡」成為通用庫標配；B+ 樹面向外存成為資料庫索引王者。掌握 BST→AVL→紅黑樹→B+ 樹的演進脈絡，是理解現代存儲引擎索引架構的鑰匙。