7.1 BST 性质：左小右大与中序有序

二叉搜索树（Binary Search Tree，简称 BST）可不是普通的二叉树，它有个很特别的规矩：对于树中的任意一个节点，它的左子树里所有的节点值都比它小，右子树里所有的节点值都比它大。这个特性听起来简单，但威力巨大——正是因为它，我们才能在 O(log n) 的时间复杂度内完成查找、插入和删除操作（当然，前提是树比较“平衡”）。

更有趣的是，如果你对一棵 BST 做中序遍历（左 → 根 → 右），得到的序列竟然是一个严格递增的有序序列！这简直是个隐藏彩蛋，很多题目就是靠这个性质来验证一棵树是不是 BST，或者用来做排序。

下面咱们先定义一下 BST 的节点结构，这是所有操作的基础。

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val      # 节点存储的值
        self.left = left    # 指向左子节点的指针
        self.right = right  # 指向右子节点的指针

有了这个基础，我们就能开始各种操作了。记住，所有操作的核心逻辑都源于“左小右大”这个金科玉律。

7.2 查找、插入、删除操作实现

BST 的三大基本操作——查找、插入、删除，都利用了其有序的特性，通过比较目标值与当前节点值的大小，来决定是往左子树还是右子树走，从而避免了遍历整棵树。

1. 查找操作 查找是最直观的。从根节点开始，如果目标值等于当前节点值，就找到了；如果目标值更小，就去左子树找；如果更大，就去右子树找。找不到就返回 None。

2. 插入操作 插入和查找的路径几乎一样。沿着查找的路径一直往下走，直到找到一个空位置（None），在那里创建一个新节点即可。

3. 删除操作 删除稍微复杂一点，要分三种情况：

• 情况一：要删除的节点是叶子节点。直接删掉就行。
• 情况二：要删除的节点只有一个子节点。让它的父节点直接指向它的子节点，然后删掉它。
• 情况三：要删除的节点有两个子节点。这是最麻烦的。我们需要找到它的后继节点（右子树中的最小值）或者前驱节点（左子树中的最大值）来替代它，然后再把这个后继/前驱节点删掉（此时它最多只有一个子节点，回到了情况一或二）。

下表总结了这三个核心操作：

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
查找节点	search(root, key)	在以 root 为根的 BST 中查找值为 key 的节点。必需参数：根节点 root，目标值 key。
插入节点	insert(root, key)	在 BST 中插入一个值为 key 的新节点。必需参数：根节点 root，待插入值 key。注意：通常会返回新的根节点，以防原树为空。
删除节点	delete(root, key)	在 BST 中删除值为 key 的节点。必需参数：根节点 root，待删除值 key。注意：同样会返回新的根节点，因为根可能被删。

下面是一个完整的示例，包含了查找、插入和删除的实现，并带有详细的注释和错误处理。

