Дерево двоичного поиска Node Удаление, не удаляющее замену Java

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

Если посмотреть на картинку выше, если я попытаюсь удалить 17, программа будет правильно перемещаться к 13 и заменить 17 на 13, но она не удалит исходный 13, как предполагается.

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

public Node root; 
 public void delete(int value){
 Node node = new Node<>(value);
 Node temp;
 if(root == null) {
 System.out.println("The tree is already empty!"); //tree is empty
 return; 
 }
 if (root.value == node.value) { //Root is target value
 temp = node.left;
 if(temp.right == null){
 node.value = temp.value;
 temp = null;
 }
 else{
 while(temp.right != null){
 temp = temp.right;
 }
 node.value = temp.value;
 temp = null;
 }
 return;
 }
 deleteRec(root, node);
}
private void deleteRec(Node lastRoot, Node node){
 Node temp;
 if (lastRoot.value >= node.value){
 if (lastRoot.left.value == node.value){
 node = lastRoot.left;
 if(node.left == null && node.right == null){ //No children
 node = null;
 lastRoot.left = null;
 }
 else if(node.left == null && node.right != null){ //Right Child
 lastRoot.left = node.right;
 node = null;
 lastRoot.left = null;
 }
 else if(node.left != null && node.right == null){ //Left Child
 lastRoot.left = node.left;
 node = null;
 }
 else{ //Two Children
 if(node.left.right == null){
 node.value = node.left.value;
 node.left = node.left.left;
 node.left = null;
 }
 else{
 node = findReplacement(node.left);
 lastRoot.left.value = node.value;
 node.left = null;
 }
 }
 }
 else{
 deleteRec(lastRoot.left, node);
 }
 }
 else{
 if (lastRoot.right.value == node.value){
 node = lastRoot.right;
 if(node.left == null && node.right == null){ //No Children
 node = null;
 lastRoot.right = null;
 }
 else if(node.left == null && node.right != null){ //Right Child
 lastRoot.left = node.right;
 node = null;
 lastRoot.right = null;
 }
 else if(node.left != null && node.right == null){ //Left Child
 lastRoot.right = node.left;
 node = null;
 }
 else{ //Two Children
 if(node.left.right == null){
 node.value = node.left.value;
 node.left = node.left.left;
 node.left = null;
 }
 else{
 node = findReplacement(node.left);
 lastRoot.left.value = node.value;
 node.left = null;
 }
 }
 }
 else{
 deleteRec(lastRoot.right, node);
 }
 }
}
private Node findReplacement(Node node) {
 while(node.right != null){
 node = node.right;
 } 
 return node;
}

И вот мой класс node:

public class Node<t> {
 public int value;
 public Node left;
 public Node right;
 public Node parent;
 public Node(int value) {
 this.value = value;
 }
}
</t>
1 ответ

Рассмотрим эту часть вашего кода:

Node rep = findReplacement(node.left);
node.value = rep.value;
rep = null;

Вы находите замену и указываете на нее rep. Тогда, по существу, вы делаете rep на null. Это не удаляет node! Родитель все еще указывает на это!

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

licensed under cc by-sa 3.0 with attribution.