第 30 课 - 二叉搜索树

学习目标

完成本课学习后，你将能够：

理解二叉搜索树（BST）的核心性质和结构。
实现向 BST 中插入新元素和查找特定元素的算法。
实现从 BST 中删除元素的算法，并处理其三种情况。
分析 BST 在最优和最差情况下的时间复杂度。
认识 BST 的局限性以及它作为更高级数据结构（如 AVL 树）基础的重要性。

核心概念

二叉搜索树是一种特殊的二叉树，它有一个非常重要的性质：对于树中的任意节点，其左子树上所有节点的值都小于该节点的值，其右子树上所有节点的值都大于该节点的值。 这个性质也被称为 BST 的有序性。

你可以把它想象成一个有组织的层级结构。比如，一个公司的组织架构，CEO 是根节点，他管理着两个副总裁（左子树和右子树），左副总裁管理的都是级别比他低的人，右副总裁管理的都是级别比他高的人（当然，这里假设一个极端的分级）。这个性质使得 BST 的查找、插入和删除操作在理想情况下非常高效。

核心操作演示：

查找：从根节点开始，比根小就去左子树找，比根大就去右子树找，直到找到或子树为空。
插入：与查找类似，找到该插入的位置（一个叶子节点），然后挂载上去。
删除：这是最复杂的操作，需要分三种情况处理（待删除节点是叶子、只有一个孩子、有两个孩子）。

代码示例

下面是一个完整的 Python 实现，包含了一个 BST 类和它的核心操作。

class TreeNode:
    """树节点类"""
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    """二叉搜索树类"""
    def __init__(self):
        self.root = None

    # 查找操作
    def search(self, value):
        """查找值是否存在，返回节点或 None"""
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        """递归查找的辅助函数"""
        if node is None or node.value == value:
            return node
        if value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

    # 插入操作
    def insert(self, value):
        """插入新值"""
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        """递归插入的辅助函数"""
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)
        # 如果值相等，根据需求可以选择忽略、计数或抛出异常

    # 删除操作
    def delete(self, value):
        """删除指定值"""
        self.root = self._delete_recursive(self.root, value)

    def _delete_recursive(self, node, value):
        """递归删除的辅助函数"""
        if node is None:
            return None

        # 1. 找到要删除的节点
        if value < node.value:
            node.left = self._delete_recursive(node.left, value)
        elif value > node.value:
            node.right = self._delete_recursive(node.right, value)
        else: # 找到了要删除的节点
            # 情况1：叶子节点或只有一个孩子
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            # 情况2：有两个孩子
            # 找到右子树中的最小节点（即后继节点）
            successor = self._find_min(node.right)
            # 用后继节点的值替换当前节点的值
            node.value = successor.value
            # 从右子树中删除这个后继节点
            node.right = self._delete_recursive(node.right, successor.value)

        return node

    def _find_min(self, node):
        """找到以给定节点为根的子树中的最小节点"""
        current = node
        while current.left is not None:
            current = current.left
        return current

    # 中序遍历（用于验证BST性质）
    def inorder_traversal(self):
        """中序遍历，结果应为升序序列"""
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)

# 测试代码
if __name__ == "__main__":
    bst = BinarySearchTree()
    values = [50, 30, 70, 20, 40, 60, 80]

    print("插入节点：", values)
    for v in values:
        bst.insert(v)

    print("中序遍历（应为升序）：", bst.inorder_traversal())

    # 查找
    node = bst.search(40)
    print(f"查找 40: {'找到，值为 ' + str(node.value) if node else '未找到'}")

    # 删除
    print("\n删除叶子节点 20")
    bst.delete(20)
    print("中序遍历：", bst.inorder_traversal())

    print("\n删除有一个子节点的节点 30 (现在只有右孩子40)")
    bst.delete(30)
    print("中序遍历：", bst.inorder_traversal())

    print("\n删除有两个子节点的节点 50")
    bst.delete(50)
    print("中序遍历：", bst.inorder_traversal())

实践练习

练习1：验证BST性质 编写一个函数 is_valid_bst(root)，给定一个二叉树的根节点，判断它是否是一个有效的二叉搜索树。

输入：一个 TreeNode 对象（可能为空）。
要求：不仅检查直接的父子关系，还要检查整棵树的值域范围。
预期输出：True 或 False。
提示：可以使用递归，并传递当前节点允许的最小值和最大值作为参数。

练习2：计算树高 编写一个函数 tree_height(root)，计算并返回给定二叉搜索树的高度（从根到最远叶子节点的边数）。

输入：一个 TreeNode 对象（可能为空）。
预期输出：一个整数。空树高度为 -1，只有一个根节点的树高度为 0。
提示：高度 = max(左子树高度，右子树高度) + 1。

练习3：层序遍历 修改或扩展示例代码，为 BinarySearchTree 类添加一个 level_order_traversal 方法。层序遍历（也称为广度优先遍历）会按层从左到右访问所有节点。

输入：无（操作当前树）。
预期输出：一个包含所有节点值的列表，顺序为层序。
提示：使用一个队列（如 collections.deque）来实现。

常见错误

忽略 BST 的全局有序性：初学者在验证 BST 时，可能只检查 node.left.val < node.val < node.right.val，但这不充分。例如，一个节点的左子树的右孩子可能大于该节点，这破坏了 BST 性质。必须保证左子树所有节点都小于根节点。
删除操作处理不当：
- 情况2（有两个孩子）：直接删除节点会导致树断裂。正确做法是找到其前驱节点（左子树中的最大值）或后继节点（右子树中的最小值）来替换它，然后删除那个前驱或后继节点。
- 忘记将删除操作的结果（新的子树根）赋值回父节点的 left 或 right 指针。
递归终止条件错误：在插入或删除的递归函数中，忘记处理 node is None 的基本情况，或者返回值处理不当（例如删除操作中，删除后应该返回新的子树根）。

小结

核心性质：二叉搜索树的关键是左 < 根 < 右 的有序性，这使得中序遍历能输出有序序列。
操作效率：在最优情况（树比较平衡）下，查找、插入、删除的时间复杂度为 O(log n)。最差情况（树退化成链表）下，复杂度退化为 O(n)。
关键操作：
- 查找/插入：沿着一条路径从根向下，比较决定方向。
- 删除：是最复杂的，需要分叶子、单孩子、双孩子三种情况讨论。
局限性：普通的 BST 无法自我平衡，可能因插入顺序（如升序插入）而性能严重退化。
重要基础：BST 是理解平衡二叉搜索树（如 AVL 树、红黑树）的基础。这些高级数据结构通过旋转等操作维持树的平衡，从而保证操作始终在 O(log n) 时间内完成。我们将在下一课学习其中的 AVL 树。

练习编辑器

rust