從 BST 到資料庫索引
這份自學頁接在二元搜尋樹、二元堆積與 AVL 樹之後，補上第 10、11 章的核心概念。閱讀重點不是背樹名，而是看每種結構如何控制「搜尋成本」：有些靠機率安排根節點，有些靠旋轉或著色控制高度，有些把一個節點做大來減少磁碟存取次數。
同一組鍵值，可以有不同的搜尋成本
二元搜尋樹的中序順序固定，但樹形不固定。若每個鍵值被搜尋的機率相同，平均比較次數只看深度；若機率不同，常被查到的鍵值應靠近根節點。
若鍵值為 $a_1 \lt a_2 \lt \cdots \lt a_n$，且搜尋 $a_i$ 的機率為 $p_i$，成功搜尋的期望成本可以看成「每個鍵值的深度加 1，再乘上它的機率」。根越淺，比較次數越少。
在每個空子指標補上一個外部節點，可把「搜尋失敗」也納入成本。若搜尋值落在 $a_i$ 與 $a_{i+1}$ 之間，就會走到對應的外部節點。
完整模型會把成功搜尋與失敗搜尋都納入成本。$p_i$ 是成功搜尋 $a_i$ 的機率；$q_i$ 是搜尋值落在兩個鍵值間隔中的機率，其中 $q_0$ 表示 $x \lt a_1$，$q_i$ 表示 $a_i \lt x \lt a_{i+1}$，$q_n$ 表示 $x \gt a_n$。
用動態規劃選出每個區間的根節點
最佳二元搜尋樹假設每個成功搜尋與失敗搜尋的機率已知，目標是在所有可能樹形中找出總期望成本最低者。核心想法是：一旦某個鍵值被選為根，左、右兩邊就變成較小的最佳子問題。
用平衡因子維持高度
AVL 樹是高度平衡的二元搜尋樹。每個節點 $v$ 記錄平衡因子 $BF(v)=h_L-h_R$，合法值只允許 $-1,0,1$。插入後若最近失衡祖先 $A$ 的平衡因子變成 $\pm2$，就用四種旋轉之一修復。
新節點落在外側子樹。LL 對 $A$ 右旋，RR 對 $A$ 左旋。
新節點落在內側子樹。LR 先對左子做左旋再對 $A$ 右旋；RL 對稱。
沿插入路徑往上找第一個失衡祖先，做一次單旋或雙旋即可恢復該區域高度。
看旋轉前後的中序序列是否相同；若相同，就沒有破壞搜尋樹規則。
用著色規則放寬 AVL 的平衡
紅黑樹是一種擴充二元搜尋樹。它不要求左右高度差最多 1，而是用紅、黑規則限制最長路徑不會超過最短黑高路徑的兩倍，因此高度仍為 $O(\log n)$。
父節點與叔節點改黑，祖父節點改紅，衝突往上傳；若祖父是根，最後強制改黑。
依 LL、LR、RR、RL 型態做 AVL 類似旋轉，再重新著色。
也可把顏色看成邊的顏色：到外部節點的邊為黑，沒有連續紅邊，黑邊數一致。
紅黑樹平衡較寬鬆，插入刪除旋轉次數通常較少，因此常見於標準函式庫的有序映射與集合。
每次操作後把目標伸展到根節點
伸展樹也是二元搜尋樹，但不儲存平衡因子或顏色。搜尋、插入、刪除先像普通搜尋樹一樣進行，接著把起始節點一路旋轉到根。單次操作最壞可到 $O(n)$，但攤銷為 $O(\log n)$。
若起始節點只有父節點、沒有祖父節點，就做一次旋轉讓它成為根。
左左或右右型態，先轉祖父再轉父節點，一次上升兩層。
左右或右左型態，對起始節點做兩次旋轉，仍保持中序順序。
近期常查詢的資料會被拉近根節點，對有局部性的查詢序列特別有用。
從根往目標走，一邊走一邊把小於目標的節點接到小樹，把大於目標的節點接到大樹。
遇到同向兩步時先做一次旋轉，避免路徑太斜；到達目標後把小樹接左邊、大樹接右邊。
一個節點裡可以放多個鍵值
多路搜尋樹把二元搜尋樹「每個節點一個鍵值、最多兩個子樹」推廣成「每個節點多個鍵值、最多 $m$ 個子樹」。搜尋時先在節點內找出目標落在哪個區間，再往對應子樹走。
一個 $m$ 路搜尋樹節點可寫成 $n,A_0,(K_1,A_1),\ldots,(K_n,A_n)$，其中最多有 $m$ 個子樹、所以鍵值數 $0\le n\le m-1$。鍵值滿足 $K_1 \lt K_2 \lt \cdots \lt K_n$。令 $K_0=-\infty$、$K_{n+1}=\infty$，則子樹 $A_i$ 中所有鍵值都必須大於 $K_i$ 且小於 $K_{i+1}$。
保持每個節點至少半滿，所有葉子同層
$m$ 階 B 樹是有容量限制的多路搜尋樹。除了根與外部節點以外，每個內部節點至少有 $\lceil m/2\rceil$ 個子節點，最多 $m$ 個子節點，所有外部節點在同一層。
先插入葉節點；若節點超過容量，取中間鍵值往父節點提升，左右鍵值分成兩個節點。
刪除後若節點鍵值太少，優先向相鄰兄弟借一個鍵值，父節點鍵值同步調整。
若兄弟無法借，就把父節點的一個分隔鍵拉下來與兄弟合併；不足可能往父節點傳。
若合併一路傳到根，且根只剩一個鍵值被拉下來，原根可被移除，樹高下降 1。
資料都在葉節點，葉節點串成雙向串列
B+ 樹把內部節點當成索引節點，只存分隔鍵值與指標；真正資料放在資料節點，也就是葉節點。所有葉節點用雙向串列串起來，因此範圍查詢找到第一個葉節點後，可以直接往右掃描。
只放鍵值與指標，用來決定搜尋往哪個子樹走，不直接放完整資料。
所有實際資料都在葉節點；內部節點只負責把搜尋導向正確葉節點。
插入到葉節點；若葉節點滿了就分裂，並把新的分隔鍵更新到上層索引。
刪除後若葉節點不足，先借用；不能借就合併，並同步更新父層索引鍵。
以插入 14 為例，資料應放在第一個葉節點；插入 86 則會讓最後一個葉節點分裂。若葉節點容量超過上限，就分裂成兩個葉節點，並把新葉節點的第一個鍵值複製到父層索引，讓搜尋能導向新的資料節點。
刪除 71 可從相鄰葉節點借用並更新父層分隔鍵；刪除 80 可能需要合併。刪除 32 或刪除 86 時，若父層索引也不足，修復會繼續往上傳。
每種搜尋樹解決的是不同瓶頸
不要把所有平衡樹都記成「某種旋轉」。先問：瓶頸是高度？搜尋機率？近期常用資料？磁碟存取？還是範圍查詢？
| 結構 | 核心想法 | 典型成本 | 適合場景 |
|---|---|---|---|
| 普通 BST | 左小右大 | 平均可好，最壞 $O(n)$ | 教學概念、資料量小、或輸入順序已隨機；不適合需要最壞情況保證的核心索引。 |
| 最佳 BST | 依搜尋機率安排根節點 | 建表 $O(n^3)$ | 查詢分布穩定、資料幾乎不更新；例如固定字典、編譯器關鍵字表。 |
| AVL 樹 | 嚴格高度平衡 | 搜尋/插入/刪除 $O(\log n)$ | 搜尋遠多於更新、需要穩定低高度；例如記憶體中的符號表、需控制查詢延遲的集合。 |
| 紅黑樹 | 用著色規則放寬平衡 | 搜尋/插入/刪除 $O(\log n)$ | 插入刪除頻繁且仍要 $O(\log n)$ 保證；例如標準函式庫的 map/set、事件集合。 |
| 伸展樹 | 操作後把目標拉到根節點 | 攤銷 $O(\log n)$ | 有快取局部性，最近查過的鍵很可能再查；例如互動式編輯器、快取表，但單次操作最壞仍可能很慢。 |
| B 樹 | 高分支、節點半滿、葉同層 | $O(\log N)$，高度很小 | 磁碟頁面或區塊存取昂貴；一個節點可對應一頁，降低樹高，適合檔案系統與資料庫索引。 |
| B+ 樹 | 資料在葉節點，葉節點串接 | 搜尋 $O(\log N)$，範圍掃描快 | 大量範圍查詢與順序掃描；葉節點串列讓區間查詢、排序輸出、資料庫索引掃描有效率。 |
如果鍵集合固定，而且每個鍵被搜尋的機率可事先估計，最佳 BST 的目標是讓常查的鍵更靠近根。
若需要一般用途的有序集合，紅黑樹常是實務預設；若搜尋比例很高、希望高度更緊，AVL 樹較合適。
如果操作序列有快取局部性，伸展樹會把最近用到的資料拉到根附近，用多次操作的平均效果換取彈性。
若主要成本是讀寫磁碟頁面或 SSD 區塊，不應只追求二元樹高度；B 樹與 B+ 樹用高分支節點減少 I/O 次數。
與線性結構的操作成本比較
| 操作 | 排序陣列 | 鏈結串列 | AVL 樹 |
|---|---|---|---|
| 搜尋 $x$ | $O(\log n)$ | $O(n)$ | $O(\log n)$ |
| 搜尋第 $k$ 筆 | $O(1)$ | $O(k)$ | $O(\log n)$ |
| 刪除 $x$ | $O(n)$ | $O(1)$（已知位置） | $O(\log n)$ |
| 插入 $x$ | $O(n)$ | $O(1)$（已知位置） | $O(\log n)$ |
| 依序輸出 | $O(n)$ | $O(n)$ | $O(n)$ |