二叉搜索树（BST）

数据结构与算法专题 · 有序键值对的树形组织方式

专题：数据结构与算法系统学习

关键词：数据结构, 算法, 二叉搜索树, BST, 搜索, 插入, 删除, 中序遍历, 前驱, 后继

一、BST的定义与性质

二叉搜索树（Binary Search Tree，简称BST），也称二叉排序树或二叉查找树，是一种特殊的二叉树结构。在BST中，任意节点的左子树中的所有节点值均小于该节点的值，右子树中的所有节点值均大于该节点的值。这一"左小右大"的递归定义赋予了BST极其重要的有序性质：对BST进行中序遍历（左-根-右）将得到一个严格递增的序列。

BST的核心性质可以归纳为以下四点：第一，若左子树不为空，则左子树上所有节点的值均小于根节点的值；第二，若右子树不为空，则右子树上所有节点的值均大于根节点的值；第三，左、右子树本身也分别是二叉搜索树；第四，BST中不允许存在重复的节点值（在允许重复的实现中，通常统一放在右子树或左子树中）。

BST的直观理解：想象一本按字母顺序排列的电话簿。你想查找"Smith"，你不会从第一页翻到最后一页，而是直接翻到S所在的大致位置。BST的搜索逻辑与此类似——每次比较都能排除大约一半的剩余数据，这就是二分查找思想在树形结构中的体现。

# BST节点的定义（Python） class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None
# 创建一个简单的BST示例 # 8 # / \ # 3 10 # / \ \ # 1 6 14 # / \ / # 4 7 13 root = TreeNode(8) root.left = TreeNode(3) root.right = TreeNode(10) root.left.left = TreeNode(1) root.left.right = TreeNode(6) root.right.right = TreeNode(14) root.left.right.left = TreeNode(4) root.left.right.right = TreeNode(7) root.right.right.left = TreeNode(13)

注意观察上述BST的形态：根节点为8，左子树中所有节点（1、3、4、6、7）都小于8，右子树中所有节点（10、13、14）都大于8。对整棵树进行中序遍历将得到序列 [1, 3, 4, 6, 7, 8, 10, 13, 14]，恰好是递增有序的。这正是BST最优雅的性质——中序有序性。

二、BST的基本操作——查找（Search）

查找是BST最基础、最核心的操作。给定一个目标值，从根节点开始，根据"左小右大"原则逐层向下比较：若目标值等于当前节点值，查找成功；若目标值小于当前节点值，进入左子树继续查找；若目标值大于当前节点值，进入右子树继续查找。若抵达空节点仍未找到，则说明目标值不存在于树中。

递归实现

def search_bst_recursive(root, target): # 递归终止条件：空节点或找到目标 if root is None or root.val == target: return root # 目标值小于当前节点，进入左子树 if target < root.val: return search_bst_recursive(root.left, target) # 目标值大于当前节点，进入右子树 return search_bst_recursive(root.right, target)

迭代实现

def search_bst_iterative(root, target): cur = root while cur is not None and cur.val != target: if target < cur.val: cur = cur.left else: cur = cur.right return cur

递归 vs 迭代：递归实现简洁直观，但在树深度较大时可能栈溢出；迭代实现使用循环而非函数调用栈，空间复杂度为O(1)，是更优的工程实践。两种实现的时间复杂度相同，均为O(h)，其中h为树的高度。

以查找值为6的节点为例，在上述BST中，搜索路径为：根节点8（6<8，向左）→ 节点3（6>3，向右）→ 节点6（找到目标）。只需要3次比较即可找到，若使用线性结构则需要至多9次比较。BST的优势在这里体现得非常明显。

三、BST的基本操作——插入（Insert）

插入操作的核心思路与查找类似：先通过搜索找到目标值应该存放的位置，然后将新节点连接到合适的位置。具体而言，从根节点开始，不断与当前节点比较：若待插入值小于当前节点值，向左子树移动；若大于，向右子树移动。当遇到空节点时，该位置就是新节点的插入位置。这一过程保证了插入后BST的性质依然成立。

递归实现

