二叉搜索树（BST）记忆与图解

一句话记忆：对每个节点，左子树所有值都小于它，右子树所有值都大于它；左右子树也必须各自满足这条规则。

1. 性质

8 左边的整棵子树都 < 8，右边的整棵子树都 > 8。
这一规则对每个节点递归成立。例如 6 的左子树都 < 6，右子树都 > 6。
只有“左孩子小、右孩子大”还不够。 下图不是 BST：12 虽然是 5 的右孩子，但它在 10 的左子树中，违反了“左子树所有值 < 10”。

2. 构建：从空树逐个插入

依次插入 8, 3, 10, 1, 6, 14, 4, 7, 13，便得到上面的示例树。插入顺序会影响形状：同一组值，换个顺序，树的高度可能不同。

记忆路径：从根开始，比当前节点小就往左，大就往右；走到空位置就放进去。

例如向示例树插入 5：

若从有序序列按顺序逐个插入，例如 1, 2, 3, 4, 5，会退化成链：

因此，普通 BST 不保证平衡。

3. 查找：每次排除半棵候选子树

查找 7：7 < 8，到左边；7 > 3，到右边；7 > 6，再到右边；找到 7。

1	8 → 3 → 6 → 7

如果走到空节点，说明值不存在。找最小值就一直向左，找最大值就一直向右。

4. 删除：先看目标有几个孩子

删除是最容易忘的部分。口诀：零个直接删，一个孩子接上去，两个孩子找接班人。

情况 A：没有孩子（叶子）

删除 7，直接把父节点指向它的链接改为空。

情况 B：只有一个孩子

删除 10，让其唯一的孩子 14 接替它的位置；14 原有的子树保持不变。

情况 C：有两个孩子

删除 8 时，通常找它的中序后继：右子树的最小值，也就是 10。用 10 替换 8，再删除原来位置的 10。

图中省略了 3 下方未改变的子树。也可以选择中序前驱（左子树最大值，即 7）作为接班人，原理相同。后继或前驱至多有一个孩子，所以第二次删除会落到情况 A 或 B。

易错点：替换的是值或节点位置，还要处理接班人原来的位置；否则树里会留下两个相同的值。实现时尤其要正确更新父节点的链接。

5. 遍历：中序会得到升序

中序遍历顺序是 左子树 → 当前节点 → 右子树。对示例树：

1	1, 3, 4, 6, 7, 8, 10, 13, 14

所以判断一棵树是否可能是 BST，可以检查中序结果是否严格递增（本文不允许重复值）。不过实际验证时，用节点的上下界约束更直接，也更容易准确指出错误位置。

6. 一份能对照记忆的 Python 实现

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def search(root, value):
    while root is not None:
        if value < root.value:
            root = root.left
        elif value > root.value:
            root = root.right
        else:
            return root
    return None


def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    # 相等时不插入：本文采用“不存重复值”的约定。
    return root


def delete(root, value):
    if root is None:
        return None

    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        if root.left is None:       # 零个孩子，或只有右孩子
            return root.right
        if root.right is None:      # 只有左孩子
            return root.left

        # 两个孩子：用右子树最小值（中序后继）替换。
        successor = root.right
        while successor.left is not None:
            successor = successor.left
        root.value = successor.value
        root.right = delete(root.right, successor.value)

    return root


def inorder(root):
    if root is not None:
        yield from inorder(root.left)
        yield root.value
        yield from inorder(root.right)


root = None
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, value)

assert list(inorder(root)) == [1, 3, 4, 6, 7, 8, 10, 13, 14]
root = delete(root, 8)
assert list(inorder(root)) == [1, 3, 4, 6, 7, 10, 13, 14]

注意每次都写 root = insert(root, x) 或 root = delete(root, x)：根节点本身也可能改变，例如从空树插入，或删除根节点。

7. 复杂度与速记

设树高为 h、节点数为 n：

操作	时间	原因
查找、插入、删除	`O(h)`	都沿一条从根向下的路径进行
找最小值、最大值	`O(h)`	一直向左或向右
中序遍历	`O(n)`	每个节点访问一次

树较平衡时：h = O(log n)，查找、插入、删除约为 O(log n)。
退化成链时：h = O(n)，这些操作最坏为 O(n)。
若需要保证对数级高度，可学习 AVL 树或红黑树。

复述：

性质：左整棵小，右整棵大，递归成立。
构建/插入：逐个比较，向左或向右，空位落下。
查找：按大小选择一边，找到目标或走到空位。
删除：零孩直接删；单孩直接接；双孩用后继（或前驱）替换，再删原接班人。
遍历：中序得到升序；效率取决于树高。

__END__

二叉搜索树老是忘