Вставка в двоичном дереве поиска

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 для выполнения задания.

   узел * t = корень, * parent = 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. Вставить узел.

   узел * новыйNode = новый узел (val); newNode-> parent = parent;
   если (! Parent) root = newNode; else if (parent-> val> val) parent-> left = newNode; еще parent-> right = newNode;

Создайте новый узел и назначьте родительский элемент его родительскому узлу. Если родители зонда имеют значение NULL, это означает, что дерево пустое, прежде чем вставлять узел. Поэтому установите новый узел как root. Если значение родителя больше его значения, присвойте ему родительский родительский элемент. Если меньше, назначьте ему правильный ребенок.

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

верните результат ввода.

Ваш последний вопрос. Я думаю, что ваш учитель хочет вернуть как результат вставки, так и узел, где находится узел. Если результат является ложным, это означает, что есть узел с тем же значением, что и значение, которое вы хотите вставить. Поэтому он возвращает узел, где он есть. Если результат верен, это означает, что вы успешно вставляете узел, а возвращаемый им узел - это тот узел, который вы вставляете.