TREE-SEARCH

概述

TREE-SEARCH 是在二叉搜索树中查找给定关键字的过程。利用 BST 性质，搜索过程从根节点出发，每一步根据当前节点的 key 与目标 key 的比较结果决定走向左子树还是右子树，运行时间为 $O(h)$，其中 $h$ 为树高。CLRS 同时给出了递归版本和迭代版本两种实现。

定义

TREE-SEARCH

给定一棵二叉搜索树的根节点 $x$ 和一个关键字 $k$，TREE-SEARCH(x, k) 返回一个指针，指向 key 为 $k$ 的节点；若 $k$ 不在树中，则返回 NIL。

递归版本

TREE-SEARCH(x, k)
1  if x == NIL or k == x.key
2      return x
3  if k < x.key
4      return TREE-SEARCH(x.left, k)
5  else return TREE-SEARCH(x.right, k)

执行逻辑：

1. 终止条件：当前节点为空（x == NIL，说明 $k$ 不在树中）或当前节点的 key 恰好等于 $k$（找到了目标）
2. 递归左子树：若 $k<x.key$，由 BST 性质，$k$ 只可能出现在左子树中
3. 递归右子树：若 $k>x.key$，由 BST 性质，$k$ 只可能出现在右子树中

迭代版本

ITERATIVE-TREE-SEARCH(x, k)
1  while x ≠ NIL and k ≠ x.key
2      if k < x.key
3          x = x.left
4      else x = x.right
5  return x

执行逻辑：与递归版本完全等价，但使用 while 循环代替递归调用。每次迭代将指针 $x$ 移动到其左子节点或右子节点，直到找到目标或到达 NIL。

逐步执行示例

在以下 BST 中搜索 $k=4$：

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

步骤	当前节点 x	k 与 x.key 比较	下一步
1	6	$4<6$	x = x.left = 2
2	2	$4>2$	x = x.right = 4
3	4	$4=4$	返回节点 4

搜索 $k=7$：

步骤	当前节点 x	k 与 x.key 比较	下一步
1	6	$7>6$	x = x.right = 8
2	8	$7<8$	x = x.left = NIL
3	NIL	—	返回 NIL（未找到）

核心性质

循环不变式（迭代版本）

循环不变式

对于 ITERATIVE-TREE-SEARCH(x, k) 的 while 循环：

不变式：在每次循环迭代开始时，若 $k$ 存在于树中，则 $k$ 所在的节点是以 $x$ 为根的子树中的某个节点。

初始化：第一次迭代前，$x$ 是整棵树的根，若 $k$ 在树中，则 $k$ 必然在以根为根的子树中。不变式成立。

保持：每次迭代中，根据 BST 性质：

• 若 $k<x.key$，则 $k$ 只可能在左子树中，令 $x=x.left$，不变式保持
• 若 $k>x.key$，则 $k$ 只可能在右子树中，令 $x=x.right$，不变式保持

终止：循环终止时，要么 $x.key=k$（找到目标），要么 $x=NIL$（$k$ 不在树中）。两种情况下返回值都正确。

时间复杂度

时间复杂度： $O(h)$

每次迭代（或递归调用）将搜索范围从当前子树缩小到其左子树或右子树，即树高减少 1。因此最多经过 $h$ 次比较即可到达目标或确定不存在，时间复杂度为 $O(h)$。

• 平衡 BST：$O(\log n)$
• 退化为链：$O(n)$

递归版本 vs 迭代版本

对比项	递归版本	迭代版本
代码简洁性	更简洁直观	稍长
空间开销	$O(h)$ 栈空间	$O(1)$
实际性能	有函数调用开销	更高效
CLRS 推荐	用于说明概念	实际使用推荐

实践建议

在大多数编程语言中，迭代版本更受推荐，因为它避免了递归调用的栈开销，且在 $h$ 较大时不会出现栈溢出的风险。

章节扩展

TREE-SEARCH 是 BST 查询操作的基础，CLRS 第12.2节还包含以下相关操作：

• TREE-MINIMUM / TREE-MAXIMUM：沿左/右边界一直向下走，$O(h)$
• TREE-SUCCESSOR / TREE-PREDECESSOR：求中序遍历的后继/前驱，$O(h)$

这些操作都依赖 BST 性质，时间复杂度同为 $O(h)$。

参见

• 二叉搜索树 — BST 的定义与性质
• 中序遍历 — BST 的有序遍历
• TREE-INSERT — 向 BST 插入新节点
• TRANSPLANT — 删除操作的核心子程序
• 散列表 — 平均 $O(1)$ 的查找，但不支持有序操作