使用 2 children 在 BST 中删除方法，不会删除它的前身

Question

我正在尝试为 BST 编写一个删除方法。如果有 0 或 1 children，它就有效。但是，如果有 2 children，则该方法将数据从前任（最右边的左 child）复制到 node-to-be-removed，然后应该删除前任。由于某种原因，前任仍在树中并且没有被正确删除。我确定这是一个简单的递归错误，但我就是想不通！我将不胜感激任何帮助、反馈和评论。谢谢。

    public boolean myRemove(Object o) {
    if (isEmpty()) {
        return false;
    }
    E data = (E)o;
    root = myRemoveHelper(root, data);
    size--;
    return true;
}
private Node<E> myRemoveHelper(Node<E> root, E data) {
    if (root.data == data) {
        return myRemoveIt(root);
    }
    else if (data.compareTo(root.data) < 0) {
        root.left = myRemoveHelper(root.left, data);
    }
    else {
        root.right = myRemoveHelper(root.right, data);
    }
    return root;
}
private Node<E> myRemoveIt(Node<E> nodeToRemove) {
    if (nodeToRemove.left == null && nodeToRemove.right == null) {
        return null;
    }
    else if (nodeToRemove.left == null && nodeToRemove.right != null) {
        return nodeToRemove.right;
    }
    else if (nodeToRemove.left != null && nodeToRemove.right == null) {
        return nodeToRemove.left;
    }
    else {
        Node<E> temp = nodeToRemove.right;
        while (temp.left != null) {
            temp = temp.left;
        }
        nodeToRemove.data = temp.data;

        //does not remove the duplicate! :(
        nodeToRemove.left = myRemoveHelper(temp, temp.data);
        return nodeToRemove;
    }
}

Answer 1

在你说的问题中你选择了 the rightmost left child 但是在 myRemoveIt 你去 leftmost right child in:

Node<E> temp = nodeToRemove.right;
while (temp.left != null) {
    temp = temp.left;
}

但是在你分配给左边之后：nodeToRemove.left = myRemoveHelper(temp, temp.data);。

您需要将其更改为：

nodeToRemove.right = myRemoveHelper(nodeToRemove.right, temp.data);

现在你确定 temp.data 在叶子上（或者至少我们知道他缺少左侧）并且你发送到 myRemoveHelper 的新根是右侧的作为新数据已设置。

使用 2 children 在 BST 中删除方法，不会删除它的前身

Remove method in BST with 2 children, won't remove it predecessor

tree

recursion

binary-tree

binary-search

binary-search-tree