Метод удаления BST не удаляет первый вставленный узел - PullRequest
Новая
       11

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

0 голосов
/ 01 мая 2018

Я не могу понять это ... Я могу вставлять и сортировать элементы без проблем, я могу удалять узлы после первой вставки, но в особом случае я пытаюсь удалить первый узел, вставленный для запуска дерево, оно ничего не делает.

Я не понимаю, почему возникает эта проблема, любая помощь в выяснении логики приветствуется.

Разветвленная версия моего кода повторяет проблему. https://pastebin.com/hxcqpG1U

Вот мой метод удаления: 

    public void delete(KeyComp key) {
    delete(_root, key);
}

private Node delete(Node root, KeyComp key) {
    //TO-DO: DELETE AN ITEM IN THE TABLE, GIVEN THE KEY

    //empty tree
    if (root == null)
        return root;

    if (key.keyCompareTo(root.data) < 0)
        root.left = delete(root.left, key);
    else if (key.keyCompareTo(root.data) > 0)
        root.right = delete(root.right, key);

    else
    {
        // node with only one child or no child
        if (root.left == null)
            return root.right;
        else if (root.right == null)
            return root.left;

        // node with two children: Get the inorder successor (smallest
        // in the right subtree)
        root.data = getMin(root.right).data;

        // Delete the inorder successor
        root.right = delete(root.right, root.data);
    }

    return root;
}

1 Ответ

0 голосов
/ 01 мая 2018

Предполагая, что ваше дерево не выполняет балансировку, первый вставленный узел будет корневым узлом дерева. Поскольку ваш метод удаления работает путем обновления внутренних ссылок, чтобы они указывали вокруг удаленного узла, попытка удаления корневого узла ничего не изменит, если вы также не обновите указатель на корневой узел.

Трудно сказать по предоставленному вами коду, но вполне вероятно, что вам нужно что-то вроде: 

public void delete(KeyComp key) {
    _root = delete(_root, key);
}
...