이진 검색 트리에서 노드 삭제

Question

사전과 같은 단어를 저장하는 이진 검색 트리에서 노드를 삭제하려고합니다. DictEntry 요소는 단어, 정의 및 표시 할 정의 유형 (문자열, 이미지 등)에 대한 숫자를 포함합니다. 단어가 발견되지 않으면 DictionaryException이 throw됩니다.

사용자는 방법으로 단어를 입력하여 항목을 삭제할 수 있어야합니다. 다음은 제거에 사용되는 메소드입니다.

public void remove(String word) throws DictionaryException { 
    if (root!=null) { 
     //checks if the word is equal to the entrie's word 
     if (word.equals(root.getElement().word())) 
      root = replacement(root); 
     else { 
      // parent is the node above current 
      BinaryTreeNode<DictEntry> current, parent = root; 
      boolean found = false; 
      // if lexicographically smaller than the root's word 
      if (word.compareTo(root.getElement().word()) < 0) 
       current = root.getLeft(); 
      // if lexicographically higher than the root's word 
      else 
       current = root.getRight(); 
      while (current != null && !found) { 
       if (word.equals(current.getElement().word())) { 
        found = true; 
        if (current == current.getLeft()) 
         parent.setLeft(replacement(current)); 
        else 
         parent.setRight(replacement(current)); 
       } else { 
        parent = current; 

        if (word.compareToIgnoreCase(current.getElement() 
          .word()) < 0) 
         current = current.getLeft(); 
        else 
         current = current.getRight(); 
       }// end if else 
      }// end while 
      if (!found) 
       throw new DictionaryException("The entry was not found"); 
     } 
    } 
} 

private BinaryTreeNode<DictEntry> replacement(BinaryTreeNode<DictEntry> node) { 
    BinaryTreeNode<DictEntry> found = null; 
    // check if both sides are empty 
    if (node.getLeft() == null && node.getRight() == null) 
     found = null; 
    else if (node.getLeft() != null && node.getRight() == null) 
     found = node.getLeft(); 
    else if (node.getLeft() == null && node.getRight() != null) 
     found = node.getRight(); 
    // if both sides have an entry 
    else { 
     //helper positions 
     BinaryTreeNode<DictEntry> current = node.getRight(); 
     BinaryTreeNode<DictEntry> parent = node; 

     //moving positions 
     while (current.getLeft() != null) { 
      parent = current; 
      current = current.getLeft(); 
     }// end while 

     if (node.getRight() == current) 
      current.setLeft(node.getLeft()); 
     else { 
      parent.setLeft(current.getRight()); 
      current.setRight(node.getRight()); 
      current.setLeft(node.getLeft()); 
     } 
     found = current; 
    }// end if else 
    return found; 
} 

제 문제는 사전 테스트가 BinarySearchTree를 나타 내기 위해 시도 할 때마다 노드가 제거되지 않는다는 것입니다.

// Insert and remove a word 
try { 
    dictionary.insert("course","A series of talks or lessons",1); 
    dictionary.remove("course"); 
    res = dictionary.findWord("course"); 
    if (res == "") {System.out.println("Remove test passed");} 
    else {System.out.println("Remove test failed");} 
} 
catch(DictionaryException e) { 
    System.out.println("Remove test 4 failed"); 
} 

나는 삽입 방법을 사용하여 게임을 시도했지만 아무런 문제가 없으므로 문제가 제거 논리에 어딘가에 있다고 가정합니다.

Answer 1

초기 모양에서 대체 방법은 == 연산자를 사용하여 노드 비교를 수행합니다. 이것은 노드의 메모리 주소 만 비교합니다. 노드의 값에 따라 비교를 수행하려면 .equals() 메소드를 사용해야합니다.