二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树数据结构

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树数据结构，其核心性质是：对于树中任意节点，其左子树中所有节点的值均小于该节点的值，右子树中所有节点的值均大于该节点的值，且左右子树本身也均为BST（递归定义）。这一性质保证了中序遍历BST可得到严格递增的有序序列。

BST支持高效的基本操作（平均时间复杂度为 O(log n)，最坏退化为链表时为 O(n)）：

• 查找（Search）：从根开始，比较目标值与当前节点值，小于则向左，大于则向右，等于则命中；
• 插入（Insert）：沿查找路径找到空位置后插入新节点，维持BST性质；
• 删除（Delete）：分三种情况处理——无子节点（直接删）、仅一个子节点（用子节点替代）、两个子节点（用中序前驱或后继替换，再递归删除该前驱/后继）；
• 中序遍历（In-order Traversal）：输出升序序列，常用于排序或范围查询。

BST是许多高级数据结构（如AVL树、红黑树）的基础，广泛应用于数据库索引、字典实现、动态集合操作等场景。

classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=rightdefsearch_bst(root,target):ifnotrootorroot.val==target:returnrootiftarget<root.val:returnsearch_bst(root.left,target)else:returnsearch_bst(root.right,target)definsert_bst(root,val):ifnotroot:returnTreeNode(val)ifval<root.val:root.left=insert_bst(root.left,val)elifval>root.val:root.right=insert_bst(root.right,val)returnroot# 若val已存在，不重复插入（可根据需求调整）

在二叉搜索树（BST）中，删除操作需在移除目标节点的同时严格维持BST性质（即左子树所有值 < 当前节点 < 右子树所有值）。根据待删除节点的子节点数量，分为以下三种情况，每种情况的处理逻辑如下：

✅ 情况1：节点为叶子节点（无子节点）

• 逻辑：直接删除该节点，将其父节点指向它的指针置为None。
• 说明：不破坏任何BST结构，最简单情形。

✅ 情况2：节点仅有一个子节点（左或右子树非空，另一个为空）

• 逻辑：用其唯一子节点替代该节点位置（即让父节点直接指向该子节点）。
• 说明：由于BST性质在单支路径上天然保持（如parent < node < right_child或left_child < node < parent），替换后仍满足BST约束。

✅ 情况3：节点有两个子节点（左右子树均非空）

• 核心思想：需选择一个语义等价且可安全上移的替代节点——即其中序前驱（左子树中的最大值）或中序后继（右子树中的最小值）。二者均与原节点值“相邻”，替换后能无缝维持有序性。
• 标准做法（常用中序后继）：
  1. 在右子树中找到最小节点（即一直向左走到叶子）；
  2. 用该后继节点的值覆盖待删节点的值；
  3. 递归删除该后继节点（它必为叶子或仅有一个右子节点——因它是右子树最左节点，故无左子树）。
• 等价做法（用中序前驱）：在左子树中找最大节点（一直向右），同理覆盖并删除。
• 关键点：不直接交换节点对象，而是值覆盖 + 删除冗余节点，避免指针重连复杂性。

🌟 补充说明：

• 重复值处理：若BST允许重复值（如插入到右子树），删除时通常只删第一个匹配节点；若定义为“不允许重复”，则查找唯一匹配即可。
• 实现要点：需在递归/迭代中维护父节点引用（或返回新子树根），以便修改父指针；Python中常采用返回更新后的子树根节点方式实现（见下方代码示例）。

defdelete_node(root,key):ifnotroot:returnNoneifkey<root.val:root.left=delete_node(root.left,key)elifkey>root.val:root.right=delete_node(root.right,key)else:# 找到待删节点ifnotroot.left:# 情况1或2：无左子树 → 返回右子树（含空）returnroot.rightifnotroot.right:# 情况1或2：无右子树 → 返回左子树returnroot.left# 情况3：双子树 → 用中序后继（右子树最小值）替换successor=root.rightwhilesuccessor.left:successor=successor.left root.val=successor.val# 值覆盖root.right=delete_node(root.right,successor.val)# 删除后继（必为情况1或2）returnroot