二叉搜索树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,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightdefsearch_bst(root,target):ifnotrootorroot.valtarget:returnrootiftargetroot.val:returnsearch_bst(root.left,target)else:returnsearch_bst(root.right,target)definsert_bst(root,val):ifnotroot:returnTreeNode(val)ifvalroot.val:root.leftinsert_bst(root.left,val)elifvalroot.val:root.rightinsert_bst(root.right,val)returnroot# 若val已存在不重复插入可根据需求调整在二叉搜索树BST中删除操作需在移除目标节点的同时严格维持BST性质即左子树所有值 当前节点 右子树所有值。根据待删除节点的子节点数量分为以下三种情况每种情况的处理逻辑如下✅ 情况1节点为叶子节点无子节点逻辑直接删除该节点将其父节点指向它的指针置为None。说明不破坏任何BST结构最简单情形。✅ 情况2节点仅有一个子节点左或右子树非空另一个为空逻辑用其唯一子节点替代该节点位置即让父节点直接指向该子节点。说明由于BST性质在单支路径上天然保持如parent node right_child或left_child node parent替换后仍满足BST约束。✅ 情况3节点有两个子节点左右子树均非空核心思想需选择一个语义等价且可安全上移的替代节点——即其中序前驱左子树中的最大值或中序后继右子树中的最小值。二者均与原节点值“相邻”替换后能无缝维持有序性。标准做法常用中序后继在右子树中找到最小节点即一直向左走到叶子用该后继节点的值覆盖待删节点的值递归删除该后继节点它必为叶子或仅有一个右子节点——因它是右子树最左节点故无左子树。等价做法用中序前驱在左子树中找最大节点一直向右同理覆盖并删除。关键点不直接交换节点对象而是值覆盖 删除冗余节点避免指针重连复杂性。 补充说明重复值处理若BST允许重复值如插入到右子树删除时通常只删第一个匹配节点若定义为“不允许重复”则查找唯一匹配即可。实现要点需在递归/迭代中维护父节点引用或返回新子树根以便修改父指针Python中常采用返回更新后的子树根节点方式实现见下方代码示例。defdelete_node(root,key):ifnotroot:returnNoneifkeyroot.val:root.leftdelete_node(root.left,key)elifkeyroot.val:root.rightdelete_node(root.right,key)else:# 找到待删节点ifnotroot.left:# 情况1或2无左子树 → 返回右子树含空returnroot.rightifnotroot.right:# 情况1或2无右子树 → 返回左子树returnroot.left# 情况3双子树 → 用中序后继右子树最小值替换successorroot.rightwhilesuccessor.left:successorsuccessor.left root.valsuccessor.val# 值覆盖root.rightdelete_node(root.right,successor.val)# 删除后继必为情况1或2returnroot