二元搜尋樹

「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·希巴德。^[6]^[7]这种数据结构常被归功于康威·柏纳-李（英语：Conway Berners-Lee）及大卫·惠勒（英语：David Wheeler (computer scientist)），他们在1960年将之用于磁带上带标签数据的存储。^[8]希巴德实现二叉搜索树的方法也是最早广为流传的一种。^[6]

若按任意顺序插入节点，树的高度可能接近节点数，导致操作效率急剧下降。研究者们发明了平衡树（即能够自平衡的二叉搜索树），将树的高度限制在 $O(\log n)$ 以内。^[9]^:458–459同时，相关人员也提出了多种高度平衡的二叉搜索树结构，例如AVL树、树堆、红黑树等。^[10]其中，AVL树是首类平衡树，^[11]由格奥尔吉·阿杰尔松-韦利斯基及叶夫根尼·兰迪斯于1962年发明，用于高效组织信息。^[12]^[13]

性质

二叉搜索树为有根的二叉树，其节点顺序为严格全序关系，每个节点都满足：左子树上所有节点的键值都小于或等于该节点，右子树上所有节点的键值都大于或等于该节点。这一结构保证可以在对数时间内定位任意键值。^[14]^:298^[15]^:287^[1]^:161-162除查找外，其也常用于排序，但性能取决于节点的插入和删除顺序——在最坏情况（英语：Best, worst and average case）下，连续操作可能使树退化为类似单链表的结构，这时的查找复杂度与链表相同。^[14]^:299-302^[16]

遍历

二叉搜索树的遍历有三种基本方法：前序、中序、后序。^[15]^:287^[1]^:162

中序遍历：依次遍历左子树、根节点、右子树。遍历结果为键值递增顺序。
前序遍历：依次遍历根节点、左子树、右子树。
后序遍历：依次遍历左子树、右子树、根节点。

以下是递归实现的遍历伪代码：^[15]^: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}}$ ），说明该键不存在。
如果根节点的键值与目标键值相等，返回该节点，表示查找成功。
如果目标键值小于根节点的键值，则继续在左子树中查找；
如果目标键值大于根节点的键值，则继续在右子树中查找。

重复上述步骤，直到找到该键，或者剩余子树为空。若到达空子树仍未找到，说明该键不存在于树中。^[15]^:290-291^[1]^:163

递归搜索

以下伪代码展示递归方式实现的查找过程：^[15]^: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}}$ 。

迭代搜索

递归过程也可展开为循环形式，一般情况下循环版本的效率更高。其伪代码如下：^[15]^: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$ 为树的高度）。^[15]^:290^[1]^:163在最坏情况下，一棵严重不平衡的二叉搜索树可能退化成单链表，这时复杂度会达到 $O(n)$ （ $n$ 为树中节点总数）。但对于高度平衡的二叉搜索树而言，复杂度为 $O(\log n)$ 。^[9]^:458–459^[17]^:403^[2]^:255

后继与前驱

在某些场景下，需要查找给定节点的「后继」或「前驱」。后继节点是大于该节点键值的节点中，键值最小的那一个；前驱节点是小于该节点键值的节点中，键值最大的那一个。以下伪代码给出求节点 ${\text{x}}$ 的后继与前驱方法：^[18]^[19]^[15]^: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

寻找树中键值最大或最小的节点，是寻找后继与前驱过程中的重要环节。其伪代码如下：^[15]^: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

范围查找

利用中序遍历，可以实现范围查找（英语：Range query (computer science)），即查询两个给定值之间的元素数量。其伪代码如下：^[17]^: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是用来收集结果的列表（也可视作队列）。上述过程将所有符合条件的值加入列表中，并跳过不可能含有目标值的子树。

插入

二叉搜索树的数据结构会随插入和删除操作而变化。插入操作须保证二叉搜索树的性质不会遭到破坏，且插入的节点总是作为叶节点加入。^[15]^:294–295^[1]^:165–166以下伪代码给出迭代形式的插入过程：^[15]^: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}}$ 即作为树的根；否则，需根据节点键值大小关系插入对应位置。^[15]^:295^[1]^:166

