이진 트리 병합 재귀 구현 병합으로 삭제

Question

병합에 의한 삭제의 반복 버전을 구현했지만 재귀 적으로 구현하는 데 어려움을 겪고 있습니다.

public void deleteByMerging(T el) { 
    BSTNode<T> tmp, node, p = root, prev = null; 
    while (p != null && !p.el.equals(el)) { 
     prev = p;       
     if (el.compareTo(p.el) < 0) 
       p = p.right; 
     else p = p.left; 
    } 
    node = p; 
    if (p != null && p.el.equals(el)) { 
     if (node.right == null) 
       node = node.left; 
     else if (node.left == null) 
       node = node.right; 
     else {     
       tmp = node.left; 
       while (tmp.right != null) 
        tmp = tmp.right;  
       tmp.right =   
        node.right;  

       node = node.left; 
     } 
     if (p == root) 
       root = node; 
     else if (prev.left == p) 
       prev.left = node; 
     else prev.right = node; // 5. 
    } 
    else if (root != null) 
     System.out.println("el " + el + " is not in the tree"); 
    else System.out.println("the tree is empty"); 
} 

지금 내가 이런 식으로 재귀 함수 구현해야합니다 :

이 내 반복 버전입니다 재귀

public void delete(T info) { 
    root = delete(root, info); 
} 

public TreeNode<T> delete(TreeNode<T> node, T info) 
    { 

    } 

임 아주 새로운을 내가 시작하는 위치의 아무 생각이 없다 .

Answer 1

(기준은 "당신의"반복 버전은 물론 당신은 아담 드로즈 덱의를 의미한다.)

이 작동합니다 : node가 null의 경우

public void delete(T info) { 
    root = delete (root.info); 
} 

public TreeNode<T> delete(TreeNode<T> node, T info) { 

    // if this node is null, we have reached the end of the tree 
    // so the node is not in the tree. 
    if (node == null) { 
     return node; // or handle as required 

    // if this is not the node to delete; 
    // recursively call this on the node's correct child 
    else if (info.compareTo(node.info) <0) { 
     node.left = delete(node.left, info); 
     return node; 
    } else { 
     node.right = delete(node.right, info); 
     return node; 
    } 

    // if this is the node to delete: 
    else if (node.info.equals(info)) { 
     // to delete it, we must return a sub-tree without it. 

     if (node.left == null) 
      // this node is a leaf node, or 
      // node.right contains only child. 
      // either way, return node.right 
      return node.right; 

     if (node.right == null) 
      // node.left contains only child 
      return node.left; 

     // else node has 2 children, so delete by merging: 
     // first, find its direct predecessor: 
     TreeNode<T> tmp = node.left; 
     while (tmp.right != null) 
      tmp = tmp.right; 
     // then append the node's right sub-tree 
     // to its direct predecessor: 
     tmp.right = node.right; 
     // lastly, replace the node by its left sub-tree: 
     return node.left; 
    } 
} 

먼저 우리는 확인한다. 그것이 존재한다면, 그것은 우리가 삭제할 요소가 트리에 없다는 것을 의미합니다. 왜냐하면 우리는 그것이있을 수있는 모든 노드를 다 쓸 때까지 통과했기 때문입니다.

다음으로 요소가 현재 노드의 요소보다 크거나 큰지 확인합니다. 그렇다면 요소를 비교하는 방법에 따라 왼쪽 또는 오른쪽으로 이동하여 트리를 계속 탐색해야합니다. 재귀 적 단계에서는 삭제 작업의 결과를 node의 자식 중 하나에 할당합니다. 우리는 root에서 삭제 작업의 결과가 할당 된 root 인 첫 번째 함수에서이 큐를 가져 왔습니다. 이 노드는 삭제하려는 노드를 나타내는 node이 나타날 때까지 반복적으로 트리를 통과합니다. 여기서도 node을 반환하므로 변경 사항이 발생하지 않은 경우 node.right = delete(node.right, info)을 호출해도 현재 노드가 변경되지 않습니다.

노드를 찾으면 노드가 리프 노드 (자식이 없음)이거나 왼쪽 또는 오른쪽 자식이 1 개이거나 자식이 두 개있을 수 있습니다. 처음 3 개 시나리오 node에 아이가없는 경우는 (널) node의 권리 아이가 반환됩니다, 그래서 첫 번째 if 검사 노드를 삭제, 사실 일 것이다

if (node.left == null) 
    return node.right; 
if (node.right == null) 
    return node.left; 

주 라인이 적용됩니다 .

null을 반환하는 이유는 노드를 삭제하는 이유는 무엇입니까? 위에 설명 된 탐색 단계에서 우리는 삭제 작업의 결과를 node의 자식에게 할당하기 때문에. 이전 재귀 단계의 node은이 단계에서 node의 부모입니다. delete가 해당 노드의 하위 노드에서 반복적으로 호출 되었기 때문입니다. 여기서 null을 반환하면 이전 호출에서 부모의 자식에 null을 할당하여 자식을 삭제합니다. 기본적으로 node이 아닌 다른 값을 반환 할 때마다 트리에서 반환하는 값으로 현재 노드를 교체합니다.

네 번째 경우에는 병합을 통해 간단한 삭제가 필요합니다. 왼쪽 하위 트리의 가장 오른쪽 노드에 node의 오른쪽 하위 트리를 추가하여이 작업을 수행 할 수 있습니다.

TreeNode<T> tmp = node.left; 
while (tmp.right != null) 
    tmp = tmp.right; 

그래서 tmp 지금 node의 직접적인 전신 : 첫째, 우리는 node의 직접적인 전신 왼쪽 서브 트리에서 가장 오른쪽 노드를 찾을 수 있습니다.다음으로 우리가 tmp에 node의 바로 하위 트리를 래치 : 그것의 왼쪽 서브 트리로 node을 대체 할 마지막

tmp.right = node.right; 

와,이 node의 자식으로 node.left와 node을 대체하기 때문에, 우리는 단순히, node.left을 반환 이전 재귀 호출의 부모.

제 설명이 혼란 스럽다면 this one을 사용해보십시오. 이것은 종이 위에 그림으로 설명하기가 훨씬 쉽습니다. 그래서 실용적인 세션 (네, 저는이 prac을 세웠습니다)보다는 나에게 물어봐야 할 것입니다. 마감일 전에 알아 냈 으면합니다!