二元搜尋樹

二叉搜索樹（binary search tree，簡稱BST）又稱有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree）。是一種有根二叉樹數據結構。它要求每個內部節點的鍵值都大於其左子樹中所有節點的鍵值，且都小於其右子樹中所有節點的鍵值。該樹各項操作時間複雜度均與樹的高度成線性關係。

二叉搜索樹每次比較都能排除大約一半的剩餘節點，故能以對數時間查找、插入、刪除數據。但其性能依賴於節點的插入順序，插入隨機鍵值時仍能維持對數級別，但在最好、最壞、平均情況下會退化成鍊表。為保證效率，研究者發明了多種平衡樹，能將最壞查找複雜度維持在$O(\log n)$。

二叉搜索樹最早由多位研究者獨立提出，1960年被用來解決帶標籤數據的存儲問題。其還可用來實現樹排序及優先隊列。

## 歷史

二叉搜索樹最早由多位研究者獨立提出，包括P.F.溫德利、安德魯·唐納德·布思、安德魯·科林、托馬斯·N·希巴德。這種數據結構常被歸功於康威·柏納-李及大衛·惠勒，他們在1960年將之用於磁帶上帶標籤數據的存儲。希巴德實現二叉搜索樹的方法也是最早廣為流傳的一種。

若按任意順序插入節點，樹的高度可能接近節點數，導致操作效率急劇下降。研究者們發明了平衡樹（即能夠自平衡的二叉搜索樹），將樹的高度限制在$O(\log n)$以內。同時，相關人員也提出了多種高度平衡的二叉搜索樹結構，例如AVL樹、樹堆、紅黑樹等。其中，AVL樹是首類平衡樹，由格奧爾吉·阿傑爾松-韋利斯基及葉夫根尼·蘭迪斯於1962年發明，用於高效組織資訊。

## 性質

二叉搜索樹為有根節點的二叉樹，其節點順序為嚴格全序關係，每個節點都滿足：左子樹上所有節點的鍵值都小於該節點，右子樹上所有節點的鍵值都大於該節點。這一結構保證可以在對數時間內定位任意鍵值。除查找外，其也常用於排序，但性能取決於節點的插入和刪除順序——在最好、最壞、平均情況下，連續操作可能使樹退化為類似單鍊表的結構，這時的查找複雜度與鍊表相同。

## 遍歷

二叉搜索樹的遍歷有三種基本方法：前序、中序、後序。

- 中序遍歷：依次遍歷左子樹、根節點、右子樹。遍歷結果為鍵值遞增順序。
- 前序遍歷：依次遍歷根節點、左子樹、右子樹。
- 後序遍歷：依次遍歷左子樹、右子樹、根節點。

以下是遞歸實現的遍歷偽代碼：

Inorder-Tree-Walk(x) if x ≠ NIL then Inorder-Tree-Walk(x.left) visit node Inorder-Tree-Walk(x.right) end if｜Preorder-Tree-Walk(x) if x ≠ NIL then visit node Preorder-Tree-Walk(x.left) Preorder-Tree-Walk(x.right) end if｜Postorder-Tree-Walk(x) if x ≠ NIL then Postorder-Tree-Walk(x.left) Postorder-Tree-Walk(x.right) visit node end if

## 操作

### 搜索

在二叉搜索樹中查找某個特定的鍵，可以使用遞歸或迭代方式實現。

查找過程從樹的根節點開始：

- 如果根節點為空（$\text{nil}$），說明該鍵不存在。
- 如果根節點的鍵值與目標鍵值相等，返回該節點，表示查找成功。
- 如果目標鍵值小於根節點的鍵值，則繼續在左子樹中查找。
- 如果目標鍵值大於根節點的鍵值，則繼續在右子樹中查找。

重複上述步驟，直到找到該鍵，或者剩餘子樹為空。若到達空子樹仍未找到，說明該鍵不存在於樹中。

#### 遞歸搜索

以下偽代碼展示遞歸方式實現的查找過程：

Recursive-Tree-Search(x, key) if x = NIL or key = x.key then return x if key < x.key then return Recursive-Tree-Search(x.left, key) else return Recursive-Tree-Search(x.right, key) end if

遞歸會一直進行，直到遇到$\text{nil}$或是找到目標鍵$\text{key}$。

#### 迭代搜索

