BST：不是“左孩子小、右孩子大”就够了

最近审阅：2026-10-09 · 先读：DFS / BFS

根是 8，右孩子是 10，而 10 的左孩子是 6。每对父子看起来都对：10 大于 8，6 小于 10。但 6 在 8 的右子树里，它必须大于 8。这棵树不是二叉搜索树（binary search tree, BST）。

BST 的约束作用于整棵子树，不是只检查相邻的两个节点。本篇采用严格顺序，不允许重复 key；实际容器也可以把同一个 key 的次数存在节点里。

搜索为什么可以舍掉半边

在节点 8 找 6：6 小于 8，右子树全部大于 8，不可能藏着 6，继续找左子树即可。省掉的是一棵子树，不保证刚好省掉一半节点。

设树高为 $h$，搜索和普通插入花 $O(h)$。平衡时 $h=O(\log n)$，按顺序插入却可能形成长链，变成 $O(n)$。普通 BST 不会自动平衡；AVL、红黑树通过额外维护来控制高度。MIT 二叉树讲义

这里的代码假定输入是无环、无共享孩子的正常二叉树，key 是可比较整数；它不是不可信图结构的验证器。

验证时，把祖先的范围带下去

根没有上下界。向左走，收紧上界；向右走，收紧下界。前面的 6 接到的范围是 $(8,10)$，因此立即失败。

None 表示没有边界，不用某个猜测的“大整数”充当无穷大。

@dataclass
class TreeNode:
    value: int
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None

def valid_bst(root):
    pending = [(root, None, None)]
    while pending:
        node, lower, upper = pending.pop()
        if node is None:
            continue
        if lower is not None and node.value <= lower:
            return False
        if upper is not None and node.value >= upper:
            return False
        pending.append((node.right, node.value, upper))
        pending.append((node.left, lower, node.value))
    return True

TreeNode 需要 from dataclasses import dataclass。所有节点都要检查，时间 $O(n)$；显式 DFS 栈最坏 $O(h)$，退化时仍可能到 $O(n)$。迭代（iteration）避免 Python 递归（recursion）深度限制，但没有凭空省掉状态。

中序遍历为什么是排序后的顺序

先左子树，再根，再右子树。左边全小于根，右边全大于根；对子树重复同样的论证，就得到严格递增序列。

        8
       / \
      3   10
     / \
    1   6

inorder: 1 → 3 → 6 → 8 → 10

因此第 3 小是 6。无需先生成整个数组：每弹出一个待访问节点，就消耗一个名额。

def kth_smallest(root, rank):
    if type(rank) is not int or rank < 1:
        raise ValueError("rank must be a positive integer")
    ancestors = []
    current = root
    while current is not None or ancestors:
        while current is not None:
            ancestors.append(current)
            current = current.left
        current = ancestors.pop()
        rank -= 1
        if rank == 0:
            return current.value
        current = current.right
    raise ValueError("rank exceeds the number of nodes")

这个函数假定输入已经是合法 BST；不会每次查询都先做一次 $O(n)$ 验证。rank 从 1 开始，空树或名次越界抛出异常。时间 $O(h+rank)$，最坏 $O(n)$；栈 $O(h)$。

如果频繁查询第几小，可以在每个节点维护子树大小。查询时比较左子树大小与目标名次，沿一条路径走，代价 $O(h)$；但插入、删除、旋转后都要维护大小，不能只给查询函数多加一个字段。

删除一个节点时，哪部分必须保住

最后一种要删除后继的原节点，否则重复 key 破坏严格顺序；若节点同时存 value，也要成对处理。这里只讲维护原理，不把它包装成完整平衡树实现。

怎么选容器，怎么检查

手测 3 类树：空树、全向右的长链、父子都对但跨祖先边界的反例。再问：允许重复 key 时，你选“计数”“固定放左边”还是“固定放右边”？三种约定的验证条件不能混用。

完整教学代码在 deeper_patterns.py。测试还会用 3,000 个节点的长链确认迭代版本不依赖递归深度，并对不同插入顺序核对排名。