3.2 二叉搜索树：有序心法与退化走火

3.2 二叉搜索树：有序心法与退化走火

本节摘要：二叉搜索树（BST）在树上加一条不变量——任何节点，左子树所有键小于它，右子树所有键大于它。查找因此变成"每层二选一"，树平衡时是 O(log n)；中序遍历天然输出升序。但这份承诺依赖树的形状：按序插入会把 BST 退化成链，查找跌回 O(n)——这是本节要亲手复现的走火现场，也是下一节平衡树的引子。

一条不变量，买来两样本事

BST 的心法只有一句话：左小右大，对每个节点成立。注意它约束的是整棵子树而不只是直接孩子——"左孩子的右孙"也必须小于根。这条不变量立刻兑现两样本事：

其一，查找是沿高度下降的。目标比当前节点小就往左，大就往右，每步排除一整棵子树。平衡时每步砍掉约一半候选，与二分查找同源，O(log n)。

其二，中序遍历天然升序。中序"左根右"的次序恰好与"小中大"的大小关系同构，不需要任何排序动作。

# BST 三招：插入、查找、中序验证
class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)                 # 挂到空位
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        return node                           # 相等则不重复插入

    def search(self, key):
        node, steps = self.root, 0
        while node:
            steps += 1                        # 每比较一次记一步
            if key == node.key:
                return True, steps
            node = node.left if key < node.key else node.right
        return False, steps

    def inorder(self):
        out, stack, node = [], [], self.root
        while stack or node:                  # 迭代中序：显式栈版
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            out.append(node.key)
            node = node.right
        return out

t = BST()
for k in (50, 30, 70, 20, 40, 60, 80):
    t.insert(k)
print("中序遍历：", t.inorder())
# 输出：中序遍历： [20, 30, 40, 50, 60, 70, 80]（插入无序，中序天然升序）
for k in (60, 20, 99):
    print(f"查 {k}：", t.search(k))
# 输出：
# 查 60：(True, 3)
# 查 20：(True, 3)
# 查 99：(False, 3)
# 这棵树高度 2，任何查找最多 3 次比较——每层二选一的兑现
​

查找 60 走的路线是 50→70→60，查找 20 走 50→30→20：比较次数等于目标所在深度加一，与树高直接挂钩。树有多矮，BST 就有多快。

删除：三分支的精细手术

删除比插入难，按孩子数分三种情形：

• 叶子节点：直接摘除，无双亲牵挂；
• 单孩子：孩子顶替上位（绕过被删节点接回去）；
• 双孩子：找中序后继（右子树最左节点，即右子树最小值），用它的键顶替被删键，再删除那个后继——后继在右子树里没有左孩子，删除它必然落入前两种情形。

# BST 删除：三分支处理
def min_node(node):                    # 一路向左找最小
    while node.left:
        node = node.left
    return node

def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:                              # 找到目标
        if node.left is None:          # 情形 1/2：无左子，右子顶替（叶子时右子为 None）
            return node.right
        if node.right is None:         # 情形 2：无右子，左子顶替
            return node.left
        succ = min_node(node.right)    # 情形 3：中序后继顶键
        node.key = succ.key
        node.right = delete(node.right, succ.key)   # 再删后继本体
    return node

t.root = delete(t.root, 20)            # 删叶子
print("删 20（叶子）后中序：", t.inorder())
t.root = delete(t.root, 30)            # 删单孩子节点（只剩右孩子 40）
print("删 30（单孩子）后中序：", t.inorder())
t.root = delete(t.root, 50)            # 删双孩子的根
print("删 50（双孩子）后中序：", t.inorder())
# 输出：
# 删 20（叶子）后中序： [30, 40, 50, 60, 70, 80]
# 删 30（单孩子）后中序： [40, 50, 60, 70, 80]
# 删 50（双孩子）后中序： [40, 60, 70, 80]
# 40 与 60 都还在：50 被后继 60 顶替，60 原位置被摘除
​

双孩子情形的后继选择不是随意的：中序后继是"大于被删键的最小值"，顶替后 BST 不变量原样成立。也可以用中序前驱（左子树最大值），两者等价，实现里保持一致即可。

走火入魔：顺序输入，神功尽废

BST 的全部承诺压在"树矮"上，而树的形状完全由插入顺序决定。把 1 到 7 顺序插入：1 成为根，2 只能挂在 1 的右边，3 挂 2 的右边……BST 变成一条向右的链。

# 退化实验：同一批键，两种插入顺序，两棵完全不同的树
def height(node):                      # 高度：叶为 0，空树 -1
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

chain = BST()
for k in (1, 2, 3, 4, 5, 6, 7):        # 顺序插入
    chain.insert(k)
nice = BST()
for k in (4, 2, 6, 1, 3, 5, 7):        # 平衡友好顺序
    nice.insert(k)
print("顺序插入：高度 =", height(chain.root), "；查 7 比较次数 =", chain.search(7)[1])
print("交错插入：高度 =", height(nice.root),   "；查 7 比较次数 =", nice.search(7)[1])
# 输出：
# 顺序插入：高度 = 6 ；查 7 比较次数 = 7
# 交错插入：高度 = 2 ；查 7 比较次数 = 3
# 同样 7 个节点：链状要摸到底，平衡树三步命中
​

同一批数据、同一个结构、同一份代码，仅因输入有序，查找从 3 次跌到 7 次。规模放大后更残酷：百万个键顺序插入，树高百万，查找退化为线性扫描——BST 的 O(log n) 是有条件的承诺，条件是输入"足够随机"。现实数据常常不配合：时间戳、自增主键、按字典序导入的名单，全是天然的顺序输入。

修复思路由此自然浮现：在插入删除时主动维护形状，让树无论经历什么输入都保持矮壮。付出的代价是每次操作额外的旋转步骤——这就是下一节平衡二叉法的主题（AVL 与红黑树）。提前给一张对照表热身：

⚠️ 常见坑：BST 删除的双孩子情形，最容易写错的是"拿右子树根顶替"。右子树根不一定大于左子树所有节点（它只大于被删键），不变量会被打破。必须用中序后继或前驱。

💡 关键直觉：BST 是"把二分查找的判定树直接存成数据"。二分查找每次中点比较对应树上走一步；有序数组要每次现算中点，BST 把这棵判定树物化下来，代价是必须养它平衡。

本节要点回顾

• BST 不变量：任何节点的左子树全小于它、右子树全大于它，约束整棵子树而非直接孩子；
• 两样本事：查找沿高度下降、每层排除一棵子树；中序遍历天然升序（可用作结构校验）；
• 删除三分支：摘叶、孩子顶替、后继顶键再删后继；双孩子情形必须用中序后继（右子树最小）；
• 退化实验：顺序插入使树高从 log 级涨到 n，查找跌回 O(n)——有序数据是 BST 的天敌；
• 修复方向：主动维护形状（旋转），代价与方案留给下一节的 AVL 与红黑树。

招式没变，心法要升级：怎么让树在任何输入下都保持矮壮？平衡二叉树接棒。