이진 검색 트리 찾기 및 제거 [C++]

Question

현재 재귀를 사용하여 수행중인 찾기 및 제거 기능을 수정하려고합니다. 그러나 케이스 2가 끝나면 케이스 0 또는 케이스 1로 연결되는지 식별하는 방법에 대해 문제가 있습니다.

다음은 내가 수행하려고 시도하는 간단한 설명입니다. 사례 2 (두 자녀) - 오른쪽 하위 트리를 최소로 바꾸면 대소 문자가 구분됩니다. the algorithm에 따르면

bool findAndRemove(const Type& v) 
{ 
    return findAndRemove(root, nullptr, v); 
} 

bool findAndRemove(Node<Type> *fr, Node<Type> *parent, const Type& v) const 
{ 
    if (fr == nullptr) 
    { 
     return true; 
    } 

    if (v < fr->element) 
    { 
     return findAndRemove(fr->left, fr, v); 
    } 
    else if (v > fr->element) 
    { 
     return findAndRemove(fr->right, fr, v); 
    } 
    else 
    { 
     switch (GetChildren(fr)) 
     { 
     case 0: 
      if (parent->left == fr) 
      { 
       parent->left = nullptr; 
       delete fr; 
      } 
      else 
      { 
       parent->right = nullptr; 
       delete fr; 
      } 
      break; 
     case 1: 
      if (parent->left == fr) 
      { 
       if (fr->left != nullptr) 
       { 
        parent->left = fr->left; 
        delete fr; 
       } 
       else 
       { 
        parent->left = fr->right; 
       } 

      } 
      else 
      { 
       if (fr->right != nullptr) 
       { 
        parent->right = fr->right; 
        delete fr; 
       } 
       else 
       { 
        parent->right = fr->left; 
       } 
      } 
      break; 
     case 2: 
     { 
      Node<Type> * swap = fr->right; 
      while (swap->left != nullptr) 
      { 
       swap = swap->left; 
      } 

      Type temp = fr->element; // 30 
      temp = swap->element; // 35 
      swap->element = fr->element; // 30 
      fr->element = temp; 

      //temp = swap->element; 
      //swap->element = temp; 
      //temp = fr->element; 
      break; 
     } 
     } 
    } 
    return false; 
} 

Answer 1

:

• 오른쪽 하위 트리에 최소 값을 찾을 수 있습니다;
• 제거 할 노드의 값을 발견 된 최소값으로 바꿉니다. 자, 오른쪽 하위 트리에 중복이 들어 있습니다!
• 중복을 제거하려면 오른쪽 하위 트리에 remove를 적용하십시오. swap 점을 그 권리 서브 트리의 최소 노드 코드에서

, 그래서 당신은이 노드에 findAndRemove 함수를 호출하는 경우, 당신은 간단하게 제거 할 수 있습니다.

{ 
    // STEP 1: find a minimum value in the right subtree; 
    Node<Type> * swap = fr->right; 
    while (swap->left != nullptr) 
    { 
     swap = swap->left; 
    } 

    // STEP 2: replace value of the node to be removed with found minimum. 
    fr->element = swap->element; 

    // STEP 3: apply remove to the right subtree to remove a duplicate. 
    // Here you should call 'findAndRemove' on 'swap' node 
    break; 
}