バイナリ検索ツリーノード置換が削除されないJava

Question

バイナリ検索ツリーからノードを削除しようとしています。特定の1つのケースを除いて、ツリー上の他のノードを正常に削除できます。ターゲットノードに2つの子があり、左の子に右のサブツリーがある場合は、正しい置換Nodeを見つけて、対象のNodeに値を切り替えることができますが、置換ノードは決して削除されません。私は17を削除しようと

、上の写真を見ると、プログラムが正しく13に移動し、13と17を置き換え、それをすることになっているとして、それはその後、元の13は削除されませんでしょう。

私は削除方法とその中​​で参照されている方法を添付しました。

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

あなたは、交換を見つけて、それにrepポイントを作っている：あなたのコードのこの部分を考えてみましょう

public class Node<T> { 
    public int value; 
    public Node left; 
    public Node right; 
    public Node parent; 

    public Node(int value) { 
     this.value = value; 
    } 
} 

Answer 1

：

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クラスです。次に、基本的にはrepを指してnullとしています。これはノードを削除しません！親はまだそれを指しています！

コードには、これらの行に沿って何かをしている場所がいくつかあります。このJava実装でツリーからノードを削除する方法は、親が指しているものを変更することです。ガベージコレクタは他の詳細を処理します。この問題に対処すると、問題を解決するのに役立ちます。