数据结构：二叉排序树的删除操作实现
二叉排序树删除操作详解
二叉排序树（Binary Search Tree，BST）是一种重要的数据结构，它满足以下性质：对于树中的每个节点，其左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。删除操作是BST中最复杂的操作之一，需要根据被删除节点的子树情况分别处理。
删除叶子节点
叶子节点是指没有左右子树的节点。删除这类节点相对简单，只需要将其父节点对应的指针置空即可。处理步骤包括：
- 找到要删除的节点 targetNode
- 找到targetNode的父节点parentNode(判断是否存在)
- 确定targetNode是parentNode的左子树还是右子树
- 根据以上的情况进行删除
左节点:parentNode.lChild == null
右节点:parentNode.rChild == null
这种操作不会影响树的其他部分，因为叶子节点不包含任何子树信息。时间复杂度为O(h)，h为树的高度。
删除单子树节点
当节点只有一个子树时，需要将该节点的子树提升到被删除节点的位置。具体处理需要考虑：
- 找到要删除的节点 targetNode
- 找到targetNode的父节点parentNode(判断是否存在)
- 确定targetNode是parentNode的左子树还是右子树
- 判断targetNode的子节点是targetNode的左子树还是右子树
(1). targetNode是parentNode的左子树
① targetNode有左子结点
parentNode.lChild = targetNode.lChild
② targetNode有右子结点
parentNode.lChild = targetNode.rChild
(2). targetNode是parentNode的右子树
① targetNode有左子结点
parentNode.rChild = targetNode.lChild
② targetNode有右子结点
parentNode.rChild = targetNode.rChild
这种操作保持了BST的性质，因为子树中的所有节点都满足与被删除节点父节点的大小关系。算法复杂度同样为O(h)。
删除双子树节点
这是最复杂的情况，通常采用以下策略之一：
- 用右子树的最小值替代被删除节点
- 用左子树的最大值替代被删除节点
示例代码选择第一种策略，具体实现包括：
- 找到右子树的最小节点（即最左节点）
- 用该节点的值替换被删除节点的值
- 递归删除该最小节点
这种方法保证了BST的性质，因为右子树的最小值大于左子树所有节点，小于右子树其他节点。时间复杂度为O(h)。
关键方法实现
public TreeNode findTarget(TreeNode root,Integer target){ if (root == null){ return null; } if (root.data == target){ return root; }else if (target < root.data){ if (root.lchild == null){ return null; } return findTarget(root.lchild,target); }else if (target > root.data){ if (root.rchild == null){ return null; } return findTarget(root.rchild,target); } return null; }findTarget方法采用递归方式查找目标节点，利用BST的性质缩小搜索范围。比较当前节点值与目标值决定搜索方向，直到找到匹配节点或到达叶子节点。
public TreeNode findParent(TreeNode root,Integer target){ if (root == null){ return null; } if((root.lchild!=null && root.lchild.data == target)||(root.rchild!=null && root.rchild.data == target)){ return root; }else { if(root.lchild!=null && target < root.data){ return findParent(root.lchild,target); }else if(root.rchild!=null && target > root.data){ return findParent(root.rchild,target); }else { return null; } } }findParent方法递归查找目标节点的父节点，通过检查左右子节点是否匹配目标值来确定父节点位置。
public int findRightTreeMin(TreeNode node){ while (node.lchild != null){ node = node.lchild; } int min = node.data; delete(root,min); return min; }findRightTreeMin方法通过迭代找到右子树的最左节点，即最小值节点。这是处理双子树删除的关键辅助方法。
public void delete(TreeNode root,Integer target){ if (root == null){ return; } if (root.lchild == null && root.rchild == null){ root = null; return; } TreeNode targetNode = findTarget(root,target); if (targetNode == null){ return; } TreeNode parentNode = findParent(root,target); if (targetNode.lchild == null && targetNode.rchild == null){//叶子结点 if (parentNode.lchild != null && parentNode.lchild.data == target){ parentNode.lchild = null; }else if (parentNode.rchild != null && parentNode.rchild.data == target){ parentNode.rchild = null; } }else if (targetNode.lchild != null && targetNode.rchild != null){//有左右子树 int min = findRightTreeMin(targetNode.rchild); targetNode.data = min; }else {//有一个子树 if (parentNode.lchild != null && parentNode.lchild.data == target){ if (targetNode.lchild != null){ parentNode.lchild = targetNode.lchild; }else { parentNode.lchild = targetNode.rchild; } }else if (parentNode.rchild != null && parentNode.rchild.data == target){ if (targetNode.lchild != null){ parentNode.rchild = targetNode.lchild; }else { parentNode.rchild = targetNode.rchild; } } } }delete方法是核心删除逻辑，处理三种不同情况：
- 叶子节点直接删除
- 单子树节点用子树替代
- 双子树节点用右子树最小值替换后删除原最小值节点
性能分析
二叉排序树的删除操作性能与树的高度直接相关。在平衡情况下，时间复杂度为O(log n)；最坏情况下（树退化为链表），时间复杂度为O(n)。因此，在实际应用中常使用平衡二叉搜索树（如AVL树、红黑树）来保证操作效率。
删除操作的正确性依赖于BST的性质维护，每次删除后仍需保持左子树<根节点<右子树的关系。示例代码通过三种情况的分别处理确保了这一性质的保持。