def insert_bst_recursive(root, val): # 找到空位，创建新节点 if root is None: return TreeNode(val) # 递归地在左子树或右子树中插入 if val < root.val: root.left = insert_bst_recursive(root.left, val) elif val > root.val: root.right = insert_bst_recursive(root.right, val) # 若val已存在，则不做任何操作（BST不包含重复值） return root

迭代实现

def insert_bst_iterative(root, val): new_node = TreeNode(val) # 空树情况 if root is None: return new_node cur = root while True: if val < cur.val: if cur.left is None: cur.left = new_node break cur = cur.left elif val > cur.val: if cur.right is None: cur.right = new_node break cur = cur.right else: # 值已存在，不插入 break return root

插入的注意点：标准的BST不允许重复值的插入。在需要支持重复值的场景中，常见的策略有两种：一是将重复值统一插入到右子树（或左子树），二是在节点中增加一个计数器（count字段）来记录相同值的出现次数。第二种方式更高效，因为避免了在树中插入多余的节点。

四、BST的基本操作——删除（Delete）

删除操作是BST中最复杂、最需要谨慎处理的操作。与查找和插入不同，删除一个节点后，需要以恰当的方式调整树的结构，使整棵树依然满足BST的性质。根据待删除节点的子节点数量，删除操作分为三种情况。

情况一：删除叶节点（度为0）

最简单的情况。待删除节点没有任何子节点，直接将其父节点的对应指针置为None即可。例如删除上图中的节点4（值为4的叶节点），只需将节点6的左指针设为None。

情况二：删除只有一个子节点的节点（度为1）

待删除节点只有一个左子节点或一个右子节点。此时用该子节点替代待删除节点的位置即可。例如删除节点14（只有左子节点13），将节点10的右指针直接指向节点13即可。这相当于"跳过"了待删除节点，将其子树整体上移。

情况三：删除有两个子节点的节点（度为2）

最复杂的情况。待删除节点同时拥有左、右两个子节点。此时不能简单地用任意一个子节点替代，因为替代后另一棵子树将无处安放。标准的解法是：找到待删除节点的中序后继（或中序前驱），用后继节点的值覆盖待删除节点的值，然后转而删除那个后继节点。中序后继是右子树中最小的节点，它最多只有一个右子节点（即度为0或1），因此删除后继节点退化为情况一或情况二。

def delete_node(root, key): # 基础情况：空树 if root is None: return None # 1. 查找待删除节点 if key < root.val: root.left = delete_node(root.left, key) elif key > root.val: root.right = delete_node(root.right, key) else: # 找到待删除节点，处理三种情况 # 情况1: 叶节点或只有一个子节点 if root.left is None: return root.right if root.right is None: return root.left # 情况2: 有两个子节点 # 找到中序后继（右子树的最小节点） successor = _find_min(root.right) # 用后继节点的值覆盖当前节点 root.val = successor.val # 删除后继节点（它一定在右子树中） root.right = delete_node(root.right, successor.val) return root def _find_min(root): # 一直向左走，找到最小值 cur = root while cur and cur.left: cur = cur.left return cur

删除操作的核心理念：对于度为2的节点，不要试图物理删除，而是采用"值替换"的策略。将删除问题从"删除一个复杂节点"转化为"删除一个简单节点（叶节点或单子节点）"。这种化归的思想在算法设计中非常重要。

举个例子。在上面的BST中删除节点3（度为2，有两个子节点）：第一步，找到节点3的中序后继——节点4（右子树6的左子节点4）；第二步，将节点3的值改为4；第三步，在右子树中删除原来的节点4（这是一个叶节点，属于情况一）。最终树被调整为：根8保持不变，节点3的位置变成了值4，原来值为4的叶节点被删除。

五、BST的遍历

BST的遍历方式与普通二叉树完全相同，包括前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）和层序遍历。但BST有一个极其重要的特性：中序遍历BST得到的是有序序列。这是BST区别于其他二叉树的最关键特征，也是BST之所以被广泛用于实现有序集合的核心原因。

# BST的中序遍历（递归）—— 输出递增序列 def inorder_traversal(root): result = [] def _inorder(node): if node is None: return _inorder(node.left) result.append(node.val) _inorder(node.right) _inorder(root) return result
# BST的中序遍历（迭代）—— 使用栈模拟递归 def inorder_iterative(root): result, stack = [], [] cur = root while cur or stack: # 一路向左，将路径上的节点压栈 while cur: stack.append(cur) cur = cur.left # 弹出栈顶，访问节点，转向右子树 cur = stack.pop() result.append(cur.val) cur = cur.right return result

