Hello 算法：二叉搜索树 Python 实现全解析——查找、插入、删除的逐步可视化

本篇围绕《Hello 算法》仓库中的 Python Tutor 可视化文档 binary_search_tree.md 展开，完整解读其中为查找（search）、插入（insert）、删除（remove）三大操作准备的二叉搜索树（Binary Search Tree，BST）Python 代码。结合仓库中的可运行实现 binary_search_tree.py 与配套教程文档 binary_search_tree.md，你将掌握 BST 的三大核心操作的代码级细节、各操作的时间复杂度推导依据，以及二叉搜索树退化场景下的性能边界。

二叉搜索树是什么

二叉搜索树满足以下两条性质（详见 教程文档）：

1. 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值；
2. 任意节点的左、右子树也是二叉搜索树，即同样满足条件 1（递归定义）。

正是这条“左小右大”的有序性质，让 BST 上的查找、插入、删除都可以像二分查找一样，每轮排除一半候选区间。仓库中所有语言的实现都遵循同一套结构：一个节点类 TreeNode（持有 val、left、right）加一个树类 BinarySearchTree（持有根节点 _root），三大操作全部基于这条性质实现。

Python Tutor 文档的可视化设计

pythontutor 文档 本身是一个“可视化索引”文件：它通过函数锚点标记（[file]{binary_search_tree}-[class]{binary_search_tree}-[func]{search/insert/remove}）为三大操作各保存了一份可在 Python Tutor 中逐步执行（step-by-step）的代码快照。每份快照都是自包含的最小可运行程序——内联定义了最简 TreeNode 类和 BinarySearchTree 类，并附带一段 Driver Code 演示对应操作。下面逐段解析这三份代码。

三个操作共用的最小节点定义为：

class TreeNode:
    """二叉树节点类"""
    def __init__(self, val):
        self.val = val      # 节点值
        self.left = None     # 左子节点引用
        self.right = None    # 右子节点引用

树类只维护一个成员变量指向根节点：

class BinarySearchTree:
    """二叉搜索树"""

    def __init__(self):
        """构造方法"""
        # 初始化空树
        self._root = None

查找操作 search：循环下探，越过叶节点即止

search 可视化对应的代码如下：

def search(self, num: int) -> TreeNode | None:
    """查找节点"""
    cur = self._root
    # 循环查找，越过叶节点后跳出
    while cur is not None:
        # 目标节点在 cur 的右子树中
        if cur.val < num:
            cur = cur.right
        # 目标节点在 cur 的左子树中
        elif cur.val > num:
            cur = cur.left
        # 找到目标节点，跳出循环
        else:
            break
    return cur

实现要点有两处：

• 终止条件统一：循环在“越过叶节点”（cur is None，元素不存在）或“命中目标”（break，元素存在）时终止，函数末尾直接 return cur，一次返回覆盖两种结果——找到则返回节点对象，未找到则返回 None。
• 每次循环排除一半：cur.val < num 时目标只可能在右子树，cur.val > num 时只可能在左子树。这与二分查找算法的工作原理一致，循环次数最多等于二叉树的高度，因此树平衡时查找耗时 $O(\log n)$。

该可视化快照的 Driver Code 先按 nums = [4, 2, 6, 1, 3, 5, 7] 建树，再执行 bst.search(7) 并打印查找到的节点对象与节点值，便于在 Python Tutor 中逐指令观察 cur 指针从根节点沿 4 → 6 → 7 下探的完整路径。

插入操作 insert：pre 指针记录父节点，禁止重复值

insert 可视化对应的代码如下：

def insert(self, num: int):
    """插入节点"""
    # 若树为空，则初始化根节点
    if self._root is None:
        self._root = TreeNode(num)
        return
    # 循环查找，越过叶节点后跳出
    cur, pre = self._root, None
    while cur is not None:
        # 找到重复节点，直接返回
        if cur.val == num:
            return
        pre = cur
        # 插入位置在 cur 的右子树中
        if cur.val < num:
            cur = cur.right
        # 插入位置在 cur 的左子树中
        else:
            cur = cur.left
    # 插入节点
    node = TreeNode(num)
    if pre.val < num:
        pre.right = node
    else:
        pre.left = node

