Метод удаления в BST с двумя детьми, не удалит его предшественник - PullRequest
Новая
       34

Метод удаления в BST с двумя детьми, не удалит его предшественник

0 голосов
/ 13 декабря 2018

Я пытаюсь написать метод удаления для BST.Работает, если есть 0 или 1 ребенок.Однако, если есть 2 дочерних элемента, метод копирует данные из предшественника (самый правый левый дочерний элемент) в узел, который должен быть удален, и затем ПРЕДПОЛАГАЕТСЯ удалить предшественник.По какой-то причине предшественник все еще находится в дереве и не удаляется должным образом.Я уверен, что это простая ошибка рекурсии, но я просто не могу понять это!Буду очень признателен за любую помощь, отзывы и комментарии.Спасибо. 

    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;
    }
}

1 Ответ

0 голосов
/ 13 декабря 2018

В вопросе, который вы сказали, вы берете 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, является правым, поскольку новые данные уже установлены.

...