第 10 章　搜尋結構

留意 10.6 節的定位：它解決的是第 8 章 8.3 節同一個問題（大量資料在磁碟上），但走「保持有序」的路線。把兩節並讀，就是資料庫索引設計的全貌。

「內部路徑長度（internal path length）為根到所有內部節點的路徑長度的加總。……外部路徑長度（external path length）為根到所有外部節點的路徑長度的加總。」對圖 10.3(a) 的樹：

「習題 1 証明有 $n$ 個內部節點的二元樹之內部和外部路徑長度之關係式為 $E = I + 2n$。因此，有最大 $E$ 值的二元樹也會有最大的 $I$ 值。」

令 $a_1 \lt a_2 \lt \cdots \lt a_n$ 為二元搜尋樹中的 $n$ 個識別字。令 $T_{ij}$ 表示 $a_{i+1},\ldots,a_j$（$i \lt j$）的最佳二元搜尋樹。對於 $0 \le i \le n$，令 $T_{ii}$ 為空的樹，而對 $i \gt j$，$T_{ij}$ 未定義。令 $c_{ij}$ 表示搜尋樹 $T_{ij}$ 的成本（$c_{ii}=0$），$r_{ij}$ 代表 $T_{ij}$ 之根節點（$r_{ii}=0$），且

代表 $T_{ij}$ 的權數（$w_{ii}=q_i$，$0 \le i \le n$）。$T_{0n}$ 為 $a_1,\ldots,a_n$ 的最佳樹。

「由 (10.2) 式可明白，如果 $\text{cost}(L) = c_{i,k-1}$ 且 $\text{cost}(R) = c_{kj}$ 時，$c_{ij}$ 為最小。否則，我們可將 $L$ 或 $R$ 以具有較低成本的子樹取代之，以形成 $a_{i+1},\ldots,a_j$ 的二元搜尋樹，其成本低於 $c_{ij}$。這與假設 $T_{ij}$ 是最佳的不符。」因此 (10.2) 式變成：

因 $T_{ij}$ 是最佳的，由公式 (10.3) 可知 $r_{ij} = k$ 使得：

或

「公式 (10.4) 說明我們如何由已知 $T_{ii}=0$ 且 $c_{ii}=0$ 開始，求得 $T_{0n}$ 和 $c_{0n}$。」

「所以，在最差的狀況下，二元搜尋樹相當於在有序串中的循序搜尋。但是，當識別字以隨機順序插入時，樹結構傾向於平衡，如圖 10.9。如果所有的排列有相同的機率，則可以証明有 $n$ 個節點的二元搜尋樹的平均搜尋和插入時間為 $O(\log n)$。」

「圖 10.12 以抽象的二元樹來表示 LL, LR, RR, 和 RL 旋轉。RL 旋轉與 LR 旋轉類似。圖中每一樹的根節點代表插入以後平衡因子變成 $\pm2$ 的最近的祖先。」

「在圖 10.11 的範例及圖 10.12 的旋轉中，未包含在旋轉中的子樹之高度維持不變。這表示旋轉之後不必再往上傳播 —— 每次插入最多只需要一次旋轉。」

「令 $N_h$ 為高度 $h$ 之高度平衡樹中的最小節點數。在最差情況下，子樹中有一個高度為 $h-1$，其他的為 $h-2$。這兩種子樹也都是高度平衡的。因此，」

「請留意 $N_h$ 的遞迴定義與費氏數值得定義 $F_n = F_{n-1} + F_{n-2}$，$F_0 = 0$，且 $F_1 = 1$ 之間的相似性。事實上，我們可以証明（習題 2）」

「由費氏數值定理可知 $F_h \approx \Phi^h/\sqrt5$ 其中 $\Phi = (1+\sqrt5)/2$。因此 $N_h \approx \Phi^{h+2}/\sqrt5 - 1$。這表示如果樹中有 $n$ 個節點，則其高度 $h$ 最多為」

「所以，在有 $n$ 個節點的高度平衡樹中，最差狀況的插入時間為 $O(\log n)$。」

「一內部節點的分支度為 2 或 3。分支度為 2 的節點稱為 2-節點，而分支度為 3 的節點稱為 3-節點。」

2-3 樹可能是空的樹，或者是滿足下列特性的樹：

