рекурсивное двоичное дерево поиска удаляет метод

Question

Прежде всего, это домашнее задание, поэтому ставим его там.

Я должен реализовать бинарное дерево поиска с конкретными методами:

недействительной вставки (String), логические удалить (String), и логические найти (String).

Я смог успешно запрограммировать и протестировать методы вставки и поиска, но у меня возникли трудности с удалением.

Что происходит в моей программе, это удаление на самом деле ничего не удаляет из дерева, и я считаю, что это связано с тем, что он ссылается только на локальное создание текущего узла, но я могу ошибаться. Я думаю, что могу реализовать логику различных случаев, которые мне нужны для тестирования (может потребоваться помощь при удалении узла с двумя детьми, но я думаю, что я понимаю его). В основном я пытаюсь понять, что мне нужно сделать по-другому, чтобы ссылаться на дерево должным образом в

current = null; // case 

Вот что я получил до сих пор:

public boolean remove(String title) 
{ 
    return remove(root, title); 
} 
private boolean remove(BSTNode current, String title) 
{ 
    if (current == null) 
    { 
     return false; 
    } 
    if (current.data == title) 
    { 
    if (current.left_child !=null && current.right_child != null) 
    { 
     return true; // returning true since I haven't finished writing this case 
    } 
    else if (current.left_child == null && current.right_child == null) 
     { 
     current = null; // this should remove the node from tree but it doesn't 
     return true; 
    } 

    else if (current.left_child != null && current.right_child == null) 
    { 
     current = current.left_child; // don't think this is right 
     return true; 
    } 
    else if (current.right_child != null && current.left_child == null) 
    { 
     current = current.right_child; // not sure about this 
     return true; 
    } 

    } 
root = current; 
if (title.compareToIgnoreCase(current.data) == -1) 
{ 
    return remove(current.left_child, title); 
} 
    else 
{ 
    return remove(current.right_child, title); 
} 
} 

Любое знание очень ценится.

Answer 1

Узел ссылается на его родительский объект (за исключением корня, на этот узел ссылается ваш BST). Чтобы удалить узел из дерева, вам нужно установить эту ссылку в родительском узле на null.

Что вы пытаетесь делать что-то вроде:

Before: 
parent.left ---> node <--- current 

After setting current = null: 
parent.left ---> node  current ---> null 

что, в настоящее время ссылки null, но это не меняет родителя (только что локальная переменная).

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

К слову: никогда, никогда сравнить строки с ==, см., Например, this question.

---

Как найти узел и его родитель без явно хранения родителя в каждом узле:

Я бы сказал, что это проще сделать это в цикле, а не с помощью рекурсии, но как должно сработать. В цикле:

BSTNode parent = null; 
BSTNode current = root; 
boolean found = false; 
while (!found && current != null) { 
    int compare = title.compareToIgnoreCase(current.data); 
    if (compare == 0) { 
     found = true; 
    } else { 
     parent = current; 
     if (compare < 0) { 
      current = current.left; 
     } else { 
      current = current.right; 
     } 
    } 
} 
if (!found) { 
    // title was not found 
} else if (parent == null) { 
    // found the root 
} else { 
    // found another node 
} 

Рекурсией это раздражает, потому что вы хотите метод, который возвращает как узел и его родителей. Для этого вам понадобится простой внутренний класс:

private class NodeAndParent { 
    public BSTNode node; 
    public BSTNode parent; 
    public NodeAndParent(BSTNode node, BSTNode parent) { 
     this.node = node; 
     this.parent = parent; 
    } 
} 

private boolean find(String title, NodeAndParent current) { 
    if (current.node == null) { 
     return false; // not found 
    } else { 
     int compare = title.compareToIgnoreCase(current.node.data); 
     if (compare == 0) { 
      return true; // found 
     } else { 
      current.parent = current.node; 
      if (compare < 0) { 
       current.node = current.node.left; 
      } else { 
       current.node = current.node.right; 
      } 
     } 
    } 
} 

private boolean remove(String title) { 
    NodeAndParent nodeAndParent = new NodeAndParent(root, null); 
    boolean found = find(title, nodeAndParent); 
    if (!found) { 
     // title was not found 
    } else if (nodeAndParent.parent == null) { 
     // found the root 
    } else { 
     // found another node 
    } 
}