3.1 二元搜尋樹

二元搜尋樹(binary search tree)是一類樹狀資料結構的統稱。簡單的二元搜尋樹是一種類似 ITree 的結構（為說明方便，我們讓樹中的元素皆為 Int）：

data BTree = Nul | Nod BTree Int BTree 

另有個附加限制：在所有內部節點 Nod t x u 中，t 之中的所有元素均小於 x, u 之中的所有元素均大於 x. 以下我們將此限制簡稱為「有序性」。 給定一個有序的二元搜尋樹 t，下述函數 search k t 判斷 k 是否出現在 t 之中：

search :: Int -> BTree -> Bool
search k Nul          = False
search k (Nod t x u)  | k < x   = search k t
                      | k == x  = True
                      | x < k   = search k u 

這是一個歸納定義。由於有序性，每遇到一個 Nod t x u 節點，我們可比較 k 與 x 的大小，藉以決定往哪一個子樹做搜尋。

如果二元樹是平衡的 --- 意指在樹中的每個 Nod t x u 之中，t 和 u 的元素數目大致相等，或著至少其比例為某個常數，search k (Nod t x u) 每次選擇往 t 或 u 搜尋時都會排除一定比例的元素。如此一來，搜尋一個含 n 個元素的樹可在 $O(\log n)$ 的時間內完成。 然而，維持「平衡」並不容易，也是各種二元搜尋樹各顯神通之處。

以下我們多給一些定義，以便更形式化地描述有序性。我們假設有個抽象的「集合」型別 Set a. 含單一元素 x 的集合寫成 singleton x; 聯集寫作 (∪), 並具有結合律、交換律等性質。下述函數 elems 傳回一個樹中的所有元素（類似練習 2.33 中的 tags）：

elems :: BTree -> Set Int
elems Nul          = []
elems (Nod t x u)  = elems t ∪ singleton x ∪ elems u 

有序性可表示為下列述語 sorted:

sorted :: BTree -> Bool
sorted Nul          =  True
sorted (Nod t x u)  =  all (<x) (elems t) ⋀ all (x<) (elems u) ⋀
                       sorted t ⋀ sorted u 

其中 all :: (a -> Bool) -> Set a -> Bool 檢查一個集合中的元素是否均滿足某述語。函數 all 滿足以下性質：

all p empty          = True
all p (singleton x)  = p x
all p (s ∪ t)  = all p s ⋀ all p t 

在二元搜尋樹中插入新元素的函數可定義如下：

insert :: Int -> BTree -> BTree
insert k Nul          = Nod Nul k Nul
insert k (Nod t x u)  | k < x   = Nod (insert k t) x u
                      | k == x  = Nod t x u
                      | x < k   = Nod t x (insert k u) 

函數 insert 和 search 的結構很類似：都藉由比較 k 與 x 決定該往哪兒插入元素；函數 search 只在碰到 Nul 時才能傳回 False, 函數 insert k 也只將 Nod Nul k Nul 放在原本 Nul 出現之處 --- 新插入的節點永遠是最邊緣的葉節點。

我們自然會希望 insert 保持有序性：如果 t 是有序的，insert k t 也應該是。表示為定理如下：

     sorted (insert k (Nod t x u))
<=>   {- insert 之定義, k < x -}
     sorted (Nod (insert k t) x u)
<=>   {- sorted 之定義 -}
     all (<x) (elems (insert k t)) ⋀ all (x<) (elems u) ⋀
     sorted (insert k t) ⋀ sorted u
<=>   {- 練習 3.1: elems (insert k t) = singleton k ∪ elems t -}
     all (<x) (singleton k ∪ elems t) ⋀ all (x<) (elems u) ⋀
     sorted (insert k t) ⋀ sorted u
<=>   {- all 之性質 -}
     k < x ⋀ all (<x) (elems t) ⋀ all (x<) (elems u) ⋀
     sorted (insert k t) ⋀ sorted u
<==   {- k < x, 歸納假設 -}
     all (<x) (elems t) ⋀ all (x<) (elems u) ⋀
     sorted t ⋀ sorted u
<=>   {- sorted 之定義 -}
     sorted (Nod t x u) 

函數 insert 並不保證做出的樹能平衡 --- 恰恰相反，我們一不小心便會做出偏一邊的樹。例如， insert 5 (insert 4 (insert 3 (insert 2 (insert 1 Nul)))) 得到的結果會是：

  Nod Nul 1 (Nod Nul 2 (Nod Nul 3 (Nod Nul 4 (Nod Nul 5 Nul)))) 

在這個樹中搜尋 5, 和在串列 [1,2,3,4,5] 之中尋找 5 基本上是一樣的。

許多建立在二元搜尋樹的進階資料結構會在插入元素時多做些操作，想辦法維持樹的平衡。 我們將在第3.2 節介紹的紅黑樹就是一個例子。