迭代版本的中序遍历是一个很重要的算法模式。它的核心思想是：不依赖递归调用栈，而是手动维护一个显式栈。外层循环控制整体流程，内层循环负责处理"一直向左走到尽头"的逻辑。每弹出一个节点就访问它，然后立即转向右子树。这一模式在后续学习线索二叉树、Morris遍历时还会用到。

遍历方式顺序BST中的特殊性
前序遍历根 → 左 → 右可用于序列化BST（结合中序可重建BST）
中序遍历左 → 根 → 右输出严格递增序列（BST最重要的性质）
后序遍历左 → 右 → 根可用于自底向上处理（如计算子树高度）
层序遍历逐层从左到右可用于判断BST的完全性、广度优先搜索

六、BST的前驱与后继

在BST中，一个节点的前驱（predecessor）是指值小于该节点的所有节点中最大的一个（即中序遍历序列中位于该节点前一位的节点）。后继（successor）是指值大于该节点的所有节点中最小的一个（即中序遍历序列中位于该节点后一位的节点）。前驱和后继的查找在BST删除操作和区间查询中非常关键。

后继的查找

查找节点p的后继有两种情况：如果p有右子树，则后继是右子树中最左侧的节点（即右子树的最小值）。如果p没有右子树，则需要从根节点开始查找，记录在搜索路径上最后一个"向右转"的节点（即最后一个值大于p的祖先节点）。前驱的查找是对称的。

def get_successor(root, p): """ 查找节点p的中序后继 情况1: p有右子树 → 右子树中的最小值 情况2: p无右子树 → 从根到p的路径上，最后一个"向左转"的祖先节点 """ if p.right: # 情况1：右子树的最小值 cur = p.right while cur.left: cur = cur.left return cur # 情况2：从根开始查找 successor = None cur = root while cur and cur != p: if p.val < cur.val: # 当前节点值大于p，是候选后继 successor = cur cur = cur.left else: cur = cur.right return successor
def get_predecessor(root, p): """ 查找节点p的中序前驱 情况1: p有左子树 → 左子树中的最大值 情况2: p无左子树 → 从根到p的路径上，最后一个"向右转"的祖先节点 """ if p.left: cur = p.left while cur.right: cur = cur.right return cur predecessor = None cur = root while cur and cur != p: if p.val > cur.val: predecessor = cur cur = cur.right else: cur = cur.left return predecessor

前驱/后继与删除的关系：在BST删除操作的第三种情况中，我们使用了后继节点来替代被删除节点。实际上也可以使用前驱节点来替代——两种策略都是正确的，选择哪一个取决于实现偏好。用后继替换的本质是：将当前节点变为它右子树的最小值，再删除那个最小值。

七、BST的时间复杂度分析

BST的查找、插入和删除操作的时间复杂度都等于树的高度h。因为每次比较都沿着一条从根到叶的路径走，不会访问其他路径上的节点。因此，分析BST的时间复杂度本质上就是分析树的高度。

平均情况：O(log n)

当BST是平衡的，即对于任意节点，其左右子树的高度大致相等时，树的高度约为log₂n。这是因为每一层可以容纳的节点数量翻倍（第一层1个，第二层2个，第三层4个...），因此n个节点构成的完全二叉树的高度约为log₂(n+1)。在平均情况下，随机插入足够多的节点后，BST的期望高度为O(log n)，因此查找/插入/删除的平均时间复杂度为O(log n)。

最坏情况：O(n)

当插入的序列是递增的（或递减的），BST会退化为一个"链表"状的结构。例如依次插入1、2、3、4、5、6，每个节点都只有右子节点，树的高度等于节点数量n。此时查找元素6需要遍历所有节点，时间复杂度退化为O(n)。这与线性表的顺序查找没有区别。

操作平均时间复杂度最坏时间复杂度
查找（Search）O(log n)O(n)
插入（Insert）O(log n)O(n)
删除（Delete）O(log n)O(n)
中序遍历O(n)O(n)
查找前驱/后继O(log n)O(n)