遞歸過程也可展開為循環形式，一般情況下循環版本的效率更高。其偽代碼如下：

Iterative-Tree-Search(x, key) while x ≠ NIL and key ≠ x.key do if key < x.key then x := x.left else x := x.right end if repeat return x

由於查找可能會一直到葉節點，因此時間複雜度為樹的高度$O(h)$（$h$為樹的高度）。在最壞情況下，一棵嚴重不平衡的二叉搜索樹可能退化成單鍊表，這時複雜度會達到$O(n)$（$n$為樹中節點總數）。但對於高度平衡的二叉搜索樹而言，複雜度為$O(\log n)$。

#### 後繼與前驅

在某些場景下，需要查找給定節點的「後繼」或「前驅」。後繼節點是大於該節點鍵值的節點中，鍵值最小的那一個；前驅節點是小於該節點鍵值的節點中，鍵值最大的那一個。以下偽代碼給出求節點$\text{x}$的後繼與前驅方法：

BST-Successor(x) if x.right ≠ NIL then return BST-Minimum(x.right) end if y := x.parent while y ≠ NIL and x = y.right do x := y y := y.parent repeat return y｜BST-Predecessor(x) if x.left ≠ NIL then return BST-Maximum(x.left) end if y := x.parent while y ≠ NIL and x = y.left do x := y y := y.parent repeat return y

尋找樹中鍵值最大或最小的節點，是尋找後繼與前驅過程中的重要環節。其偽代碼如下：

BST-Maximum(x) while x.right ≠ NIL do x := x.right repeat return x｜BST-Minimum(x) while x.left ≠ NIL do x := x.left repeat return x

#### 選擇與排名

若在節點中維護以之為根節點的子樹的節點總數，則可實現選擇與排名操作。選擇操作用於在樹中直接定位排名為$k$的節點，即第$k$小的鍵。排名操作則與之相對，給定指定鍵後，其會返回小於該鍵的節點數。這兩種操作的偽代碼如下：

Select‑By‑Rank(T, k) return Select(T.root, k) Select(x, k) if x = NIL then return NIL end if t := size(x.left) if t > k then return Select(x.left, k) else if t < k then return Select(x.right, k − t − 1) else return x end if

Rank-In-Tree(T, key) return Rank(key, T.root) Rank(key, x) if x = NIL then return 0 cmp := compare(key, x.key) if cmp 0 then return 1 + size(x.left) + Rank(key, x.right) else return size(x.left) end if

其中`size`表示子樹規模資訊，即子樹中節點數量。

#### 範圍查找

利用中序遍歷，可以實現範圍查找 (電腦科學)，即查詢兩個給定值之間的元素數量。其偽代碼如下：

Range-Query(x, lo, hi, list) if x = NIL then return end if if lo x.key then Range-Query(x.right, lo, hi, list) end if

其中`list`是用來收集結果的列表（也可視作隊列）。上述過程將所有符合條件的值加入列表中，並跳過不可能含有目標值的子樹。

### 插入

二叉搜索樹的數據結構會隨插入和刪除操作而變化。插入操作須保證二叉搜索樹的性質不會遭到破壞，且插入的節點總是作為葉節點加入。以下偽代碼給出迭代形式的插入過程：

1 BST-Insert(T, z) 2 y := NIL 3 x := T.root 4 while x ≠ NIL do 5 y := x 6 if z.key < x.key then 7 x := x.left 8 else 9 x := x.right 10 end if 11 repeat 12 z.parent := y 13 if y = NIL then 14 T.root := z 15 else if z.key < y.key then 16 y.left := z 17 else 18 y.right := z 19 end if

過程使用變量$\text{y}$作為遍歷節點$\text{x}$的父節點（追蹤指針）。初始時如果$\text{y}$為$\text{nil}$，說明樹為空，新節點$\text{z}$即作為樹的根；否則，需根據節點鍵值大小關係插入對應位置。

### 刪除

<image>

從樹中刪除某個節點$\text{Z}$時，需分三種情況處理：