1. 每一內部節點可能是 2-節點或是 3-節點。2-節點有一個元素，而 3-節點有兩個元素。
2. 令 left_child 和 middle_child 代表 2-節點的子節點。令 data_l 為此節點中的元素，data_l.key 為其鍵值。在以 left_child 為根節點的 2-3 子樹中的所有元素之鍵值均小於 data_l.key，而在以 middle_child 為根節點的 2-3 子樹中的所有元素之鍵值均大於 data_l.key。
3. 令 left_child、middle_child 和 right_child 代表 3-節點的子節點。令 data_l 和 data_r 為此節點中的兩個元素。則 data_l.key < data_r.key；在 left_child 的子樹中所有元素之鍵值均小於 data_l.key；在 middle_child 的子樹中所有元素之鍵值均小於 data_r.key 且大於 data_l.key；在 right_child 的子樹中所有元素之鍵值均大於 data_r.key。
4. 所有的外部節點在同一階層上。

「我們需要這個堆疊是因為在節點分裂以後，我們必須處理被分裂的節點之父節點。」—— 2-3 樹的插入是由下而上的：先往下找到葉節點，插入；若該節點已是 3-節點就分裂，中間元素上推給父節點；父節點若也滿了就繼續分裂……這個往上傳播的過程需要記住來時路，所以要堆疊。

用 INT_MAX 當「這個欄位沒有元素」的標記（p->data_r.key == INT_MAX 表示是 2-節點）—— 這是本章反覆使用的技巧，在 10.4 節的 2-3-4 樹也看得到。

「個別的旋轉或合併作業所需時間為 $O(1)$ 是很明顯的。如果執行旋轉，刪除即結束。如果執行合併，$p$ 在 2-3 樹中向上移動一個階層。所以，在一次刪除期間可以執行的合併次數不會超過 2-3 樹的高度。所得到的結討是從 $n$ 個元樹的 2-3 樹中刪除元素需要 $O(\log n)$ 時間。□」

「2-3-4 樹由 2-3 擴充，使其容許有 4-節點（4-節點最多有四個子節點）。」

2-3-4 樹為一搜尋樹，它可能是空的，或者滿足下列的特性：

1. 每一內部節點為 2-, 3-, 或 4-節點。2-節點有一個元素，3-節點有二個元素，而 4-節點有三個元素。
2. （2-節點的子樹順序規則，同 2-3 樹）
3. （3-節點的子樹順序規則，同 2-3 樹）
4. 令 left_child、left_mid_child、right_mid_child 和 right_child 表示 4-節點的子節點。令 data_l、data_m 和 data_r 為此節點中的三個元素。則 data_l.key < data_m.key < data_r.key，且四棵子樹的鍵值範圍依序被這三個元素分隔。

注意程式的結構：往下走的路上，一遇到 4-節點就立刻分裂它（if (four_node(p)) split_...），不等到真的需要。

這樣做的回報是：當我們抵達葉節點時，它一定不是 4-節點，所以插入必定成功、不必往上傳播。因此 2-3-4 樹的插入是由上而下的一趟（one-pass），不需要堆疊 —— 對照 2-3 樹的插入必須由下而上、需要堆疊。

多一種節點型態，換來的是演算法結構上的簡化。這在並行環境下特別重要（不必持有整條路徑的鎖）。

「(2) 一個 3-節點 $p$ 以兩個用紅指標連接的 red_black 節點表示。有兩種方式可以完成它（見圖 10.26，其中 color 欄位未畫出）。(3) 一個 4-節點以三個 red_black 節點表示，其中有一個以紅指標和另外兩個連接（見圖 10.27）。」

• (Q2) 每一外部節點的等級為 0。
• (Q3) 一個內部節點，它是外部節點的父節點時，等級為 1。
• (Q4) 一個有父節點 $p(x)$ 的內部節點 $x$，其 $\text{rank}(x) \le \text{rank}(p(x)) \le \text{rank}(x)+1$。
• (Q5) 一個有祖父節點 $qp(x)$ 的內部節點 $x$，其 $\text{rank}(x) \lt \text{rank}(qp(x))$。

每一有 $n$ 個（內部）節點的紅-黑樹 $RB$ 滿足下列各式：

1. $\text{height}(RB) \le 2\lceil \log_2(n+1)\rceil$
2. $\text{height}(RB) \le 2\,\text{rank}(RB)$
3. $\text{rank}(RB) \le \lceil \log_2(n+1)\rceil$

(1) 就是紅黑樹的核心保證：高度不超過完美平衡樹的兩倍。理由是 (2)+(3)：rank（黑高度）最多 $\log_2(n+1)$，而每一層 rank 之間最多夾一條紅指標，所以實際高度最多是 rank 的兩倍。