BST的优势（平衡时）

  • 查找效率高：O(log n)
  • 支持有序遍历：O(n)输出有序序列
  • 支持范围查询：查找[min, max]区间的元素
  • 动态结构：插入和删除比有序数组更高效

BST的劣势（极端情况下）

  • 可能退化为链表：O(n)
  • 没有自平衡机制
  • 需要额外的指针空间
  • 对插入顺序敏感

八、BST的局限性

BST最大的问题在于其性能高度依赖输入数据的顺序。当输入数据有序或接近有序时，BST会严重退化。这个问题在实际工程中非常致命——谁能保证用户插入的数据是随机的呢？为了解决这个问题，计算机科学家提出了一系列的自平衡二叉搜索树（Self-balancing BST），它们在插入和删除后通过旋转操作自动调整树的结构，确保树的高度始终维持在O(log n)。

从BST到自平衡树的演进路线：

  • AVL树（1962年）： 严格平衡，任意节点左右子树高度差不超过1。查找效率最高，但插入/删除的旋转操作较多。
  • 红黑树（1972年）： 近似平衡，通过颜色约束保证最长路径不超过最短路径的2倍。插入/删除效率高，是工业界的主流选择。
  • B树/B+树（1972年）： 多路平衡搜索树，每个节点可以有多个子节点和多个键值。专门为磁盘I/O优化，是数据库索引的标准数据结构。
  • Treap（1989年）： 树+堆的结合体，通过随机优先级保持平衡。实现简单，期望深度为O(log n)。
  • Splay树（1985年）： 基于"最近访问的节点很可能再次被访问"的局部性原理，每次操作后将节点旋转到根。

在这些自平衡树中，红黑树的应用最为广泛。C++ STL中的std::map和std::set、Java中的TreeMap和TreeSet、Linux内核中的完全公平调度器（CFS）都使用红黑树作为底层数据结构。红黑树的"近似平衡"策略在查找和修改之间取得了良好的平衡，是工程实践中的最优解之一。

九、BST的应用场景

尽管BST存在退化风险，但在理解了其局限性和适用边界后，BST以及它的变种（自平衡BST）在计算机科学中有着极其广泛的应用。

1. 实现有序集合和有序字典

这是BST最经典的应用。基于BST的有序集合（如C++的std::set）可以在O(log n)时间内完成插入、删除和查找操作，同时支持在O(1)时间内获取最小/最大值，以及在O(log n)时间内查找前驱和后继。这些操作是哈希表无法高效支持的。例如，在C++中std::set是基于红黑树实现的，而std::unordered_set是基于哈希表实现的——两者分别擅长不同的场景。

# Python中的有序集合（由第三方库提供） # Python标准库没有内置的基于BST的有序集合 # 但可以用bisect模块在有序列表上模拟 import bisect # 或使用sortedcontainers第三方库 # from sortedcontainers import SortedList # sl = SortedList([3, 1, 4, 1, 5, 9, 2, 6])

2. 区间查询与范围统计

BST的中序有序性使得区间查询非常简单。如果要查找在[a, b]范围内的所有元素，只需先找到a的后继（或a本身），然后中序遍历到第一个大于b的元素为止。在扩展的BST（如线段树、树状数组）中，还可以高效地统计区间内的元素个数和求和。

3. 表达式树与语法分析

在编译原理中，算术表达式可以表示为二叉树（表达式树），其中内部节点是运算符，叶节点是操作数。虽然表达式树不一定是BST（因为它不满足左小右大的性质），但基于BST的遍历技巧（前序得到前缀表达式、中序得到中缀表达式、后序得到后缀表达式）是表达式求值和语法分析的基础。

4. Huffman编码树

在数据压缩领域的Huffman算法中，每一步都从优先队列中取出两个频率最小的节点合并。这个优先队列可以用最小堆实现，而最小堆本质上是一棵完全二叉搜索树变体。虽然Huffman树本身不是BST，但BST中"层层比较、按序组织"的思想是Huffman编码的理论基础之一。

5. 二叉搜索树在计算机图形学中的应用

在3D渲染的场景管理系统中，BSP树（二叉空间分割树）借鉴了BST的空间划分思想，将场景递归地分割为两个半空间，加速了碰撞检测和可见性判断等操作。KD树则是BST在多维空间的推广，用于最近邻搜索和点云处理。