- $\text{Z}$是葉節點：直接用空指針替換即可。（如圖中(a)）
- $\text{Z}$僅有一個子節點：用$\text{Z}$的子節點替換$\text{Z}$。（如圖中(b)、(c)）
- $\text{Z}$有兩個子節點：用$\text{Z}$的中序遍歷所得到的後繼或前驅$\text{Y}$代替$\text{Z}$。此處以後繼為例：
- 如果$\text{Y}$恰好是$\text{Z}$的右子節點：直接用$\text{Y}$取代$\text{Z}$，$\text{Y}$的右子樹保持不變。（如圖中(d)）
- 如果$\text{Y}$位於$\text{Z}$的右子樹內部：先用$\text{Y}$的右子節點替換$\text{Y}$，再用$\text{Y}$替代$\text{Z}$。（如圖中(e)）

以下偽代碼實現刪除操作：

1 BST-Delete(BST, z) 2 if z.left = NIL then 3 Shift-Nodes(BST, z, z.right) 4 else if z.right = NIL then 5 Shift-Nodes(BST, z, z.left) 6 else 7 y := BST-Successor(z) 8 if y.parent ≠ z then 9 Shift-Nodes(BST, y, y.right) 10 y.right := z.right 11 y.right.parent := y 12 end if 13 Shift-Nodes(BST, z, y) 14 y.left := z.left 15 y.left.parent := y 16 end if 1 Shift-Nodes(BST, u, v) 2 if u.parent = NIL then 3 BST.root := v 4 else if u = u.parent.left then 5 u.parent.left := v 5 else 6 u.parent.right := v 7 end if 8 if v ≠ NIL then 9 v.parent := u.parent 10 end if

$\text{BST-Delete}$過程根據上述3種情況處理節點刪除：第1種情況（葉節點）對應第2—3行；第2種情況（單個子節點）對應第4—5行；第3種情況（有兩個子節點）對應第6—16行。輔助函數$\text{Shift-Nodes}$用於把節點$\text{u}$替換成$\text{v}$。

若在第3種情況中，僅選用後繼或前驅節點中的一種，則並未考慮到樹的對稱性，可能會導致性能問題。若要避免此問題，可以隨機選擇使用後繼或前驅。

## 平衡樹

普通的二叉搜索樹中，若不加以平衡，插入或刪除操作可能會導致樹退化。若是使用隨機鍵值構建二叉搜索樹，那麼平均高度仍能維持在對數級別（當節點數$n$足夠大時，高度趨近於$2.99 \lg n$）；但在最好、最壞、平均情況下，高度會達到節點數$n$，查找性能退化至線性搜索的水準。要保持二叉搜索樹的高效，關鍵在於通過「自平衡」機制，使樹的高度始終維持在$O(\log n)$級別。

### 高度平衡樹

若一棵樹的任意節點，其左右子樹高度之比都被某個常數所限制，就稱其為高度平衡樹。這一思想最早在AVL樹中使用，後續的紅黑樹也沿用了類似機制。每次執行插入或刪除操作後，需要沿著從根到修改節點的路徑，檢查並修正各節點的高度，以維持平衡。

### 加權平衡樹

在加權平衡樹中，平衡條件不再以高度衡量，而是以子樹的葉節點數量為準。葉節點數量即代表權重，左右子樹的權重差最多為常數$1$。但單純依靠差值，難以在插入和刪除時用$O(\log n)$的代價維護，因此引入比例因子$\alpha$，要求左右子樹的權重各自至少占整棵子樹權重的$\alpha$比例，由此形成$\alpha$-權重平衡樹族。

### 其他類型

常見的自平衡二叉搜索樹包括：T樹、樹堆、紅黑樹、B樹、2-3樹、伸展樹。

## 應用

### 排序

二叉搜索樹可用於樹排序：先將所有元素插入二叉搜索樹中，然後對樹做中序遍歷，即可得到有序序列。在快速排序的某些實現中，也可藉助二叉搜索樹來提高性能。

### 優先隊列

二叉搜索樹也可用來實現優先隊列，藉助節點的鍵值來表示優先級。插入操作與普通的二叉搜索樹相同，但刪除操作取決於優先隊列的類型：

- 升序優先隊列：移除最低優先級元素時，從根節點向左一路遍歷即可找到最小鍵。
- 降序優先隊列：移除最高優先級元素時，從根節點向右一路遍歷即可找到最大鍵。

## 外部連結

- 哈爾沙·蘇利亞納拉亞納的教學影片：pYT9F8_LFTM
- Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. (PDF; 1675 kB) 2004.

## 基本資料

- 日語原文：二叉搜索樹
- 類型：樹
- 演算法：1960年