BST не обновляет дерево после удаления узла - PullRequest
Новая
       55

BST не обновляет дерево после удаления узла

1 голос
/ 19 июня 2020

Я пытаюсь удалить узел из BST, и мой код выглядел так: 

public boolean remove(K key) throws IllegalNullKeyException{
        if(key == null) {
            throw new IllegalNullKeyException();
        }
        else {
            try {
                root = remove(root,key);
                numKeys--;
                return true;
            }catch(KeyNotFoundException e) {
                return false;

            }
        }
    }

    private Node remove(Node node, K key) throws KeyNotFoundException  {
        if(node == null) {
            throw new KeyNotFoundException();
        }
        if(key.equals(node.key)) {
            //if n has no children
            if(node.left == null && node.right == null) {
                return null;
            }
            // n has one child: returns n's other child to parent
            else if(node.left == null) {
                return node.right;
            }
            else if(node.right  == null) {
                return node.left;
            }
            //n has two children
            else if(node.left != null&& node.right  == null ) {
                Node inOrderPred = findMaxValOfLeft(root);
                node.key  = inOrderPred.key;
                node.value = inOrderPred.value;
                node.left = remove(node.left,inOrderPred.key);
                return node;
            }
        }
        else {
            if(key.compareTo(node.key) < 0) {
                remove(node.left,key);
                return node;
            }
            else if(key.compareTo(node.key) > 0) {
                remove(node.right,key);
                return node;
            }
        }
        return node;
    }

    public Node findMaxValOfLeft(Node node) {
        if(node.right == null) {
            return null;
        }
        else {
            return findMaxValOfLeft(node.right);
        }
    }

Я попытался протестировать свой код, добавив кучу узлов: 

            st.insert(7, "7");
            st.insert(3, "3");
            st.insert(11, "11");

            st.insert(1, "1");
            st.insert(5, "5");
            st.insert(9, "9");
            st.insert(13, "13");

            st.insert(0, "0");
            st.insert(2, "2");
            st.insert(4, "4");
            st.insert(6, "6");
            st.insert(8, "8");
            st.insert(10, "10");
            st.insert(12, "12");
            st.insert(14, "14");
            st.remove(6)

Хотя я успешно уменьшил numKeys для моего bst после запуска кода, мне все равно не удалось удалить узел «6» из bst, который, как я думал: 

           if(node.left == null && node.right == null) {
               return null;
           }

сможет удалить узел, так как я вернул ноль.

Любые предложения и помощь будут очень благодарны, спасибо!

1 Ответ

1 голос
/ 19 июня 2020

Вы не переназначаете левый и правый указатели с помощью рекурсивных вызовов remove. 

else {
    if(key.compareTo(node.key) < 0) {
        node.left = remove(node.left,key); //Assign the returned value to node.left
        return node;
    }
    else if(key.compareTo(node.key) > 0) {
        node.right = remove(node.right,key); //Assign the returned value to node.right
        return node;
    }
}

В вашем коде есть несколько ошибок.

1 .Метод findMaxValOfLeft. Он всегда возвращает null. 

public Node findMaxValOfLeft(Node node) {
    if(node.right == null) {
        return node; //Changed from return null.
    }
    else {
        return findMaxValOfLeft(node.right);
    }
}

2. Вторая ошибка связана с условием else if 

node.left != null&& node.right == null  //always false

Это должно быть 

node.left != null && node.right != null

3. findMaxValOfLeft вызывается с неверный аргумент. Это должно быть findMaxValOfLeft(node.left).

.
...