# 验证一棵二叉树是否是BST（经典面试题） def is_valid_bst(root): # 使用中序遍历：BST的中序遍历结果应该是严格递增的 prev = [None] # 用列表包裹以实现引用传递 def _inorder(node): if node is None: return True # 检查左子树 if not _inorder(node.left): return False # 检查当前节点是否大于前一个值 if prev[0] is not None and node.val <= prev[0]: return False prev[0] = node.val # 检查右子树 return _inorder(node.right) return _inorder(root)

十、完整代码实现：BST类

下面给出一个完整的BST类实现，包含增删查改、遍历、前驱后继查找等核心功能。这是面试和工程中最常用的实现方式。

class BST: class _Node: def __init__(self, val): self.val = val self.left = None self.right = None def __init__(self): self._root = None self._size = 0 def search(self, target): """查找目标值，返回节点或None""" cur = self._root while cur and cur.val != target: if target < cur.val: cur = cur.left else: cur = cur.right return cur def insert(self, val): """插入值（迭代版）""" if self._root is None: self._root = self._Node(val) self._size += 1 return cur = self._root while True: if val < cur.val: if cur.left is None: cur.left = self._Node(val) self._size += 1 break cur = cur.left elif val > cur.val: if cur.right is None: cur.right = self._Node(val) self._size += 1 break cur = cur.right else: break # 值已存在，不插入 def delete(self, key): """删除值""" self._root = self._delete(self._root, key) def _delete(self, node, key): if node is None: return None if key < node.val: node.left = self._delete(node.left, key) elif key > node.val: node.right = self._delete(node.right, key) else: if node.left is None: self._size -= 1 return node.right if node.right is None: self._size -= 1 return node.left # 有两个子节点：用后继替换 succ = self._find_min(node.right) node.val = succ.val node.right = self._delete(node.right, succ.val) return node def _find_min(self, node): while node.left: node = node.left return node def inorder(self): """中序遍历，返回有序列表""" result, stack = [], [] cur = self._root while cur or stack: while cur: stack.append(cur) cur = cur.left cur = stack.pop() result.append(cur.val) cur = cur.right return result def successor(self, val): """查找给定值的后继，返回节点值或None""" node = self._search_node(val) if node is None: return None if node.right: cur = node.right while cur.left: cur = cur.left return cur.val cur = self._root succ = None while cur and cur != node: if val < cur.val: succ = cur cur = cur.left else: cur = cur.right return succ.val if succ else None def _search_node(self, val): cur = self._root while cur and cur.val != val: if val < cur.val: cur = cur.left else: cur = cur.right return cur def __len__(self): return self._size def __contains__(self, val): return self._search_node(val) is not None

十一、核心要点总结

  • BST的核心性质： 左小右大，中序有序。这是BST定义和所有操作的基础。
  • 查找操作： 每次都排除一半的搜索空间，平均时间复杂度O(log n)，最坏O(n)。递归和迭代两种实现都可，迭代更省空间。
  • 插入操作： 先找到插入位置再连接新节点，本质就是一次失败的查找。递归实现需注意返回新子树根节点。
  • 删除操作： 三种情况（叶节点、单子节点、双子节点）。双子节点采用"值替换"策略，将问题转化为删除前驱或后继。
  • 前驱与后继： 基于中序序列的定义。有右子树则找右子树最小值，无右子树则找祖先中的最后一个候选。
  • 时间复杂度： 所有基本操作的时间复杂度均为O(h) = O(log n)平均 / O(n)最坏。关键在于树是否平衡。
  • 局限性： BST对输入顺序敏感，有序输入会导致退化。自平衡BST（AVL树、红黑树、B树等）通过旋转机制解决了这一问题。
  • 应用广泛： 有序集合/字典（C++ std::set/map）、数据库索引（B+树）、文件系统、编译器、图形学等领域均有BST或其变种的身影。
  • 学习意义： BST是理解更复杂树结构（AVL树、红黑树、B树、线段树）的基石，也是面试中最高频的数据结构考点之一。
  • 验证技巧： 用中序遍历检查BST的有效性是最简便的方法——只需检查遍历结果是否严格递增即可。