二叉搜尋樹

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

二叉搜尋樹
類型	樹
發明時間	1960年
發明者	P.F.溫德利、安德魯·唐納德·布思、安德魯·科林、托馬斯·N·希巴德
用大O符號表示的時間複雜度 演算法 平均 最差 搜尋 O(log n) O(n) 插入 O(log n) O(n) 刪除 O(log n) O(n) 尋找最小值 O(log n) O(n) 刪除最小值 O(log n) O(n) 用大O符號表示的空間複雜度 空間 O(n) O(n)

「binary search tree」的各地常用譯名
中國大陸	二叉搜索樹[1]:163、二叉查找樹[2]:250
港澳	二叉搜尋樹[3]
臺灣	二元搜尋樹[4]:6-11

一棵二叉搜尋樹，其節點數為9，高度為3，根節點為8

二叉搜尋樹每次比較都能排除大約一半的剩餘節點，故能以對數時間尋找、插入、刪除數據。但其效能依賴於節點的插入順序，插入隨機鍵值時仍能維持對數級別，但在最壞情況（英語：Best, worst and average case）下會退化成鏈結串列。為保證效率，研究者發明了多種平衡樹，能將最壞尋找複雜度維持在${\displaystyle O(\log n)}$。

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

歷史

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

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

性質

二叉搜尋樹為有根的二叉樹，其節點順序為嚴格全序關係，每個節點都滿足：左子樹上所有節點的鍵值都小於該節點，右子樹上所有節點的鍵值都大於該節點。這一結構保證可以在對數時間內定位任意鍵值。^{[15]:298[16]:287[1]:161-162}除尋找外，其也常用於排序，但效能取決於節點的插入和刪除順序——在最壞情況（英語：Best, worst and average case）下，連續操作可能使樹退化為類似單鏈結串列的結構，這時的尋找複雜度與鏈結串列相同。^{[15]:299-302[17]}

遍歷

主條目：樹的遍歷

參見：線索二叉樹

二叉搜尋樹的遍歷有三種基本方法：前序、中序、後序。^{[16]:287[1]:162}

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

以下是遞歸實現的遍歷偽代碼：^{[16]:287–289[1]:162}

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

操作

搜尋

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

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

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

重複上述步驟，直到找到該鍵，或者剩餘子樹為空。若到達空子樹仍未找到，說明該鍵不存在於樹中。^{[16]:290-291[1]:163}

遞歸搜尋

以下偽代碼展示遞歸方式實現的尋找過程：^{[16]:290[1]:163}

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

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

迭代搜尋

遞歸過程也可展開為循環形式，一般情況下循環版本的效率更高。其偽代碼如下：^{[16]:291[1]:163}

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

由於尋找可能會一直到葉節點，因此時間複雜度為樹的高度${\displaystyle O(h)}$（${\displaystyle h}$為樹的高度）。^{[16]:290[1]:163}在最壞情況下，一棵嚴重不平衡的二叉搜尋樹可能退化成單鏈結串列，這時複雜度會達到${\displaystyle O(n)}$（${\displaystyle n}$為樹中節點總數）。但對於高度平衡的二叉搜尋樹而言，複雜度為${\displaystyle O(\log n)}$。^{[10]:458–459[18]:403[2]:255}

後繼與前驅

在某些場景下，需要尋找給定節點的「後繼」或「前驅」。後繼節點是大於該節點鍵值的節點中，鍵值最小的那一個；前驅節點是小於該節點鍵值的節點中，鍵值最大的那一個。以下偽代碼給出求節點${\displaystyle {\text{x}}}$的後繼與前驅方法：^{[19][20][16]:292–293[1]:164}

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

尋找樹中鍵值最大或最小的節點，是尋找後繼與前驅過程中的重要環節。其偽代碼如下：^{[16]:291–292[1]:163–164}

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

選擇與排名

若在節點中維護以之為根節點的子樹的節點總數，則可實現選擇與排名操作。選擇操作用於在樹中直接定位排名為${\displaystyle k}$的節點，即第${\displaystyle k}$小的鍵。^{[18]:406–407[2]:257–258}排名操作則與之相對，給定指定鍵後，其會返回小於該鍵的節點數。^{[18]:408[2]:258–259}這兩種操作的偽代碼如下：^{[18]:409[2]:258–259}

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 Rank(key, x.left) else if cmp > 0 then return 1 + size(x.left) + Rank(key, x.right) else return size(x.left) end if

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

範圍尋找

利用中序遍歷，可以實現範圍尋找（英語：Range query (computer science)），即查詢兩個給定值之間的元素數量。其偽代碼如下：^{[18]:412–413[2]:261–262}

Range-Query(x, lo, hi, list) if x = NIL then return end if if lo < x.key then Range-Query(x.left, lo, hi, list) end if if lo ≤ x.key ≤ hi then list.append(x.key) end if if hi > x.key then Range-Query(x.right, lo, hi, list) end if

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

插入

二叉搜尋樹的數據結構會隨插入和刪除操作而變化。插入操作須保證二叉搜尋樹的性質不會遭到破壞，且插入的節點總是作為葉節點加入。^{[16]:294–295[1]:165–166}以下偽代碼給出迭代形式的插入過程：^{[16]:294[1]:165–166}

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

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

刪除

二叉搜尋樹刪除節點的過程

從樹中刪除某個節點${\displaystyle {\text{Z}}}$時，需分三種情況處理：^{[16]:295-297[1]:166-167}

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

以下偽代碼實現刪除操作：^{[16]:296-298[1]:167-168}

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

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

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

平衡樹

主條目：平衡樹

普通的二叉搜尋樹中，若不加以平衡，插入或刪除操作可能會導致樹退化。^[21]若是使用隨機鍵值構建二叉搜尋樹，那麼平均高度仍能維持在對數級別（當節點數${\displaystyle n}$足夠大時，高度趨近於${\displaystyle 2.99\lg n}$）；^{[18]:413[2]:263}但在最壞情況（英語：Best, worst and average case）下，高度會達到節點數${\displaystyle n}$，尋找效能退化至線性搜尋的水平。^[21]要保持二叉搜尋樹的高效，關鍵在於通過「自平衡」機制，使樹的高度始終維持在${\displaystyle O(\log n)}$級別。^{[10]:458–459[22]:50[18]:414[2]:263}

高度平衡樹

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

加權平衡樹

主條目：加權平衡樹

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

其他類型

常見的自平衡二叉搜尋樹包括：T樹（英語：T-tree）^[24]、樹堆^[25]、紅黑樹^{[16]:273[1]:174}、B樹^[26]、2-3樹^[10]:483、伸展樹^[27]。

應用

排序

主條目：樹排序（英語：Tree sort）

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

優先佇列

主條目：優先佇列

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

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

參見

• 搜尋樹
• 最佳化二元搜尋樹
• 二叉搜尋樹的幾何性質（英語：Geometry of binary search trees）
• 三叉搜尋樹

註腳