이진 검색 트리 제거 방법

Question

String 키로 정렬 된 이진 검색 트리를 만들고 있습니다. 각 노드는 키와 연관된 정보의 연결되지 않은 링크 목록으로 구성됩니다. 나무는 inorder (알파벳 순서)입니다.

대부분의 프로그램을 완료했지만 제거 방법에 문제가 있습니다.

본질적으로 재귀 적이어야합니다. 메서드는 지정된 키를 가진 노드를 제거해야합니다. 예를 들어 "Architecture"가 지정된 문자열이면 트리를 탐색하여 "Architecture"를 키로 사용하여 해당 노드를 제거해야합니다.

문자열을 제거해야하기 때문에 문제가 있습니다. 다른 과제는 가장 높은 값이나 가장 낮은 값을 제거해야하는 정수를 사용했습니다. 그러나 가장 높은 또는 가장 낮은 String 값을 가진 노드는 제거하지 않고 지정된 String과 동일한 노드를 제거합니다.

저는이 방법에 대해 어떻게 생각하는지 묻습니다. 선택하지 않으면 실제 코드를 제공 할 필요가 없지만 일부 포인터 나 조언은 유용 할 것입니다.

감사합니다.

//My attempt: 
//Removes node with corresponding k 
public void remove(String k) { 
    rootNode = remove(rootNode, k); 
} 

//Recursive method: 
private KeyNode remove(KeyNode x, String k) { 
    if (x == null) { 
     return x; 
    } 
    //int comparison with compareTo 
    //if less than 0, left node = remove(left node, k) 
    //if greater than 0, right node = remove(right node, k) 
    //if left node and right node are both null, return null 
    //if left node is null, return left node 
    //if right node is null, return right node 
    //return 
} 

Answer 1

이

public rootNode remove (String k, rootNode n) { 
    if (n == null) 
     return null; 

    if (k.compareTo(n.key)<0) 
     remove (k, n.leftChild); 
    else if (k.compareTo(n.key)>0) 
     remove (k, n.rightChild); 
    else { 
     if (n.leftChild != null && n.rightChild != null) { 
      /* n has two children, find max from left then 
      * switch it with n and remove n */ 

     } 
     else if(n.leftChild != null) { 
      /* n has a left child only then left child replaces n 
      * and n is deleted */ 


     } 
     else if(n.rightChild != null) { 
      /* n has a right child only then right child replaces n 
      * and n is deleted*/ 

     } 
     else { 
      n = null; 
     } 
    } 

}