删除

从树中删除某个节点 ${\text{Z}}$ 时，需分三种情况处理：^[15]^: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)）

以下伪代码实现删除操作：^[15]^: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}}$ 。^[15]^:296-298^[1]^:167-168

若在第3种情况中，仅选用后继或前驱节点中的一种，则并未考虑到树的对称性，可能会导致性能问题。若要避免此问题，可以随机选择使用后继或前驱。^[17]^:410^[2]^:260

平衡树

普通的二叉搜索树中，若不加以平衡，插入或删除操作可能会导致树退化。^[20]若是使用随机键值构建二叉搜索树，那么平均高度仍能维持在对数级别（当节点数 $n$ 足够大时，高度趋近于 $2.99\lg n$ ）；^[17]^:413^[2]^:263但在最坏情况（英语：Best, worst and average case）下，高度会达到节点数 $n$ ，查找性能退化至线性搜索的水平。^[20]要保持二叉搜索树的高效，关键在于通过「自平衡」机制，使树的高度始终维持在 $O(\log n)$ 级别。^[9]^:458–459^[21]^:50^[17]^:414^[2]^:263

高度平衡树

若一棵树的任意节点，其左右子树高度之比都被某个常数所限制，就称其为高度平衡树。这一思想最早在AVL树中使用，后续的红黑树也沿用了类似机制。^[21]^:50-51每次执行插入或删除操作后，需要沿着从根到修改节点的路径，检查并修正各节点的高度，以维持平衡。^[21]^:52

加权平衡树

在加权平衡树中，平衡条件不再以高度衡量，而是以子树的叶节点数量为准。叶节点数量即代表权重，左右子树的权重差最多为常数 $1$ 。^[21]^:61^[22]但单纯依靠差值，难以在插入和删除时用 $O(\log n)$ 的代价维护，因此引入比例因子 $\alpha$ ，要求左右子树的权重各自至少占整棵子树权重的 $\alpha$ 比例，由此形成 $\alpha$ -权重平衡树族。^[21]^:62

其他类型

常见的自平衡二叉搜索树包括：T树（英语：T-tree）^[23]、树堆^[24]、红黑树^[15]^:273^[1]^:174、B树^[25]、2-3树^[9]^:483、伸展树^[26]。

应用

排序

二叉搜索树可用于树排序：先将所有元素插入二叉搜索树中，然后对树做中序遍历，即可得到有序序列。^[27]在快速排序的某些实现中，也可借助二叉搜索树来提高性能。^[28]

优先队列

二叉搜索树也可用来实现优先队列，借助节点的键值来表示优先级。插入操作与普通的二叉搜索树相同，但删除操作取决于优先队列的类型：^[29]

升序优先队列：移除最低优先级元素时，从根节点向左一路遍历即可找到最小键。
降序优先队列：移除最高优先级元素时，从根节点向右一路遍历即可找到最大键。

参见

搜索树
最优二叉搜索树
二叉搜索树的几何性质（英语：Geometry of binary search trees）
三叉搜索树

脚注

注释