插入分两步：查找插入位置（与 search 相同，从根出发循环下探，直到 cur 越过叶节点变成 None）→ 在该位置挂载新节点。实现中有两个值得注意的工程细节：

• 不允许重复节点：二叉搜索树定义隐含“节点值唯一”，若下探过程中遇到 cur.val == num，说明该值已存在，直接返回不执行插入，否则会破坏树的有序性质。
• pre 指针记录上一轮节点：循环结束时 cur 已是 None，无法直接定位挂接点；借助每轮更新一次的 pre，可以在循环外通过比较 pre.val < num 决定把新节点挂到 pre.right 还是 pre.left，从而把新节点置于那个 None 的位置。

与查找相同，插入节点的耗时为 $O(\log n)$（树平衡时）。可视化快照的 Driver Code 在插入序列 [4, 2, 6, 1, 3, 5, 7] 之后再执行 bst.insert(16)，适合观察新节点沿 4 → 6 → 7 右链路下探、最终挂到 7 的右子节点这一完整过程。

删除操作 remove：按子节点数量分三种情况处理

remove 是三份可视化代码中最复杂的一段，也是 BST 实现的难点所在：

def remove(self, num: int):
    """删除节点"""
    if self._root is None:
        return
    # 查找节点
    cur, pre = self._root, None
    while cur is not None:
        if cur.val == num:
            break
        pre = cur
        if cur.val < num:
            cur = cur.right
        else:
            cur = cur.left
    if cur is None:
        return

    # 子节点数量 = 0 or 1
    if cur.left is None or cur.right is None:
        # 当子节点数量 = 0 / 1 时， child = null / 该子节点
        child = cur.left or cur.right
        # 删除节点 cur
        if cur != self._root:
            if pre.left == cur:
                pre.left = child
            else:
                pre.right = child
        else:
            self._root = child
    # 子节点数量 = 2
    else:
        # 获取中序遍历中 cur 的下一个节点
        tmp: TreeNode = cur.right
        while tmp.left is not None:
            tmp = tmp.left
        # 递归删除节点 tmp
        self.remove(tmp.val)
        # 用 tmp 覆盖 cur
        cur.val = tmp.val

删除的前提是删除后仍满足“左子树 < 根节点 < 右子树”的性质，因此按待删除节点的子节点数量分三类处理（与 教程文档 中的图解流程一致）：

情况一、二：度为 0 或 1（叶节点或仅有一个子节点）

child = cur.left or cur.right

这一行是 Python 的惯用写法：若两个子节点都为 None，child 取 None（叶节点，直接“摘除”）；否则取存在的那个非 None 子节点（度为 1 时，用子节点顶替被删节点的位置）。随后：

• 若 cur 不是根节点：比较 pre.left == cur 决定把 child 接回父节点的左/右引用；
• 若 cur 是根节点：直接 self._root = child 重新指定根（覆盖“整棵树只剩一个节点”时删空的情形）。

情况三：度为 2（左右子节点都有）

此时不能直接删除，必须找一个节点顶替。顶替者可以是右子树的最小节点或左子树的最大节点；代码选择右子树最小节点（即中序遍历的下一个节点）：

1. 从 cur.right 出发沿 left 一路下探，直到 tmp.left is None，得到中序后继 tmp；
2. 递归删除 tmp（self.remove(tmp.val)）：由于 tmp 是右子树最左节点，它至多只有一个右子节点，递归删除走的是上面的“度为 0 或 1”分支，不会无限递归；
3. 用 tmp 的值覆盖 cur（cur.val = tmp.val）：以值覆盖代替节点搬运，避免了搬运整棵子树的指针操作。

可视化快照的 Driver Code 恰好覆盖全部三种情况：

