二叉搜索树（，简称BST）是一种有根二叉树数据结构。它要求每个内部节点的键值都大于其左子树中所有节点的键值，且都小于其右子树中所有节点的键值。该树各项操作时间复杂度均与树的高度成线性关系。

二叉搜索树每次比较都能排除大约一半的剩余节点，故能以对数时间查找、插入、删除数据。但其性能依赖于节点的插入顺序，插入随机键值时仍能维持对数级别，但在下会退化成链表。为保证效率，研究者发明了多种平衡树，能将最坏查找复杂度维持在O(\log n)。

二叉搜索树最早由多位研究者独立提出，1960年被用来解决带标签数据的存储问题。其还可用来实现及优先队列。

历史
二叉搜索树最早由多位研究者独立提出，包括P.F.温德利、安德鲁·唐纳德·布思、安德鲁·科林、托马斯·N·希巴德。这种数据结构常被归功于及，他们在1960年将之用于磁带上带标签数据的存储。希巴德实现二叉搜索树的方法也是最早广为流传的一种。

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

性质
二叉搜索树为有的二叉树，其节点顺序为严格全序关系，每个节点都满足：左子树上所有节点的键值都小于该节点，右子树上所有节点的键值都大于该节点。这一结构保证可以在对数时间内定位任意键值。除查找外，其也常用于排序，但性能取决于节点的插入和删除顺序——在下，连续操作可能使树退化为类似单链表的结构，这时的查找复杂度与链表相同。

遍历
二叉搜索树的遍历有三种基本方法：前序、中序、后序。

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

以下是递归实现的遍历伪代码：

操作
搜索
在二叉搜索树中查找某个特定的键，可以使用递归或迭代方式实现。

查找过程从树的开始：

• 如果根节点为空（\text{nil}），说明该键不存在。
• 如果根节点的键值与目标键值相等，返回该节点，表示查找成功。
• 如果目标键值小于根节点的键值，则继续在左子树中查找；
• 如果目标键值大于根节点的键值，则继续在右子树中查找。

重复上述步骤，直到找到该键，或者剩余子树为空。若到达空子树仍未找到，说明该键不存在于树中。

递归搜索
以下伪代码展示递归方式实现的查找过程：

递归会一直进行，直到遇到\text{nil}或是找到目标键\text{key}。

迭代搜索
递归过程也可展开为循环形式，一般情况下循环版本的效率更高。其伪代码如下：

由于查找可能会一直到叶节点，因此时间复杂度为树的高度O(h)（h为树的高度）。在最坏情况下，一棵严重不平衡的二叉搜索树可能退化成单链表，这时复杂度会达到O(n)（n为树中节点总数）。但对于高度平衡的二叉搜索树而言，复杂度为O(\log n)。

后继与前驱
在某些场景下，需要查找给定节点的「后继」或「前驱」。后继节点是大于该节点键值的节点中，键值最小的那一个；前驱节点是小于该节点键值的节点中，键值最大的那一个。以下伪代码给出求节点\text{x}的后继与前驱方法：

寻找树中键值最大或最小的节点，是寻找后继与前驱过程中的重要环节。其伪代码如下：

选择与排名
若在节点中维护以之为根节点的子树的节点总数，则可实现选择与排名操作。选择操作用于在树中直接定位排名为k的节点，即第k小的键。排名操作则与之相对，给定指定键后，其会返回小于该键的节点数。这两种操作的伪代码如下：

其中size表示子树规模信息，即子树中节点数量。

范围查找
利用中序遍历，可以实现，即查询两个给定值之间的元素数量。其伪代码如下：

其中list是用来收集结果的列表（也可视作队列）。上述过程将所有符合条件的值加入列表中，并跳过不可能含有目标值的子树。

插入
二叉搜索树的数据结构会随插入和删除操作而变化。插入操作须保证二叉搜索树的性质不会遭到破坏，且插入的节点总是作为叶节点加入。以下伪代码给出迭代形式的插入过程：

过程使用变量\text{y}作为遍历节点\text{x}的父节点（追踪指针）。初始时如果\text{y}为\text{nil}，说明树为空，新节点\text{z}即作为树的根；否则，需根据节点键值大小关系插入对应位置。

删除
从树中删除某个节点\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)）

以下伪代码实现删除操作：

\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，查找性能退化至线性搜索的-{zh:水平;zh-hans:水平;zh-hant:水平;zh-tw:水準;}-。要保持二叉搜索树的高效，关键在于通过「自平衡」机制，使树的高度始终维持在O(\log n)级别。

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

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

其他类型
常见的自平衡二叉搜索树包括：、树堆、红黑树、B树、2-3树、伸展树。

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

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

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

参见

• 搜索树
• 最优二叉搜索树

*

• 三叉搜索树

脚注
注释
来源
延伸阅读
*
*
*
*
*
*

外部链接

• 的教学视频：
• Ben Pfaff: [http://ftp.gnu.org/gnu/avl/avl-2.0.3.pdf.gz An Introduction to Binary Search Trees and Balanced Trees]. (PDF; 1675 kB) 2004.