BST 노드 삭제 혼란 [JaVa]

Question

JaVa에서 이진 검색 트리를 만들었습니다. 불행히도 '삭제'기능이 작동하지 않습니다. 좀 봐 주시면 정말 감사하겠습니다. 미리 감사드립니다.

문제점 : 노드를 삭제 한 후 트리를 inorder로 인쇄 할 수 없습니다.

노드 :

class Node { 

//Properties 
private Node left, right, parent; 
private int key; 

//Getters and Setters 
public Node(int key) { 
    this.key = key; 
} 

public int getKey() { 
    return key; 
} 

public void setKey(int key) { 
    this.key = key; 
} 

public Node getLeft() { 
    return left; 
} 

public void setLeft(Node left) { 
    this.left = left; 
} 

public Node getRight() { 
    return right; 
} 

public void setRight(Node right) { 
    this.right = right; 
} 

public Node getParent() { 
    return parent; 
} 

public void setParent(Node parent) { 
    this.parent = parent; 
} 

} 

이진 검색 트리 :

public class BinarySearchTree { 

//Properties 
private Node root; 

//Getters and Setters 
Node getRoot() { 
    return root; 
} 

public void setRoot(Node root) { 
    this.root = root; 
} 

//Search Method 
public Node search(Node x, int k){ 
    if (x == null || k==x.getKey()){ 
     return x; 
    } 
    if (k<x.getKey()){ 
     return search(x.getLeft(), k); 
    } 
    else{ 
     return search(x.getRight(), k); 
    } 
} 

//Insertion Method 
public void insert(Node z) { 
    Node y = null; 
    Node x = getRoot(); 
    while (x != null) { 
     y = x; 
     if (z.getKey() < x.getKey()) { 
      x = x.getLeft(); 
     } else { 
      x = x.getRight(); 
     } 
    } 
    z.setParent(y); 
    if (y == null) { 
     setRoot(z); 
    } else if (z.getKey() < y.getKey()) { 
     y.setLeft(z); 
    } else { 
     y.setRight(z); 
    } 

} 

//Printer Method 
public void inorder(Node x) { 

    if (x != null) { 
     inorder(x.getLeft()); 
     System.out.print(x.getKey() + " "); 
     inorder(x.getRight()); 
    } 
} 

//Transplant Method 
public void transplant(Node u, Node v){ 
    if (u.getParent() == null){ 
     setRoot(v); 
    } 
    else if (u==u.getParent().getLeft()){ 
     u.getParent().setLeft(v); 
    } 
    else{ 
     u.getParent().setRight(v); 
    } 
    if (v!=null){ 
     v.setParent(u.getParent()); 
    } 
} 

//Deletion Method 
public void delete(Node x) { 
     if (x.getLeft() == null) { 
      transplant(x, x.getRight()); 
     } else if (x.getRight() == null) { 
      transplant(x, x.getLeft()); 
     } else { 
      Node y = minimum(x.getRight()); 
      if (y.getParent() != x) { 
       transplant(y, y.getRight()); 
       y.setRight(x.getRight()); 
       y.getRight().setParent(y); 
      } 
      transplant(x, y); 
      y.setLeft(x.getLeft()); 
      y.getLeft().setParent(y); 
     } 
    } 

//Maximum Finder 
public Node maximum(Node x) { 
    while (x.getRight() != null) { 
     x = x.getRight(); 
    } 
    return x; 
} 

//Minimum Finder 
public Node minimum(Node x) { 
    while (x.getLeft() != null) { 
     x = x.getLeft(); 
    } 
    return x; 
} 

//Example Tree Constructor 
public void createBST(int[] a){ 

    for (int i=0; i<a.length; i++){ 
     Node nodeToBeAdded = new Node(a[i]); 
     insert(nodeToBeAdded); 
    } 
    inorder(root); 
} 

} 

및 테스트 클래스 :

public class Test { 

public static void main(String[] args) { 

    //CREATION 
    System.out.println("CREATION"); 
    BinarySearchTree tree = new BinarySearchTree(); 

    int[] a = {54, 32, 76, 7, 44, 63, 99}; 

    tree.createBST(a); 

    System.out.println(); 
    System.out.print("The root of the tree is: "); 
    System.out.println(); 

    System.out.print("Maximum Node is: "); 
    tree.inorder(tree.maximum(tree.getRoot())); 
    System.out.println(); 

    System.out.print("Minimum Node is: "); 
    tree.inorder(tree.minimum(tree.getRoot())); 
    System.out.println(); 


    //INSERTION 
    System.out.println("INSERTION"); 
    tree.insert(new Node(25)); 
    tree.inorder(tree.getRoot()); 

    tree.insert(new Node(485)); 
    System.out.println(); 
    tree.inorder(tree.getRoot()); 

    tree.insert(new Node(12)); 
    System.out.println(); 
    tree.inorder(tree.getRoot()); 

    tree.insert(new Node(5)); 
    System.out.println(); 
    tree.inorder(tree.getRoot()); 

    tree.insert(new Node(9985)); 
    System.out.println(); 
    tree.inorder(tree.getRoot()); 

    System.out.println(); 
    System.out.print("Maximum Node is: "); 
    tree.inorder(tree.maximum(tree.getRoot())); 
    System.out.println(); 

    System.out.print("Minimum Node is: "); 
    tree.inorder(tree.minimum(tree.getRoot())); 
    System.out.println(); 

    //SEARCH 
    System.out.println("SEARCH"); 
    tree.inorder(tree.search(tree.getRoot(), 32)); 
    System.out.println(); 


    //DELETION 
    System.out.println("DELETION"); 
    tree.delete(new Node(5)); 
    tree.inorder(tree.getRoot()); 
} 

} 

Answer 1

새로운 인스턴스를 만들었으므로 Node (5)를 찾을 수 없으므로 equals/hashCode 메서드를 재정의하지 않습니다. 당신이 Test.java에서 코드를 변경하는 경우 :

tree.insert(new Node(12)); 
System.out.println(); 
tree.inorder(tree.getRoot()); 
// Start changes 
Node node5 = new Node(5); 
tree.insert(node5); 
System.out.println(); 
tree.inorder(tree.getRoot()); 
// End changes 
tree.insert(new Node(9985)); 
// -cut some code 
//DELETION 
System.out.println("DELETION"); 
tree.delete(node5); 
System.out.println(); 
tree.inorder(tree.getRoot()); 

이