实现二叉搜索树（BST）的插入、查找和删除操作

题目描述
二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下性质：

• 对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值
• 其右子树中的所有节点的值都大于该节点的值
• 左右子树也分别是二叉搜索树

这个题目要求你实现BST的三个基本操作：插入新节点、查找指定值的节点、以及删除指定值的节点。

基本结构
首先我们需要定义BST的节点结构：

class TreeNode:
    def __init__(self, val=0):
        self.val = val      # 节点值
        self.left = None    # 左子节点
        self.right = None   # 右子节点

插入操作
插入操作的目标是向BST中添加一个新节点，同时保持BST的性质。

步骤分解：

1. 基本情况：如果树为空（root为None），直接创建新节点作为根节点
2. 比较值大小：
   • 如果要插入的值小于当前节点值，递归插入到左子树
   • 如果要插入的值大于当前节点值，递归插入到右子树
   • 如果值相等，根据具体需求处理（通常BST不允许重复值）

详细过程：

def insert(root, val):
    # 基本情况：到达空位置，创建新节点
    if root is None:
        return TreeNode(val)
    
    # 递归插入
    if val < root.val:
        root.left = insert(root.left, val)  # 插入到左子树
    elif val > root.val:
        root.right = insert(root.right, val)  # 插入到右子树
    
    return root  # 返回更新后的根节点

查找操作
查找操作在BST中搜索特定值的节点。

步骤分解：

1. 基本情况1：如果树为空或找到目标值，返回当前节点
2. 比较值大小：
   • 目标值小于当前节点值，在左子树中继续查找
   • 目标值大于当前节点值，在右子树中继续查找

详细过程：

def search(root, val):
    # 基本情况：树为空或找到目标
    if root is None or root.val == val:
        return root
    
    # 根据值大小决定搜索方向
    if val < root.val:
        return search(root.left, val)  # 在左子树中搜索
    else:
        return search(root.right, val)  # 在右子树中搜索

删除操作
删除操作是三个操作中最复杂的，需要处理三种不同情况。

三种删除情况：

1. 要删除的节点是叶子节点：直接删除
2. 要删除的节点只有一个子节点：用子节点替代被删除节点
3. 要删除的节点有两个子节点：找到右子树的最小节点（或左子树的最大节点）替代

步骤分解：

def delete(root, val):
    if root is None:
        return root  # 树为空，直接返回
    
    # 1. 查找要删除的节点
    if val < root.val:
        root.left = delete(root.left, val)  # 在左子树中删除
    elif val > root.val:
        root.right = delete(root.right, val)  # 在右子树中删除
    else:
        # 2. 找到要删除的节点，处理三种情况
        
        # 情况1：节点只有一个子节点或没有子节点
        if root.left is None:
            return root.right  # 用右子节点替代
        elif root.right is None:
            return root.left   # 用左子节点替代
        
        # 情况2：节点有两个子节点
        # 找到右子树的最小节点（中序遍历的后继节点）
        temp = find_min(root.right)
        
        # 用后继节点的值替代当前节点值
        root.val = temp.val
        
        # 删除右子树中的后继节点（此时它最多有一个右子节点）
        root.right = delete(root.right, temp.val)
    
    return root

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

操作示例
以插入序列[5, 3, 7, 2, 4, 6, 8]为例：

1. 插入过程：

   • 插入5：成为根节点
   • 插入3：3<5，成为5的左子节点
   • 插入7：7>5，成为5的右子节点
   • 插入2：2<5→2<3，成为3的左子节点
   • 以此类推...

2. 删除节点3（有两个子节点）：

   • 找到3的右子树的最小节点（4）
   • 用4替代3的位置
   • 删除原来位置的4（该节点没有左子节点）

时间复杂度分析

• 平均情况：O(log n)，树基本平衡时
• 最坏情况：O(n)，树退化为链表时（如插入有序序列）
• 插入、查找、删除的时间复杂度相同，都取决于树的高度

关键要点

1. BST的性质保证了搜索的高效性
2. 删除操作是难点，特别是处理有两个子节点的情况
3. 保持BST平衡很重要，否则性能会退化
4. 实际应用中常使用平衡BST（如AVL树、红黑树）