재귀적인 이진 탐색 트리 제거 방법

Question

우선, 이것은 숙제이므로, 거기에 두는 것입니다.

무효 삽입 (문자열), 부울 제거 (문자열), 및 부울 발견 (문자열) :

가 나는 구체적인 방법과 이진 검색 트리를 구현하기로하고 있습니다.

삽입 프로그램을 테스트하고 테스트 할 수 있었지만 제거 방법에 어려움이 있습니다.

내 프로그램에서 벌어지는 일은 제거가 실제로 트리에서 아무 것도 제거하지 않는 것이고 현재 노드의 로컬 생성을 참조하고 있지만 잘못되었을 수 있기 때문입니다. 테스트 할 필요가있는 여러 사례의 논리를 구현할 수 있다고 생각합니다 (두 명의 자녀가있는 노드를 삭제하는 데 도움이 필요할 수 있지만 개념적으로 생각합니다). 주로 참조 할 때 무엇을해야하는지 이해하려고합니다. 나무가 제대로 여기

current = null; // case 

에서 내가 지금까지 무엇을 가지고 있습니다 :

public boolean remove(String title) 
{ 
    return remove(root, title); 
} 
private boolean remove(BSTNode current, String title) 
{ 
    if (current == null) 
    { 
     return false; 
    } 
    if (current.data == title) 
    { 
    if (current.left_child !=null && current.right_child != null) 
    { 
     return true; // returning true since I haven't finished writing this case 
    } 
    else if (current.left_child == null && current.right_child == null) 
     { 
     current = null; // this should remove the node from tree but it doesn't 
     return true; 
    } 

    else if (current.left_child != null && current.right_child == null) 
    { 
     current = current.left_child; // don't think this is right 
     return true; 
    } 
    else if (current.right_child != null && current.left_child == null) 
    { 
     current = current.right_child; // not sure about this 
     return true; 
    } 

    } 
root = current; 
if (title.compareToIgnoreCase(current.data) == -1) 
{ 
    return remove(current.left_child, title); 
} 
    else 
{ 
    return remove(current.right_child, title); 
} 
} 

모든 지식을 많이 감사합니다.

Answer 1

노드가 상위 노드에 의해 참조됩니다 (루트 노드 제외). 노드는 BST 자체에서 참조됩니다. 트리에서 노드를 제거하려면 상위 노드의 해당 참조를 null으로 설정해야합니다. 당신은 지금 뭘 하려는지

은 같은 것입니다 :

, 현재 참조 null이지만, 그 부모 (해당 지역 변수)를 변경하지 않습니다

Before: 
parent.left ---> node <--- current 

After setting current = null: 
parent.left ---> node  current ---> null 

.

제거 방법에서 부모를 함께 전달해야합니다 (또는 부모와 통화 할 때 두 자녀를 모두 처리하는 것이 더 좋음).

덧붙여서 절대은 ==과 문자열을 비교합니다 (예 : this question 참조).

---

어떻게 노드를 찾을 수 있으며 명시 적으로 각 노드에 부모를 저장하지 않고 부모 입니다 :

나는 오히려 재귀보다, 루프에서이 작업을 수행하는 것이 더 간단하다 말할 것입니다,하지만 모두 작동 할 것이다. 루프 있음 :

BSTNode parent = null; 
BSTNode current = root; 
boolean found = false; 
while (!found && current != null) { 
    int compare = title.compareToIgnoreCase(current.data); 
    if (compare == 0) { 
     found = true; 
    } else { 
     parent = current; 
     if (compare < 0) { 
      current = current.left; 
     } else { 
      current = current.right; 
     } 
    } 
} 
if (!found) { 
    // title was not found 
} else if (parent == null) { 
    // found the root 
} else { 
    // found another node 
} 

재귀를 사용하면 노드와 그 부모를 모두 반환하는 메서드가 필요하므로 짜증나게됩니다. 이 문제를 해결하기 위해 간단한 내부 클래스가 필요합니다.

private class NodeAndParent { 
    public BSTNode node; 
    public BSTNode parent; 
    public NodeAndParent(BSTNode node, BSTNode parent) { 
     this.node = node; 
     this.parent = parent; 
    } 
} 

private boolean find(String title, NodeAndParent current) { 
    if (current.node == null) { 
     return false; // not found 
    } else { 
     int compare = title.compareToIgnoreCase(current.node.data); 
     if (compare == 0) { 
      return true; // found 
     } else { 
      current.parent = current.node; 
      if (compare < 0) { 
       current.node = current.node.left; 
      } else { 
       current.node = current.node.right; 
      } 
     } 
    } 
} 

private boolean remove(String title) { 
    NodeAndParent nodeAndParent = new NodeAndParent(root, null); 
    boolean found = find(title, nodeAndParent); 
    if (!found) { 
     // title was not found 
    } else if (nodeAndParent.parent == null) { 
     // found the root 
    } else { 
     // found another node 
    } 
}