二元搜尋樹

「binary search tree」的各地常用譯名
「binary search tree」的各地常用譯名
中國大陸	二叉搜索樹、二叉查找樹
港澳	二叉搜尋樹
臺灣	二元搜尋樹

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

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

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

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

歷史

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

若按任意順序插入節點，樹的高度可能接近節點數，導致操作效率急劇下降。研究者們發明了平衡樹（即能夠自平衡的二元搜尋樹），將樹的高度限制在 $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

操作

搜尋

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

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

如果根節點為空（ ${\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

遞迴會一直進行，直到遇到 ${\text{nil}}$ 或是找到目標鍵 ${\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

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

後繼與前驅

在某些場景下，需要尋找給定節點的「後繼」或「前驅」。後繼節點是大於該節點鍵值的節點中，鍵值最小的那一個；前驅節點是小於該節點鍵值的節點中，鍵值最大的那一個。以下虛擬碼給出求節點 ${\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

選擇與排名

若在節點中維護以之為根節點的子樹的節點總數，則可實現選擇與排名操作。選擇操作用於在樹中直接定位排名為 $k$ 的節點，即第 $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

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

刪除

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

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

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

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

平衡樹

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

高度平衡樹

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

加權平衡樹

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

其他類型

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

應用

排序

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

優先佇列

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

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

參見

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

註腳

注釋

^ 又稱有序二元樹^[5]（英語：ordered binary tree）或排序二元樹^[6]（英語：sorted binary tree）。

來源

^ ^1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 ^1.14 ^1.15 ^1.16 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 算法导论. 由殷建平; 徐雲; 王剛; 劉曉光; 蘇明; 鄒恆明; 王宏志翻譯第3版. 北京市: 機械工業出版社. 2013. ISBN 978-7-111-40701-0 （中文（中國大陸））.
^ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 Sedgewick, Robert; Wayne, Kevin. 算法. 由謝路雲翻譯第4版. 北京市: 人民郵電出版社. 2012. ISBN 978-7-115-29380-0 （中文（中國大陸））.
^ 香港特別行政區政府教育局課程發展處科技教育組. 中學資訊及通訊科技科常用英漢辭彙 (PDF). 中華人民共和國香港特別行政區教育局: 7. 2023-01 [2025-05-18]. （原始內容存檔 (PDF)於2025-04-09）（中文（香港））.
^ 胡昭民. 圖解資料結構x演算法：運用C語言. 新北市: 博碩文化股份有限公司. 2022. ISBN 978-626-333-119-8 （中文（臺灣））.
^ 吳海輝; 吳建國. 一种基于有序二叉树的高效优化索引树. 微機發展. 2004, (4): 18–21,24. CNKI WJFZ200404006 （中文（中國大陸））.
^ 王雅琳; 肖媛; 雷友誠; 桂衛華. 基于排序二叉树的摘挂列车编组钩计划自动编制方法. 中國鐵道科學. 2012, 33 (3): 116–122. CNKI ZGTK201203020 （中文（中國大陸））.
^ ^7.0 ^7.1 Culberson, J.; Munro, J. I. Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations. The Computer Journal（英語：The Computer Journal）. 1989-01-01, 32 (1): 68–69 [2025-05-11]. doi:10.1093/comjnl/32.1.68 . （原始內容存檔於2023-08-23）（英語）.
^ Culberson, J.; Munro, J. I. Analysis of the standard deletion algorithms in exact fit domain binary search trees. Algorithmica（英語：Algorithmica） (Springer Publishing（英語：Springer Publishing）, University of Waterloo). 1986-07-28, 5 (1–4): 297 [2025-05-11]. S2CID 971813. doi:10.1007/BF01840390. （原始內容存檔於2023-10-23）（英語）.
^ P. F. Windley. Trees, Forests and Rearranging. The Computer Journal（英語：The Computer Journal）. 1960-01-01, 3 (2): 84. doi:10.1093/comjnl/3.2.84  （英語）.
^ ^10.0 ^10.1 ^10.2 ^10.3 Knuth, Donald. The Art of Computer Programming 3 2. Addison-Wesley. 1998. ISBN 978-0201896855 （英語）.
^ Black, Paul E. Paul E. Black , 編. red-black tree. Dictionary of Algorithms and Data Structures. 2019-11-12 [2022-05-19]. （原始內容存檔於2009-01-23）（英語）.
^ Pitassi, Toniann. CSC263: Balanced BSTs, AVL tree (PDF). University of Toronto, Department of Computer Science: 6. 2015 [2022-05-19]. （原始內容存檔 (PDF)於2019-02-14）（英語）.
^ Myers, Andrew. CS 312 Lecture: AVL Trees. Cornell University, Department of Computer Science. [2022-05-19]. （原始內容存檔於2021-04-27）（英語）.
^ Adelson-Velsky, Georgy; Landis, Evgenii. An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences（英語：Proceedings of the USSR Academy of Sciences）. 1962, 146: 263–266 （俄語）. English translation （頁面存檔備份，存於網際網路檔案館） by Myron J. Ricci in Soviet Mathematics - Doklady, 3:1259–1263, 1962.
^ ^15.0 ^15.1 Thareja, Reema. Hashing and Collision. Data Structures Using C 2. Oxford University Press. 2018-10-13 [2025-05-11]. ISBN 9780198099307. （原始內容存檔於2025-05-09）（英語）.
^ ^16.00 ^16.01 ^16.02 ^16.03 ^16.04 ^16.05 ^16.06 ^16.07 ^16.08 ^16.09 ^16.10 ^16.11 ^16.12 ^16.13 ^16.14 ^16.15 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 2nd. MIT Press. 2001 [2025-05-11]. ISBN 0-262-03293-7. （原始內容存檔於2022-06-24）（英語）.
^ R. A. Frost; M. M. Peterson. A Short Note on Binary Search Trees. The Computer Journal（英語：The Computer Journal） (Oxford University Press). 1982-02-01, 25 (1): 158. doi:10.1093/comjnl/25.1.158 （英語）.
^ ^18.0 ^18.1 ^18.2 ^18.3 ^18.4 ^18.5 ^18.6 ^18.7 Sedgewick, Robert; Wayne, Kevin. Algorithms 4th. Upper Saddle River, New Jersey: Addison-Wesley Professional. 2011 [2025-05-11]. ISBN 978-0-321-57351-3. （原始內容存檔於2014-07-15）（英語）. Condensed web version ; book version .
^ Junzhou Huang. Design and Analysis of Algorithms (PDF). University of Texas at Arlington: 12. [2021-05-17]. （原始內容存檔 (PDF)於2021-04-13）（英語）.
^ Ray, Ray. Binary Search Tree. Loyola Marymount University, Department of Computer Science. [2022-05-17]. （原始內容存檔於2024-03-24）（英語）.
^ ^21.0 ^21.1 Thornton, Alex. ICS 46: Binary Search Trees. University of California, Irvine. 2021 [2021-10-21]. （原始內容存檔於2021-07-04）（英語）.
^ ^22.0 ^22.1 ^22.2 ^22.3 ^22.4 Brass, Peter. Advanced Data Structure. Cambridge University Press. 2011-01 [2025-05-11]. ISBN 9780511800191. doi:10.1017/CBO9780511800191. （原始內容存檔於2025-05-09）（英語）.
^ Blum, Norbert; Mehlhorn, Kurt. On the Average Number of Rebalancing Operations in Weight-Balanced Trees (PDF). Theoretical Computer Science. 1978, 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3. （原始內容存檔 (PDF)於2022-10-09）（英語）.
^ Lehman, Tobin J.; Carey, Michael J. A Study of Index Structures for Main Memory Database Management Systems. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto. 1986-08. ISBN 0-934613-18-4 （英語）.
^ Aragon, Cecilia R.; Seidel, Raimund. 30th Annual Symposium on Foundations of Computer Science. Washington, D.C.: IEEE Computer Society Press: 540–545. 1989. ISBN 0-8186-1982-1. doi:10.1109/SFCS.1989.63531 （英語）.
^ Comer, Douglas. The Ubiquitous B-Tree. Computing Surveys. 1979-06, 11 (2): 123–137. ISSN 0360-0300. S2CID 101673. doi:10.1145/356770.356776  （英語）.
^ Sleator, Daniel D.; Tarjan, Robert E. Self-Adjusting Binary Search Trees (PDF). Journal of the ACM. 1985, 32 (3): 652–686. S2CID 1165848. doi:10.1145/3828.3835 （英語）.
^ Narayanan, Arvind. COS226: Binary search trees. Princeton University School of Engineering and Applied Science（英語：Princeton University School of Engineering and Applied Science）. 2019 [2021-10-21]. （原始內容存檔於2021-03-22） –透過cs.princeton.edu （英語）.
^ Xiong, Li. A Connection Between Binary Search Trees and Quicksort. Oxford College of Emory University, The Department of Mathematics and Computer Science. [2022-06-04]. （原始內容存檔於2021-02-26）（英語）.
^ Myers, Andrew. CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps. Cornell University, Department of Computer Science. [2021-10-21]. （原始內容存檔於2021-10-21）（英語）.

延伸閱讀

本條目參照的公有領域材料。材料來自NIST的文件：Black, Paul E. Binary Search Tree. 演算法與資料結構辭典（英語：Dictionary of Algorithms and Data Structures）.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 12: Binary search trees, 15.5: Optimal binary search trees. Introduction to Algorithms 2nd. MIT Press. 2001: 253–272, 356–363. ISBN 0-262-03293-7 （英語）.
Jarc, Duane J. Binary Tree Traversals. Interactive Data Structure Visualizations. University of Maryland. 2005-12-03 [2006-04-30]. （原始內容存檔於2014-02-27）（英語）.
Knuth, Donald. 6.2.2: Binary Tree Searching. The Art of Computer Programming. 3: "Sorting and Searching" 3rd. Addison-Wesley. 1997: 426–458. ISBN 0-201-89685-0 （英語）.
Long, Sean. Binary Search Tree (PPT). Data Structures and Algorithms Visualization-A PowerPoint Slides Based Approach. SUNY Oneonta（英語：SUNY Oneonta）（英語）.
Parlante, Nick. Binary Trees. CS Education Library. Stanford University. 2001. （原始內容存檔於2022-01-30）（英語）.

外部連結

哈爾沙·蘇利亞納拉亞納（英語：Harsha Suryanarayana）的教學影片：YouTube上的Data structures: Binary Search Tree（英文）
Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. (PDF; 1675 kB) 2004. （英語）

[7] 又稱有序二元樹^[5]（英語：ordered binary tree）或排序二元樹^[6]（英語：sorted binary tree）。

[Cormen2013_zh-1] 1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 ^1.14 ^1.15 ^1.16 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 算法导论. 由殷建平; 徐雲; 王剛; 劉曉光; 蘇明; 鄒恆明; 王宏志翻譯第3版. 北京市: 機械工業出版社. 2013. ISBN 978-7-111-40701-0 （中文（中國大陸））.

[Sedgewick2012_zh-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 Sedgewick, Robert; Wayne, Kevin. 算法. 由謝路雲翻譯第4版. 北京市: 人民郵電出版社. 2012. ISBN 978-7-115-29380-0 （中文（中國大陸））.

[edb-01-3] 香港特別行政區政府教育局課程發展處科技教育組. 中學資訊及通訊科技科常用英漢辭彙 (PDF). 中華人民共和國香港特別行政區教育局: 7. 2023-01 [2025-05-18]. （原始內容存檔 (PDF)於2025-04-09）（中文（香港））.

[胡昭民2022-4] 胡昭民. 圖解資料結構x演算法：運用C語言. 新北市: 博碩文化股份有限公司. 2022. ISBN 978-626-333-119-8 （中文（臺灣））.

[吴海辉2004-5] 吳海輝; 吳建國. 一种基于有序二叉树的高效优化索引树. 微機發展. 2004, (4): 18–21,24. CNKI WJFZ200404006 （中文（中國大陸））.

[王雅琳2012-6] 王雅琳; 肖媛; 雷友誠; 桂衛華. 基于排序二叉树的摘挂列车编组钩计划自动编制方法. 中國鐵道科學. 2012, 33 (3): 116–122. CNKI ZGTK201203020 （中文（中國大陸））.

[Culberson1989-8] 7.0 ^7.1 Culberson, J.; Munro, J. I. Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations. The Computer Journal（英語：The Computer Journal）. 1989-01-01, 32 (1): 68–69 [2025-05-11]. doi:10.1093/comjnl/32.1.68 . （原始內容存檔於2023-08-23）（英語）.

[Culberson1986-9] Culberson, J.; Munro, J. I. Analysis of the standard deletion algorithms in exact fit domain binary search trees. Algorithmica（英語：Algorithmica） (Springer Publishing（英語：Springer Publishing）, University of Waterloo). 1986-07-28, 5 (1–4): 297 [2025-05-11]. S2CID 971813. doi:10.1007/BF01840390. （原始內容存檔於2023-10-23）（英語）.

[Windley1960-10] P. F. Windley. Trees, Forests and Rearranging. The Computer Journal（英語：The Computer Journal）. 1960-01-01, 3 (2): 84. doi:10.1093/comjnl/3.2.84  （英語）.

[Knuth1998-11] 10.0 ^10.1 ^10.2 ^10.3 Knuth, Donald. The Art of Computer Programming 3 2. Addison-Wesley. 1998. ISBN 978-0201896855 （英語）.

[nist-01-12] Black, Paul E. Paul E. Black , 編. red-black tree. Dictionary of Algorithms and Data Structures. 2019-11-12 [2022-05-19]. （原始內容存檔於2009-01-23）（英語）.

[toronto-01-13] Pitassi, Toniann. CSC263: Balanced BSTs, AVL tree (PDF). University of Toronto, Department of Computer Science: 6. 2015 [2022-05-19]. （原始內容存檔 (PDF)於2019-02-14）（英語）.

[cornell-01-14] Myers, Andrew. CS 312 Lecture: AVL Trees. Cornell University, Department of Computer Science. [2022-05-19]. （原始內容存檔於2021-04-27）（英語）.

[Adelson-Velsky1962-15] Adelson-Velsky, Georgy; Landis, Evgenii. An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences（英語：Proceedings of the USSR Academy of Sciences）. 1962, 146: 263–266 （俄語）. English translation （頁面存檔備份，存於網際網路檔案館） by Myron J. Ricci in Soviet Mathematics - Doklady, 3:1259–1263, 1962.

[Thareja2018-16] 15.0 ^15.1 Thareja, Reema. Hashing and Collision. Data Structures Using C 2. Oxford University Press. 2018-10-13 [2025-05-11]. ISBN 9780198099307. （原始內容存檔於2025-05-09）（英語）.

[Cormen2001-17] 16.00 ^16.01 ^16.02 ^16.03 ^16.04 ^16.05 ^16.06 ^16.07 ^16.08 ^16.09 ^16.10 ^16.11 ^16.12 ^16.13 ^16.14 ^16.15 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 2nd. MIT Press. 2001 [2025-05-11]. ISBN 0-262-03293-7. （原始內容存檔於2022-06-24）（英語）.

[Frost1982-18] R. A. Frost; M. M. Peterson. A Short Note on Binary Search Trees. The Computer Journal（英語：The Computer Journal） (Oxford University Press). 1982-02-01, 25 (1): 158. doi:10.1093/comjnl/25.1.158 （英語）.

[Sedgewick2011-19] 18.0 ^18.1 ^18.2 ^18.3 ^18.4 ^18.5 ^18.6 ^18.7 Sedgewick, Robert; Wayne, Kevin. Algorithms 4th. Upper Saddle River, New Jersey: Addison-Wesley Professional. 2011 [2025-05-11]. ISBN 978-0-321-57351-3. （原始內容存檔於2014-07-15）（英語）. Condensed web version ; book version .

[uta-01-20] Junzhou Huang. Design and Analysis of Algorithms (PDF). University of Texas at Arlington: 12. [2021-05-17]. （原始內容存檔 (PDF)於2021-04-13）（英語）.

[lmu-01-21] Ray, Ray. Binary Search Tree. Loyola Marymount University, Department of Computer Science. [2022-05-17]. （原始內容存檔於2024-03-24）（英語）.

[uci-01-22] 21.0 ^21.1 Thornton, Alex. ICS 46: Binary Search Trees. University of California, Irvine. 2021 [2021-10-21]. （原始內容存檔於2021-07-04）（英語）.

[Brass2011-23] 22.0 ^22.1 ^22.2 ^22.3 ^22.4 Brass, Peter. Advanced Data Structure. Cambridge University Press. 2011-01 [2025-05-11]. ISBN 9780511800191. doi:10.1017/CBO9780511800191. （原始內容存檔於2025-05-09）（英語）.

[Blum1978-24] Blum, Norbert; Mehlhorn, Kurt. On the Average Number of Rebalancing Operations in Weight-Balanced Trees (PDF). Theoretical Computer Science. 1978, 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3. （原始內容存檔 (PDF)於2022-10-09）（英語）.

[Lehman1998-25] Lehman, Tobin J.; Carey, Michael J. A Study of Index Structures for Main Memory Database Management Systems. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto. 1986-08. ISBN 0-934613-18-4 （英語）.

[Aragon1989-26] Aragon, Cecilia R.; Seidel, Raimund. 30th Annual Symposium on Foundations of Computer Science. Washington, D.C.: IEEE Computer Society Press: 540–545. 1989. ISBN 0-8186-1982-1. doi:10.1109/SFCS.1989.63531 （英語）.

[Comer1979-27] Comer, Douglas. The Ubiquitous B-Tree. Computing Surveys. 1979-06, 11 (2): 123–137. ISSN 0360-0300. S2CID 101673. doi:10.1145/356770.356776  （英語）.

[Sleator1985-28] Sleator, Daniel D.; Tarjan, Robert E. Self-Adjusting Binary Search Trees (PDF). Journal of the ACM. 1985, 32 (3): 652–686. S2CID 1165848. doi:10.1145/3828.3835 （英語）.

[princeton-01-29] Narayanan, Arvind. COS226: Binary search trees. Princeton University School of Engineering and Applied Science（英語：Princeton University School of Engineering and Applied Science）. 2019 [2021-10-21]. （原始內容存檔於2021-03-22） –透過cs.princeton.edu （英語）.

[emory-01-30] Xiong, Li. A Connection Between Binary Search Trees and Quicksort. Oxford College of Emory University, The Department of Mathematics and Computer Science. [2022-06-04]. （原始內容存檔於2021-02-26）（英語）.

[cornell-02-31] Myers, Andrew. CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps. Cornell University, Department of Computer Science. [2021-10-21]. （原始內容存檔於2021-10-21）（英語）.

[1]

[2]

[3]

[4]

[a]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[5]

[6]

閱論編電腦科學中的樹
二元樹	二元搜尋樹笛卡爾樹 MVP樹 Top tree（英語：Top tree） T樹線索二元樹
自平衡二元搜尋樹	AA樹 AVL樹左傾紅黑樹紅黑樹替罪羊樹伸展樹樹堆加權平衡樹
B樹	B+樹 B*樹 B^x樹 UB樹 2-3樹 2-3-4樹 (a,b)-樹（英語：(a,b)-tree）跳舞樹（英語：Dancing tree） H樹
堆	二元堆積二項堆斐波那契堆左偏樹配對堆斜堆范恩德蟒蛇樹（英語：Van Emde Boas tree）
Trie	字尾樹基數樹三元搜尋樹 X-快速字首樹 Y-快速字首樹 AC自動機
二元空間分割（BSP）樹	四元樹八元樹 k-d樹隱式k-d樹 VP樹
非二元樹	指數樹（英語：Exponential tree）融合樹（英語：Fusion tree） PQ樹（英語：PQ tree） SPQR樹（英語：SPQR tree）
空間資料分割樹	R樹 R*樹 R+樹 X樹 M樹線段樹 (儲存區間) 線段樹 (區間查詢) 可持久化線段樹希爾伯特R樹優先R樹
其他樹	雜湊日曆雜湊樹手指樹（英語：Finger tree）順序統計樹度量樹（英語：Metric tree）覆蓋樹（英語：Cover tree） BK樹二重連鎖樹（英語：Doubly chained tree） iDistance（英語：iDistance） Link-cut tree（英語：Link-cut tree） Log-structured merge-tree（英語：Log-structured merge-tree）樹狀陣列雜湊樹

閱論編資料結構
類型	集合容器
抽象類型	關聯陣列多重關連陣列串列前向串列堆疊佇列雙端佇列優先佇列雙端優先佇列集合多重集併查集可持久化資料結構線段樹
陣列	字串位陣列環形緩衝區動態陣列雜湊表雜湊陣列樹（英語：Hashed array tree）稀疏矩陣
鏈（英語：Linked data structure）	關聯表（英語：Association list）鏈結串列跳躍串列鬆散鏈結串列（英語：Unrolled linked list）互斥或鏈結串列
樹	線段樹 B樹二元樹 AA樹 AVL樹紅黑樹平衡樹伸展樹二元搜尋樹自平衡二元搜尋樹堆二元堆積左偏樹二項堆斐波那契堆 R樹 R*樹 R+樹希爾伯特R樹（英語：Hilbert R-tree）希爾伯特字首樹雜湊樹
圖	有向圖有向無環圖二元決策圖無向圖確定性非迴圈有限自動機（英語：Deterministic acyclic finite state automaton）
資料結構術語列表