二叉排序树的删除java

二叉排序树（Binary Search Tree，BST）的删除操作涉及到对已存在节点的查找、替换以及可能的结构调整。在Java中，删除一个节点通常分为三个步骤：

1. **查找目标节点**：
- 如果节点不存在，直接返回，不做任何处理；
- 如果找到该节点，将其分为三种情况：左子树为空、右子树为空和左右子树都不空。

2. **删除节点**：
- 左子树为空的情况：将右子树作为新根节点；
- 右子树为空的情况：将左子树作为新根节点；
- 左右子树都不空的情况：找到右子树中的最小元素（对于左旋左子树），将这个最小元素替换到当前节点，并递归地在右子树中删除它。

3. **调整结构**：
- 删除后，需要保持BST的性质：即左子树的所有节点值都小于当前节点，右子树的所有节点值都大于当前节点。这可能涉及旋转操作，如左旋或右旋，以保证BST的特性。

以下是删除节点的一个简化版伪代码示例：

Node delete(Node root, int key) {
    if (root == null) return null;
    
    // 递归查找并删除
    if (key < root.key)
        root.left = delete(root.left, key);
    else if (key > root.key)
        root.right = delete(root.right, key);
    else { // 找到了要删除的节点
        // 分三种情况处理
        Node temp = root;
        if (temp.left == null) {
            temp = temp.right; // 将右子树复制给原节点
        } else if (temp.right == null) {
            temp = temp.left; // 将左子树复制给原节点
        } else { // 存在一个后继节点
            Node successor = findMin(temp.right); // 查找右子树最小节点
            temp.key = successor.key; // 更新当前节点
            temp.right = delete(temp.right, successor.key); // 递归删除后继节点
        }
    }

    return root;
}

// 辅助函数：查找最小节点
Node findMin(Node node) {
    while (node.left != null) node = node.left;
    return node;
}