再帰を使用してバイナリ検索ツリー内のノードを削除する方法

Question

現在、ノードに検索対象のコンテンツが含まれている場合、バイナリ検索ツリー内のノードを削除するための削除関数を作成しようとしています。私はコンテンツの検索を行い、見つかったかどうかによって真偽を返す関数のスケルトンを書いています。問題は、自分の関数の実際の削除部分をどのように実装するのか分からないということです。ルートノードに私が探している値が含まれている場合、削除後に古いルートの子の1つをルート位置に割り当てる方法がわかりません。また、ノードの削除後に子ポインタをNULLにする方法と、検索される値を含むノードを切断するだけで切断される可能性のあるツリーの部分を再リンクする方法を調べるのは苦労しています。以下は

これまでのところ、私が持っている機能である：

bool BSTree::Remove(int content, BSTNode*& bst_node) const { 
// makes sure the tree is not empty (function returns false if it is) 
if (bst_node != NULL) { 
    // checks to see if nodes contents matches content param 
    if (bst_node->GetContents() == content) { 
     // checks to see if the node has children 
     if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) { 

     } else if (bst_node->GetLeftChild() == NULL) { 

     } else if (bst_node->GetRightChild() == NULL) { 

     } else { 

     } 
     return true; 
    // checks to see if the content of node is less/greater than content param 
    } else if (content < bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() != NULL) 
      return Remove(content, bst_node->GetLeftChild()); 
    } else if (content > bst_node->GetContents()) { 
     if (bst_node->GetRightChild() != NULL) 
      return Remove(content, bst_node->GetRightChild()); 
    } 
    } 
    return false; 
} 

私が追加したもの：remove関数のための

bool BSTree::Remove(int content, BSTNode*& bst_node) { 
    BSTNode* parent = bst_node; 
    if (bst_node == NULL) { 
    return false; 
    } else { 
    if (content == bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) { 
     if (bst_node == root_) { 
      Clear(); 
     } else { 
      // code for deleting leaf 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      size_--; 
     } 
     } else if (bst_node->GetLeftChild() == NULL) { 
     // code for deleting node with only right child 
     if (bst_node == root_) { 
      parent = bst_node->GetRightChild(); 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      root_ = parent; 
     } else { 

     } 
     size_--; 
     } else if (bst_node->GetRightChild() == NULL) { 
     // code for deleting node with only left child 
     if (bst_node == root_) { 
      parent = bst_node->GetLeftChild(); 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      root_ = parent; 
     } else { 

     } 
     size_--; 
     } else { 
     // code for deleting node with two children 
     size_--; 
     } 
    } else if (content < bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() == NULL) { 
     return false; 
     } else { 
     return Remove(content, bst_node->GetLeftChild()); 
     } 
    } else if (content > bst_node->GetContents()) { 
     if (bst_node->GetRightChild() == NULL) { 
     return false; 
     } else { 
     return Remove(content, bst_node->GetRightChild()); 
     } 
    } 
    } 
    return true; 
} 

ヘルパー機能：

int BSTree::FindMin(BSTNode* bst_node) const { 
    if (bst_node != NULL) { 
    if (bst_node->GetLeftChild() != NULL) 
     return FindMin(bst_node->GetLeftChild()); 
    return bst_node->GetContents(); 
    } 
    return 0; 
} 

Answer 1

一つの可能​​な方法をノードを削除することは、その直後の後継者と置き換えることです。つまり、リーフを削除して、ツリーinvariを壊さないようにします蟻。

ノードの後続ノードは右サブツリーの一番左の子ノードなので、削除したいノードに移動したら、そのノードの後続ノードを検索してスワップします。それが終わったら、葉を探してそれを削除します。一番左の子を取ったとき、あなたは葉にNULLの左の子があることを確信しています。それは右の子供を持って、右の子供と葉を交換し、それはそれです。

バイナリ検索ツリーの通常の実装では、Removeがノードを返すようにしているので、ノードを返すだけでツリーの形を変えることができ、孫のケースを気にする必要はありません。