二叉搜索树

概述

二叉搜索树（Binary Search Tree, BST） 是一种组织有序数据的二叉树数据结构，支持动态集合的搜索、插入、删除、求最小值、求最大值、求前驱和求后继等操作。BST 的核心优势在于：借助二叉搜索树性质，所有基本操作都能在 $O(h)$ 时间内完成，其中 $h$ 为树高。

定义

二叉搜索树

二叉搜索树是一棵二叉树，其中每个节点包含以下属性：

• key：关键字的值
• left：左子节点指针
• right：右子节点指针
• p：父节点指针（CLRS 第4版使用此属性）

此外，整棵树维护一个属性 root，指向根节点。

二叉搜索树必须满足二叉搜索树性质（BST Property）： 设 $x$ 为树中的任意节点，则：

• 若 $y$ 是 $x$ 左子树中的任意节点，则 $y.key\le x.key$
• 若 $y$ 是 $x$ 右子树中的任意节点，则 $y.key\ge x.key$

直观理解

可以将 BST 想象为一棵”有序树”：站在任意节点上，往左看（左子树）的所有值都不大于当前节点，往右看（右子树）的所有值都不小于当前节点。这一性质递归地作用于整棵树。

例如，以下是一棵合法的 BST：

        6
       / \
      2   8
     / \   \
    1   4   9
       / \
      3   5

• 节点 6 的左子树中所有 key（1, 2, 3, 4, 5）都 $\le 6$
• 节点 6 的右子树中所有 key（8, 9）都 $\ge 6$
• 此性质对每个节点都成立

核心性质

定理12.1：中序遍历输出有序序列

定理12.1

如果对一棵二叉搜索树进行中序遍历（inorder tree walk），则输出的 key 序列是单调递增的。

证明（CLRS 原版）：

对 BST 中任意节点 $x$，使用数学归纳法证明：中序遍历以 $x$ 为根的子树输出的 key 序列是递增的。

• 归纳基础：若 $x$ 的子树为空（$x.left=NIL$ 且 $x.right=NIL$），则中序遍历只输出 $x.key$，单个元素的序列自然是递增的。

• 归纳假设：假设中序遍历 $x.left$ 和 $x.right$ 产生的子序列都是递增的。

• 归纳步骤：中序遍历以 $x$ 为根的子树按以下顺序输出：

  1. 中序遍历 $x.left$ 产生的序列 $L$
  2. $x.key$
  3. 中序遍历 $x.right$ 产生的序列 $R$

  由 BST 性质：

  • $L$ 中所有 key $\le x.key$（因为 $L$ 的节点都在 $x$ 的左子树中）
  • $R$ 中所有 key $\ge x.key$（因为 $R$ 的节点都在 $x$ 的右子树中）

  由归纳假设，$L$ 内部递增、$R$ 内部递增。因此拼接后的完整序列 $L\cdot [x.key]\cdot R$ 也是递增的。$■$

操作的时间复杂度

BST 上所有基本操作（中序遍历、TREE-SEARCH、TREE-INSERT、求最小值/最大值、求前驱/后继、TRANSPLANT 及删除）的运行时间都为 $O(h)$，其中 $h$ 是树高。

• 最好情况：树是完全平衡的，$h=O(\log n)$，所有操作 $O(\log n)$
• 最坏情况：树退化为链（所有节点只有右子节点或只有左子节点），$h=n$，所有操作退化为 $O(n)$

与散列表的对比

BST 与 散列表 都支持动态集合操作，但 BST 天然维护元素的有序性，支持求最小值、最大值、前驱、后继等顺序统计操作，而散列表不支持。

章节扩展

操作	对应概念页	时间复杂度
中序遍历	中序遍历	$\Theta (n)$
查询	TREE-SEARCH	$O(h)$
插入	TREE-INSERT	$O(h)$
子树替换（删除子程序）	TRANSPLANT	$O(1)$
删除	12.3 插入和删除	$O(h)$
多路推广为B树	B树	$O({\log }_{t}n)$

参见

• 中序遍历 — BST 的核心遍历方式
• TREE-SEARCH — 在 BST 中查找关键字
• TREE-INSERT — 向 BST 中插入新节点
• TRANSPLANT — 删除操作的核心子程序
• 散列表 — 另一种动态集合实现，不支持有序操作
• B树 — BST向多路搜索树的推广
• 最小度 — B树的核心参数