「插入可用兩種方式來執行：由上而下或由下而上。在由上而下插入中，在紅-黑樹中只做了一次由根到葉節點的處理過程。由下而上的插入則做了由根到葉節點與由葉節點到根的二次處理過程。」

「在分支度為 $m$ 高度為 $h$ 的樹中，最大的節點個數為 $\sum_{0 \le i \le h-1} m^i = (m^h-1)/(m-1)$。因每一節點最多有 $m-1$ 個鍵值，在高度為 $h$ 的 m-路樹索引中最大的鍵值個數為 $m^h - 1$。」

「明顯地，高分支度的搜尋樹之潛力比低分支度的搜尋樹大得多。想要得到一個效率，使它非常接近 $n$ 個鍵值的 m-路搜尋樹之最佳效率時，這個搜尋樹必須是平衡的。我們將要討論的一種平衡的 m-路搜尋樹的特別變化稱為 B-樹。」

度數（order）為 $m$ 的 B-樹是一個 m-路搜尋樹，它可能是空的，或者滿足下列特性：

1. 根節點至少有兩個子節點。
2. 其餘的各個非失敗節點至少有 $\lceil m/2 \rceil$ 個子節點。
3. 所有失敗節點在同一階層上。

「在定義 B-樹時，習慣重新提出失敗節點的觀念。請記住失敗節點代表在搜尋時，如果要找尋的值 $x$ 不在樹中才可到達的節點。」

「的索引之 $l \le \log_{100}\{(n+1)/2\} + 1$。因 $l$ 為整數，可得到 $l \le 3$。對 $n \le 2\times10^8 - 2$，可得到 $l \le 4$。所以，使用高度數的 B-樹所得到的結果是，即使資料項的個數非常多，一個樹結構索引可以用很少的磁碟存取次數來搜尋。」

兩億筆資料，四次磁碟存取。這就是為什麼幾乎所有的資料庫索引都是 B 樹或 B+ 樹。

「為了達到比較合理的 $m$ 的選擇，我們必須記住我們真正的目的在使得搜尋 B-樹中的一個鍵值 $x$ 所需全部時間為最小。這個時間有兩個組成因素，其一，從磁碟讀取一個節點的時間，其二，找尋有 $x$ 值的節點。」

假設一個節點的大小約為 $m(\alpha + 2\beta)$ 字元，則讀取一個節點所需的時間 $t_i$ 為：

其中 $a = t_s + t_l =$ 找尋的時間 + 延遲時間，$b = (\alpha+2\beta)t_c$，$t_c =$ 每一字元的傳送時間。

「如果以二分搜尋法找尋 B-樹的每一節點，則每一節點的內部處理時間為 $c\log_2 m + d$，$c$ 和 $d$ 為常數值。」所以每一節點全部的處理時間為 $a + bm + c\log_2 m + d$，而總時間為這個乘上樹的高度 $\approx \log_{\lceil m/2\rceil} n$。

「AVL，2-3，2-3-4，和紅-黑樹允許我們在 $O(\log n)$ 最差狀況時間內完成每一個搜尋樹的運算：插入，刪除和搜尋。在優先權佇列的例子中我們已看到，如果我們對分攤成本而不是對最差狀況複雜度有興趣，則可使用較簡單的結構。這對搜尋樹也是成立的。使用外張樹時，每一搜尋樹運算可以在 $O(\log n)$ 分攤時間內完成。」

「外張樹（splay tree）是一種二元搜尋樹，其中每一搜尋，插入，和刪除的方法都與原始的二元的搜尋樹（見第 5 章）相同。但是，在每一運算之後跟著一個向外張開（splay）運算。外張運算由一連串的旋轉構成。」

沒有平衡因子、沒有顏色、沒有等級 —— 節點結構與第 5 章的 BST 完全相同。全部的智慧都在「每次操作後把剛碰過的節點旋轉到根」這一條規則裡。

「外張樹分析則使用一種潛能（potential）技巧。令 $p_0$ 為搜尋樹最初的潛能，$p_i$ 為在一連串 $n$ 個運算的第 $i$ 個運算後的潛能。定義第 $i$ 個運算的分攤時間為：」

「就是說，分攤時間為實際時間加上潛能的改變。重新排列各項，可發現第 $i$ 個運算的實際時間為：」

「因此，執行連續 $n$ 個運算所需的實際時間為：」

「數位搜尋樹的搜尋，插入和刪除程序式與二元樹的相關程序式非常的類似。基本的差別在於要移到那個子樹由搜尋鍵值的位元來決定，而不是由搜尋鍵值與現行節點的鍵值比較結果來決定。」

