Удалить рекурсивно из двоичного дерева поиска

Это домашнее задание; пожалуйста, не просто дайте мне код

У меня есть два метода: remove(T data) и removeRec(Node<T> node, T data).

В текущем состоянии кажется, что мой код удаляет только root node BST.

@Override
public T remove(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Data is null");
    }
    if (root == null) {
        throw new java.util.NoSuchElementException("BST is empty");
    } else {
        size--;
        BSTNode<T> dummy = new BSTNode<T>(null);
        return removeRec(root, data, dummy).getData(); //This is probably wrong too
    }
}

/**
 * Helper method to recursively search for, and remove the BSTNode with
 * the given data in it
 * @param  node is the node we're currently at
 * @param  data is the data we're looking for
 * @param  temp I have no idea why
 * @return node that was removed
 */
private BSTNode<T> removeRec(BSTNode<T> node, T data, BSTNode<T> temp) {
    if (compare(data, node.getData()) < 0) {
        temp.setLeft(removeRec(node.getLeft(), data, temp));
    } else if (compare(data, node.getData()) > 0) {
        temp.setRight(removeRec(node.getRight(), data, temp));
    } else if (node.getLeft() != null && node.getRight() != null) {
        temp.setData(findMin(node.getRight()).getData());
        temp.setRight(removeRec(node.getRight(), data, temp));
    } else {
        if (node.getLeft() != null) {
            temp = node.getLeft();
        } else {
            temp = node.getRight();
        }
    }
    return temp;
}

private int compare(T a, T b) {
    return a.compareTo(b);
}

Мой инструктор сказал мне (как подсказку), что я должен увидеть, что в третьем аргументе метод, в данном случае, BSTNode<T> temp. Я не понимаю, как это помогает, или как его использовать. Я не вижу, как помогает использование третьего аргумента; и я не могу найти что-либо в Интернете относительно того, почему вы тоже это сделаете.

Ответы

Ответ 1

При попытке удалить data из вашего дерева двоичного поиска есть три основные возможности:

  • data меньше текущего значения node: Вызов удаляется в левом поддереве или бросает NoSuchElementException, если он равен нулю.
  • data больше, чем текущее значение node: вызывать удаление в правом поддереве или бросать a NoSuchElementException, если оно равно null.
  • data равен текущему значению node.

1 и 2 довольно просты, но 3 имеет еще четыре случая:

3,1. текущий node - это лист. Оба левого и правого поддеревьев равны нулю. Просто замените ссылку на текущий node на родительский на null.

3,2. текущий node имеет только левый дочерний элемент: вам нужно сделать родительский текущего node точкой в ​​левом поддереве, тем самым удалив текущую точку. Для этого вы можете реализовать функцию, которая будет проверять, находилась ли текущая точка в левом или правом поддереве родительский, и замените ее соответствующим образом. Вызов будет выглядеть так:

replaceNodeInParent(node, node.getLeft(), parent);

3.3. текущий node имеет только правильный дочерний: аналогично 3.4, но использует getRight() вместо getLeft().

3.4. текущий node имеет как левый, так и правый дочерние элементы. Вы должны сохранить свойство BST, что все узлы слева меньше текущего node, а все узлы справа больше, чем текущий node. Для этого вы должны найти наименьшее значение справа, скопировать его в текущий node и удалить его из правого поддерева. Что-то вроде этого:

BSTNode<T> successor = findMin(node.getRight());
node.setData(successor.getData());
removeRec(node.getRight(), successor.getData(), node);

Похоже, ваш BSTNode не содержит ссылку на родительский node. Если это так, я считаю, что должен быть третий аргумент для removeRec. Вам понадобится ссылка на родительский при каждом замене текущего node, поэтому вы можете установить родительское левое или правое поддерево по мере необходимости.

Для дальнейшего чтения вы можете проверить эту статью статью о деревьях двоичного поиска из Википедии.