class TreeNode:
    """二叉树节点定义"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def search(root, key):
    """
    在BST中查找指定值的节点
    :param root: TreeNode, BST的根节点
    :param key: int, 要查找的目标值
    :return: TreeNode or None, 找到的节点或None
    """
    # 如果根节点为空，或者找到了目标节点，直接返回
    if root is None or root.val == key:
        return root
    
    # 如果目标值小于当前节点值，递归搜索左子树
    if key < root.val:
        return search(root.left, key)
    # 否则，递归搜索右子树
    else:
        return search(root.right, key)

def insert(root, key):
    """
    在BST中插入一个新节点
    :param root: TreeNode, BST的根节点
    :param key: int, 要插入的值
    :return: TreeNode, 插入后BST的新根节点
    """
    # 如果树为空，创建一个新节点作为根
    if root is None:
        return TreeNode(key)
    
    # 如果要插入的值小于当前节点值，递归插入左子树
    if key < root.val:
        root.left = insert(root.left, key)
    # 如果要插入的值大于当前节点值，递归插入右子树
    elif key > root.val:
        root.right = insert(root.right, key)
    # 如果值相等，根据BST定义，通常不插入重复值，直接返回
    else:
        return root
    
    # 返回根节点（可能未改变）
    return root

def find_min(node):
    """辅助函数：找到以node为根的子树中的最小值节点（最左边的节点）"""
    while node.left is not None:
        node = node.left
    return node

def delete(root, key):
    """
    在BST中删除一个节点
    :param root: TreeNode, BST的根节点
    :param key: int, 要删除的值
    :return: TreeNode, 删除后BST的新根节点
    """
    # 基线条件：如果树为空，无法删除，返回None
    if root is None:
        return root

    # 递归查找要删除的节点
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        # 找到了要删除的节点
        # 情况1：节点是叶子节点 或 只有右子树
        if root.left is None:
            return root.right
        # 情况2：节点只有左子树
        elif root.right is None:
            return root.left
        # 情况3：节点有两个子节点
        else:
            # 找到右子树中的最小值节点（后继节点）
            successor = find_min(root.right)
            # 用后继节点的值替换当前节点的值
            root.val = successor.val
            # 递归删除右子树中的后继节点（它最多只有一个右子节点）
            root.right = delete(root.right, successor.val)
    
    return root

# ===== 使用示例 =====
if __name__ == "__main__":
    # 创建一个空的BST
    root = None
    
    # 插入一系列值
    values_to_insert = [50, 30, 70, 20, 40, 60, 80]
    for val in values_to_insert:
        root = insert(root, val)
        print(f"插入 {val} 后，根节点为: {root.val}")
    
    # 尝试查找
    target = 40
    found_node = search(root, target)
    if found_node:
        print(f"成功找到值为 {target} 的节点!")
    else:
        print(f"未找到值为 {target} 的节点。")
    
    # 尝试删除一个有两个子节点的节点 (50)
    print("删除根节点 50...")
    root = delete(root, 50)
    # 验证删除后，中序遍历是否依然有序
    def inorder_traversal(node, result):
        if node:
            inorder_traversal(node.left, result)
            result.append(node.val)
            inorder_traversal(node.right, result)
    
    sorted_list = []
    inorder_traversal(root, sorted_list)
    print(f"删除后的中序遍历结果: {sorted_list}") # 应该依然是有序的

注意事项：

• 整体调用注意事项：insert 和 delete 函数都会返回树的根节点。这是因为当树为空时，插入操作会创建一个新的根；而删除操作有可能会删除原来的根节点，因此必须用函数的返回值来更新根节点的引用，否则会丢失对整棵树的引用。
• 接受的返回值注意事项：search 函数返回的是一个 TreeNode 对象或者 None。在使用返回值之前，务必检查它是否为 None，以避免 AttributeError。

7.3 平衡性问题与退化为链表的风险

BST 虽然在理想情况下能提供 O(log n) 的高效操作，但它有一个致命的弱点——极度依赖于输入数据的顺序。

想象一下，如果我们按顺序插入一组已经排好序的数字，比如 [1, 2, 3, 4, 5]。按照 BST 的插入规则，1 是根，2 比 1 大所以成为 1 的右子节点，3 比 1 和 2 都大，所以成为 2 的右子节点……最终，这棵 BST 会退化成一条单向链表！

在这种最坏的情况下，所有的操作（查找、插入、删除）的时间复杂度都会从理想的 O(log n) 恶化到 O(n)，跟在一个普通数组里线性查找没啥区别，完全失去了 BST 的优势。

这个问题的根本原因在于 BST 没有自我调节平衡的能力。为了解决这个问题，计算机科学家们发明了各种自平衡二叉搜索树，比如 AVL 树、红黑树等。它们通过在插入和删除操作后执行特定的旋转操作，来保证树的高度始终保持在 O(log n) 级别，从而确保操作效率。

虽然我们本章的重点不是这些高级数据结构，但了解这个“退化”风险至关重要。它提醒我们，在实际工程中，如果不能保证输入数据的随机性，直接使用简单的 BST 可能会带来性能灾难。Python 内置的 dict 和 set 之所以高效，正是因为它们底层使用了经过高度优化的哈希表，而不是简单的 BST。

7.4 验证 BST：中序遍历 or 递归范围检查

如何判断一棵给定的二叉树是不是一棵合法的 BST？这是一个非常经典的面试题。主要有两种思路：

思路一：中序遍历法 正如我们在 7.1 节提到的，BST 的中序遍历结果必然是一个严格递增的序列。所以，我们可以对树进行一次中序遍历，将所有节点的值收集到一个列表里，然后检查这个列表是否严格递增。

这种方法简单直观，但需要 O(n) 的额外空间来存储遍历结果。

思路二：递归范围检查法 这是一种更优雅、空间效率更高的方法。核心思想是：对于任何一个节点，它的值都必须落在一个特定的范围内。例如，根节点的值可以是任何数（范围是 (-∞, +∞)）；根的左子节点的值必须小于根的值（范围是 (-∞, root.val)）；根的右子节点的值必须大于根的值（范围是 (root.val, +∞)）。以此类推，我们可以递归地向下传递这个有效范围。

一旦发现某个节点的值超出了它应有的范围，就可以立刻断定这不是一棵 BST。

下表对比了这两种方法：

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
中序遍历验证	is_valid_bst_inorder(root)	通过中序遍历生成序列并检查是否递增。必需参数：根节点 root。空间复杂度 O(n)。
递归范围验证	is_valid_bst_recursive(root)	通过递归传递上下界来验证每个节点。必需参数：根节点 root。空间复杂度 O(height)，通常更优。

下面是两种方法的具体实现：

# 假设 TreeNode 类已定义

def is_valid_bst_inorder(root):
    """
    方法一：通过中序遍历验证BST
    :param root: TreeNode, 二叉树的根节点
    :return: bool, 是否为有效的BST
    """
    def inorder(node, values):
        """中序遍历辅助函数"""
        if not node:
            return
        inorder(node.left, values)
        values.append(node.val)
        inorder(node.right, values)
    
    # 存储中序遍历结果
    values = []
    inorder(root, values)
    
    # 检查列表是否严格递增
    for i in range(1, len(values)):
        if values[i] <= values[i-1]: # 注意：BST通常不允许重复值
            return False
    return True

def is_valid_bst_recursive(root):
    """
    方法二：通过递归范围检查验证BST
    :param root: TreeNode, 二叉树的根节点
    :return: bool, 是否为有效的BST
    """
    def validate(node, low, high):
        """
        递归验证函数
        :param node: 当前节点
        :param low: 当前节点值的下界（不包含）
        :param high: 当前节点值的上界（不包含）
        :return: bool
        """
        # 空节点是有效的
        if not node:
            return True
        
        # 检查当前节点值是否在有效范围内
        if node.val <= low or node.val >= high:
            return False
        
        # 递归检查左右子树，并更新范围
        # 左子树的所有值必须小于node.val，所以上界更新为node.val
        # 右子树的所有值必须大于node.val，所以下界更新为node.val
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))
    
    # 初始调用，根节点的范围是负无穷到正无穷
    import math
    return validate(root, -math.inf, math.inf)

# ===== 使用示例 =====
if __name__ == "__main__":
    # 构建一个合法的BST:     5
    #                      /   \
    #                     3     8
    #                    / \   / \
    #                   2   4 7   9
    root_valid = TreeNode(5)
    root_valid.left = TreeNode(3)
    root_valid.right = TreeNode(8)
    root_valid.left.left = TreeNode(2)
    root_valid.left.right = TreeNode(4)
    root_valid.right.left = TreeNode(7)
    root_valid.right.right = TreeNode(9)
    
    # 构建一个非法的二叉树:     5
    #                        /   \
    #                       3     8
    #                      / \   / \
    #                     2   6 7   9  (注意：6 > 5，但它在5的左子树里！)
    root_invalid = TreeNode(5)
    root_invalid.left = TreeNode(3)
    root_invalid.right = TreeNode(8)
    root_invalid.left.left = TreeNode(2)
    root_invalid.left.right = TreeNode(6) # 这里是错误的
    root_invalid.right.left = TreeNode(7)
    root_invalid.right.right = TreeNode(9)
    
    print("验证合法BST:")
    print("中序遍历法:", is_valid_bst_inorder(root_valid))
    print("递归范围法:", is_valid_bst_recursive(root_valid))
    
    print("\n验证非法二叉树:")
    print("中序遍历法:", is_valid_bst_inorder(root_invalid))
    print("递归范围法:", is_valid_bst_recursive(root_invalid))

注意事项：

• 整体调用注意事项：两种方法都能正确工作，但在处理大型树时，递归范围法通常更优，因为它不需要额外的 O(n) 空间，并且可以在发现第一个违规节点时立即返回 False，无需遍历完整棵树。
• 接受的返回值注意事项：两个函数都返回一个布尔值 (True 或 False)，直接表示输入的树是否为有效的 BST。调用者可以根据这个结果进行后续逻辑判断。