자바의 BinarySearchTree에서 메소드 추가 및 삭제

Question

좋아, 전화 번호부에 BinarySearchTree가있는 DictionaryADT 인터페이스를 구현하고 있습니다. BST 추가 및 삭제를 제외하고 내 파일이 제대로 작동합니다. 중복 된 항목을 추가 할 수 없지만 트리가 중복되어 추가 할 수 없으며 그 이유는 알 수 없습니다. 마찬가지로 삭제할 때 내 삭제 된 항목이 테스트 파일에서 발견되므로 삭제가 전혀 작동하지 않는다고 생각합니다! 내 방법은 다음과 같습니다. 어떤 도움이라도 대단히 감사합니다.

public boolean add(K key, V value) { 

    if (root == null) 
     root = new Node<K, V>(key, value); 
    else 
     insert(key, value, root, null, false); 
    currentSize++; 
    modCounter++; 
    return true; 

} 

private void insert(K k, V v, Node<K, V> n, Node<K, V> parent, boolean wasLeft) 
{ 
    if (n == null) { 
     if (wasLeft) 
      parent.leftChild = new Node<K, V>(k, v); 
     else 
      parent.rightChild = new Node<K, V>(k, v); 
    } 
    else if (((Comparable<K>) k).compareTo((K) n.key) < 0) 
     insert(k, v, n.leftChild, n, true); 
    else 
     insert(k, v, n.rightChild, n, false); 
} 

여기가 내 삭제 :

public boolean delete(K key){ 
     if (!this.contains(key)) { 
      return false; 
    } 

    Node<K, V> node = find(key, root, 0); 
    Node<K,V> parent = remove(node, root); 
    root=parent; 
    currentSize--; 
    modCounter++; 

    return true; 
} 


private Node<K,V> remove(Node<K,V> node_to_delete, Node<K,V> start_node) 
{ 
    if(start_node == null) 
     return start_node; 
    if(((Comparable<K>)node_to_delete.key).compareTo(start_node.key) < 0) 
     start_node.leftChild = remove(node_to_delete, start_node.leftChild); 
    else if(((Comparable<K>)node_to_delete.key).compareTo(start_node.key) > 0) 
     start_node.rightChild = remove(node_to_delete, start_node.rightChild); 
    else if(start_node.leftChild != null && start_node.rightChild != null) 
    { 
     start_node.key = findMin(start_node.rightChild).key; 
     start_node.rightChild = remove(start_node, start_node.rightChild); 
    } 
    else 
     start_node = (start_node.leftChild != null) ? start_node.leftChild : start_node.rightChild; 
    return start_node; 
} 

private Node<K,V> findMin(Node<K,V> t) 
{ 
    if(t == null) 
     return null; 
    else if(t.leftChild == null) 
     return t; 
    return findMin(t.leftChild); 
} 

Answer 1

수표가 insert에서 불완전 :

else if (((Comparable<K>) k).compareTo((K) n.key) < 0) 
    insert(k, v, n.leftChild, n, true); 
else 
    insert(k, v, n.rightChild, n, false); 

비교의 결과가 0 일 경우에, 당신은 이미 가치가 발생했습니다 이 시점에서 당신은 새로운 가치를 버려야합니다.

insert은 다음과 같이해야한다 :

private void insert(K k, V v, Node<K, V> n, Node<K, V> parent, boolean wasLeft) 
{ 
    if (n == null) { 
     if (wasLeft) 
      parent.leftChild = new Node<K, V>(k, v); 
     else 
      parent.rightChild = new Node<K, V>(k, v); 
    } 
    else { 
     int result = ((Comparable<K>) k).compareTo((K) n.key); 
     if (result < 0) 
      insert(k, v, n.leftChild, n, true); 
     else if(result > 0) 
      insert(k, v, n.rightChild, n, false); 
     //else: discard the data, it's a duplicate! 
    } 
} 

Answer 2

가 좋아, 지금 내 파일이 잘 실행, 더 중복이 추가되지도 잘 작동 삭제 ...하지만! 전화 번호부에서 번호를 인쇄 할 때 BST가 특정 정렬 된 순서로 번호를 제공해야합니다. 그렇지 않습니까? 내 번호 (키) 무작위가 아니라 특정 순서에 왜 .. 여기

내가 내 add 메소드에 추가 무슨 ... 내 경우와

Node<K,V> newNode = new Node<K,V>(key,value); 
    if(contains(key)) 
     return false; 

을 발생하지 그게 이해가 안 돼요 .