バイナリ検索ツリーへの挿入

Question

先生がクラスのウェブサイトに次のコードを投稿しました。私はそれの働きを理解していません。もし誰かが精緻化することができれば、それは素晴らしいだろう。もう1つの理由は、なぜ彼女は戻り値としてペアを使用しています、boolだけでは十分ではありませんか？ここで

コードです：

template <class T> 

std::pair<BST<T>::iterator, bool> BST<T>::insert(const T& val) { 
    node<T>* t = root, *parent = null; 

    while (t) { 
     if (t->val == val) 
      //return std::pair<BST<T>::iterator, bool>(iterator(t, this), false);  
      return std::make_pair(iterator(t, this), false); // stl convenience function 

     parent = t; 

     if (t->val > val) t = t->left; 
     else if (t->val < val) t = t->right; 
    } 

    node<T>* newNode = new node<T>(val); // (1) allocate memory 
    newNode->parent = parent;    // (2) link child to parent 

    //(3) link parent to child 
    if (!parent) root = newNode; 
    else if (parent->val > val) parent->left = newNode; 
    else parent->right = newNode; 

    return std::make_pair(iterator(newNode, this), true); 
} 

Answer 1

まず、あなたはBST（二分探索木）何をするか知っている必要がありますを意味します。

BSTは、検索に使用される一種のデータ構造体です。ノードの値は左の子ノードの値より大きくなく、右の子ノードの値よりも小さくなりません。

次に、教師のコードについて話しましょう。

ジョブを実行するには2つの大きなステップがあります。

1. ノードが挿入される位置を見つける。 先生のコードでは、ループを使って仕事をしています。

   node * t = root、* parent = null;

初期設定として、プローブはrootに割り当てられます。親とは、プローブの親ノードを意味します。 nullの場合は、プローブがルートノードであることを意味します。

while (t) { 
    if (t->val == val) 
     return std::make_pair(iterator(t, this), false);   
    parent = t; 
    if (t->val > val) t = t->left; 
    else if (t->val < val) t = t->right; 
    } 

挿入する必要がある値とプローブの値を比較します。挿入値がプローブの値より小さい場合、プローブをその左の子に割り当てます。大きい場合は、プローブをその右の子に割り当てます。プローブの値と等しい場合、挿入は失敗します。挿入が失敗するか、プローブがヌルになるまでジョブを実行して、リーフノードに到達することを意味します。

2. ノードを挿入します。

   ノード* newNode =新しいノード（val）; newNode-> parent = parent;
   if（！parent） root = newNode; else if（parent-> val> val） parent-> left = newNode; else parent-> right = newNode;

新しいノードを作成し、その親ノードに親を割り当てます。 プローブの親がヌルの場合、ノードを挿入する前にツリーが空であることを意味します。新しいノードをrootとして設定します。 親の値がその値より大きい場合、その親の左の子をそれに割り当てます。小さい場合は、適切な子供を割り当てます。

return std::make_pair(iterator(newNode, this), true); 

挿入結果を返します。

最後の質問です。 あなたの先生は、挿入の結果とノードがあるノードの両方を返すことを望んでいると思います。結果がfalseの場合は、挿入する値と同じ値のノードがあることを意味します。それで、ノードはどこにあるのかを返します。結果が真の場合は、ノードを正常に挿入したことを意味し、ノードが返すノードは挿入したノードです。