이진 검색 트리에 삽입

Question

선생님이 클래스 웹 사이트에 다음 코드를 게시했습니다. 나는 그 일을 이해하지 못한다. 누군가가 정교 할 수 있다면, 좋을 것입니다. 한 가지 더, 왜 그녀는 쌍을 반환 값으로 사용합니까, 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는 검색에 사용되는 일종의 데이터 구조체입니다. 노드의 값은 왼쪽 자식 노드의 값보다 크지 않고 오른쪽 자식 노드의 값보다 작지 않습니다.

그럼 선생님 코드에 대해 이야기 해 봅시다.

두 가지 큰 단계가 있습니다.

1. 노드가 삽입 될 위치를 찾습니다. 교사 코드가 while 루프를 사용하여 작업을 수행합니다.

   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; 
    } 

삽입해야하는 값과 검사 값을 비교하십시오. 삽입 값이 검사 값보다 작 으면 검사를 왼쪽 자식에 지정합니다. 그것이 더 크다면 오른쪽 아이에게 프로브를 할당하십시오. probe의 값과 같으면 삽입이 실패합니다. 삽입이 실패하거나 프로브가 널 노드에 도달 함을 의미하는 null이 될 때까지 작업을 수행하십시오.

2. 노드를 삽입하십시오.

   노드 * newNode = 새 노드 (val); newNode-> parent = parent;
   if (! parent) root = newNode; else if (parent-> val> val) parent-> left = newNode; else parent-> right = newNode;

새 노드를 만들고 상위 노드에 부모를 할당하십시오. 프로브의 부모가 null 인 경우 노드를 삽입하기 전에 트리가 비어 있음을 의미합니다. 그래서 새로운 노드를 root로 설정하십시오. 부모의 값이 값보다 큰 경우 부모의 왼쪽 자식을 할당합니다. 더 작 으면, 그것에 적당한 아이를 할당하십시오.

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

삽입 결과를 반환합니다.

마지막 질문. 선생님은 삽입 결과와 노드가있는 노드를 모두 반환하려고한다고 생각합니다. 결과가 false이면 삽입하려는 값과 동일한 값을 가진 노드가 있음을 의미합니다. 그래서 노드를 반환합니다. 결과가 true이면 노드를 성공적으로 삽입하고 반환하는 노드는 삽입 한 노드입니다.