bst.remove(1)  # 度为 0
bst.remove(2)  # 度为 1
bst.remove(4)  # 度为 2

在 Python Tutor 中逐步执行这三行，可以分别观察“直接摘除叶节点”“用子节点顶替”“中序后继覆盖 + 递归删除”三条代码路径的分支走向。

仓库中的完整可运行版本

pythontutor 快照为追求最小化而内联了精简版 TreeNode；仓库中真正可运行、可打印树形的版本是 binary_search_tree.py，三大方法的核心逻辑与可视化快照完全一致（search、insert、remove），差异在于：

• 复用公共模块 tree_node.py 中的 TreeNode，该类额外维护一个 height 字段，供 AVL 树等后续章节使用；
• 提供 get_root() 方法与 print_tree() 工具，Driver Code 会打印每一步操作后的完整树形：

# 初始化二叉搜索树
bst = BinarySearchTree()
nums = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
# 请注意，不同的插入顺序会生成不同的二叉树，该序列可以生成一个完美二叉树
for num in nums:
    bst.insert(num)

node = bst.search(7)      # 查找节点
bst.insert(16)            # 插入节点
bst.remove(1)             # 删除节点
bst.remove(2)             # 删除节点
bst.remove(4)             # 删除节点

运行方式：在项目根目录执行 python codes/python/chapter_tree/binary_search_tree.py 即可看到初始树、查找结果、以及每次插入/删除后的树形变化。该文件顶部还通过 sys.path.append 将父目录加入模块搜索路径以导入 modules，这一细节保证脚本可直接独立运行。

中序遍历有序性与效率分析

两个性质决定了 BST 的价值边界：

中序遍历有序。中序遍历遵循“左 → 根 → 右”的顺序，而 BST 满足“左 < 根 < 右”的大小关系，因此对 BST 做中序遍历总能得到升序序列（见 教程文档图解）。这意味着在 BST 上获取有序数据只需 $O(n)$ 时间，无须额外排序。remove 操作选择“中序后继”顶替被删节点，正是利用了这一有序性：后继节点的值恰好是树中大于被删值的最小值，覆盖后不会破坏有序性质。

操作效率对比。按 教程文档 的总结，BST 各项操作的时间复杂度都是对数阶（树平衡时）：

	无序数组	二叉搜索树
查找元素	$O(n)$	$O(\log n)$
插入元素	$O(1)$	$O(\log n)$
删除元素	$O(n)$	$O(\log n)$

其中删除节点的 $O(\log n)$ 由两部分构成：查找待删除节点需要 $O(\log n)$，获取中序遍历后继节点需要 $O(\log n)$（沿右子树最左链下探，长度不超过树高）。只有在“高频添加、低频查找删除”的场景下，数组的 $O(1)$ 插入才比 BST 更有优势。

退化风险。理想情况下 BST 是“平衡”的，可在 $\log n$ 轮内完成查找；但如果在 BST 中持续按有序序列插入（例如不断插入 1、2、3…），树会退化为一条链表：

此时树的高度等于节点数 $n$，查找、插入、删除的时间复杂度全部退化为 $O(n)$。这也解释了为什么仓库后续章节引入了 AVL 树等自平衡结构（对应 avl_tree.py 与 TreeNode.height 字段），并通过旋转把树高维持在对数级别。

小结

• pythontutor 文档 为 search / insert / remove 分别保存了自包含的可视化代码快照，配合 binary_search_tree.py 的完整可运行版本，构成“逐步观察 + 直接运行”的双轨学习路径；
• 三大操作共享同一套“从根循环下探”的骨架：查找以 cur is None 或命中为终止条件；插入额外用 pre 指针定位挂接点并拒绝重复值；删除按子节点数量 0 / 1 / 2 分支处理，度为 2 时用中序后继的值覆盖并递归删除该后继；
• 树平衡时三大操作均为 $O(\log n)$，中序遍历天然升序为删除操作提供了理论依据；退化场景下的 $O(n)$ 性能边界则是引入自平衡树的直接动机。