「各個上述搜尋樹運算可以在 $O(h)$ 時間內完成，其中 $h$ 為數位搜尋樹的高度。假設數位搜尋樹中的每一鍵值有 keysize 位元，則此數位搜尋樹的高度至多為 keysize + 1。」

「假設我們有很長的鍵值，則鍵值比較的成本是很高的。我們可以將鍵值比較次數降為 1，只要利用一種相關的結構即可，稱其為 Patricia（Practical algorithm to retrieve information coded in alphanumeric）。」

三個發展步驟：「我們以三個步驟來發展這個結構。首先，我們介紹一種結構稱為 binary trie。接著將 binary trie 轉換成 compressed binary trie。最後，由 compressed binary trie 得到 Patricia。因為 binary trie 和 compressed binary trie 僅是做為達成 Patricia 的方法，我們並未深入討論如何處理這些結構。」

「Binary trie 為一種二元搜尋樹，它有兩種節點分支節點（branch node）和元素節點（element node）。分支節點有兩個欄位 left_child 和 right_child。它沒有資料欄位。一個元素節點有一個 data 欄位。我們以分支節點來建立類似數位搜尋樹的二元樹搜尋結構。這種搜尋結構指向元素節點。」

1. if (!t) return NULL; —— 走到空的分支，鍵值不在樹中。
2. if (t->tag == data) —— 到達元素節點，做唯一的一次 strcmp 確認。
3. 否則，用 get_index(key,i) 取出第 $i$ 層的取樣值，往對應的分支繼續。

「此函數使用函數 get_index(key,i)，它執行第 $i$ 階層的鍵值取樣。在由左至右，單一字元的取樣中，此函數抽取鍵值的第 $i$ 個字元，並將它轉成一個整數值索引，以指出要使用分支節點的那一個指標欄位。」

「搜尋函數是直接的，我們可以驗証其最差狀況搜尋時間為 $O(l)$ 中 $l$ 是 trie 中的階層數（包括分支和元素兩種節點在內）。□」

注意「呼叫它以前，已經將一個空白附加在搜尋鍵值之後」—— 空白當作字串結尾的哨兵，確保短的鍵值能正確終止。

「對於一個索引的全部節點都儲存在磁碟的情況而言，搜尋時最多需要 $l$ 次的存取。給予一組要以索引表示的鍵值，trie 中的階層數根據用來決定每一階層的分歧之鍵值取樣方法而定。我們可使用取樣函數 sample(x,i) 來定義」取樣策略。

常見的取樣策略：由左至右取單一字元（最直觀）；由右至左（對有共同字首的鍵值更好）；挑選特定位置的字元（如果知道某些位置區分度高，可大幅降低樹高）。這與第 8 章 8.2.2 節的「數位分析法」是完全相同的思路。

^† 由下而上，需要堆疊。  ^‡ 由上而下一趟完成，不需要堆疊。

1. $E = I + 2n$；$s = (1+1/n)u - 1$。傾斜樹 $I = n(n-1)/2$，完整二元樹 $I = O(n\log n)$。
2. 最佳 BST：$c_{ij} = w_{ij} + c_{i,k-1} + c_{kj}$，遞迴式 (10.4)，$O(n^3)$；用 Knuth 的單調性降到 $O(n^2)$。
3. AVL：四種旋轉（LL/RR 單、LR/RL 雙），每次插入最多一次旋轉。$N_h = F_{h+2}-1$，$h \le \log_\Phi(\sqrt5(n+1))-2$。
4. Karlton 實驗：53.49% 不需旋轉、23.24% 單旋轉、23.24% 雙旋轉。
5. 2-3 樹插入由下而上（要堆疊）；2-3-4 樹預先分裂，由上而下一趟（不要堆疊）。
6. 2-3 樹刪除：兄弟是 3-節點就旋轉（結束）；是 2-節點就合併（往上傳播）。
7. 紅黑樹：紅指標連接同等級節點（2-3-4 節點內部），黑指標降一級。$\text{height}(RB) \le 2\lceil\log_2(n+1)\rceil$。
8. B 樹：根至少 2 個子節點，其餘至少 $\lceil m/2\rceil$ 個，所有失敗節點同一階層。$m=3$ 是 2-3 樹、$m=4$ 是 2-3-4 樹。$m$ 由磁碟區塊大小決定。
9. 外張樹：節點結構與普通 BST 相同，每次運算後 splay 到根，用潛能法證明分攤 $O(\log n)$。
10. Trie：按位元／字元分歧而非比較鍵值，高度由鍵值長度決定，與 $n$ 無關。