^ 又称有序二叉树^[4]（英語：ordered binary tree）或排序二叉树^[5]（英語：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 Sedgewick, Robert; Wayne, Kevin. 算法. 由谢路云翻译第4版. 北京市: 人民邮电出版社. 2012. ISBN 978-7-115-29380-0 （中文（中国大陆））.
^ 胡昭民. 圖解資料結構x演算法：運用C語言. 新北市: 博碩文化股份有限公司. 2022. ISBN 978-626-333-119-8 （中文（臺灣））.
^ 吴海辉; 吴建国. 一种基于有序二叉树的高效优化索引树. 微机发展. 2004, (4): 18–21,24. CNKI WJFZ200404006 （中文（中国大陆））.
^ 王雅琳; 肖媛; 雷友诚; 桂卫华. 基于排序二叉树的摘挂列车编组钩计划自动编制方法. 中国铁道科学. 2012, 33 (3): 116–122. CNKI ZGTK201203020 （中文（中国大陆））.
^ ^6.0 ^6.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  （英语）.
^ ^9.0 ^9.1 ^9.2 ^9.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.
^ ^14.0 ^14.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）（英语）.
^ ^15.00 ^15.01 ^15.02 ^15.03 ^15.04 ^15.05 ^15.06 ^15.07 ^15.08 ^15.09 ^15.10 ^15.11 ^15.12 ^15.13 ^15.14 ^15.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 （英语）.
^ ^17.0 ^17.1 ^17.2 ^17.3 ^17.4 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）（英语）.
^ ^20.0 ^20.1 Thornton, Alex. ICS 46: Binary Search Trees. University of California, Irvine. 2021 [2021-10-21]. （原始内容存档于2021-07-04）（英语）.
^ ^21.0 ^21.1 ^21.2 ^21.3 ^21.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. （英語）
二叉搜索树的可视化页面（簡體中文）（页面存档备份，存于互联网档案馆），支持动画显示二叉搜索树的插入、查找、删除操作。

[6] 又称有序二叉树^[4]（英語：ordered binary tree）或排序二叉树^[5]（英語：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 Sedgewick, Robert; Wayne, Kevin. 算法. 由谢路云翻译第4版. 北京市: 人民邮电出版社. 2012. ISBN 978-7-115-29380-0 （中文（中国大陆））.

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

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

[王雅琳2012-5] 王雅琳; 肖媛; 雷友诚; 桂卫华. 基于排序二叉树的摘挂列车编组钩计划自动编制方法. 中国铁道科学. 2012, 33 (3): 116–122. CNKI ZGTK201203020 （中文（中国大陆））.

[Culberson1989-7] 6.0 ^6.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-8] 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-9] 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-10] 9.0 ^9.1 ^9.2 ^9.3 Knuth, Donald. The Art of Computer Programming 3 2. Addison-Wesley. 1998. ISBN 978-0201896855 （英语）.

[nist-01-11] 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-12] 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-13] Myers, Andrew. CS 312 Lecture: AVL Trees. Cornell University, Department of Computer Science. [2022-05-19]. （原始内容存档于2021-04-27）（英语）.

[Adelson-Velsky1962-14] 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-15] 14.0 ^14.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-16] 15.00 ^15.01 ^15.02 ^15.03 ^15.04 ^15.05 ^15.06 ^15.07 ^15.08 ^15.09 ^15.10 ^15.11 ^15.12 ^15.13 ^15.14 ^15.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-17] 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-18] 17.0 ^17.1 ^17.2 ^17.3 ^17.4 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-19] Junzhou Huang. Design and Analysis of Algorithms (PDF). University of Texas at Arlington: 12. [2021-05-17]. （原始内容存档 (PDF)于2021-04-13）（英语）.

[lmu-01-20] Ray, Ray. Binary Search Tree. Loyola Marymount University, Department of Computer Science. [2022-05-17]. （原始内容存档于2024-03-24）（英语）.

[uci-01-21] 20.0 ^20.1 Thornton, Alex. ICS 46: Binary Search Trees. University of California, Irvine. 2021 [2021-10-21]. （原始内容存档于2021-07-04）（英语）.

[Brass2011-22] 21.0 ^21.1 ^21.2 ^21.3 ^21.4 Brass, Peter. Advanced Data Structure. Cambridge University Press. 2011-01 [2025-05-11]. ISBN 9780511800191. doi:10.1017/CBO9780511800191. （原始内容存档于2025-05-09）（英语）.

[Blum1978-23] 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-24] 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-25] 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-26] 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-27] 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-28] 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-29] 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-30] 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]

[a]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[4]

[5]

查论编计算机科学中的树
二叉树	二元搜尋樹笛卡尔树 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）
数据结构术语列表