CODEWITHSUNDEEP
c++algorithmbinary-treec++17
R0xx0rZzz
R0xx0rZzz

Reputation: 35

C++, BTree Insert

Hi this is a code from my SearchTree class. Node* is a structure whith m_info type int, and m_left(smaller nodes by info) and m_right(bigger nodes by info)

void SearchTree::insert(const int &x) {
  Node* tempo = m_root;
  while (tempo != nullptr) {
    if (tempo->m_info >= x) {
      tempo = tempo->m_left;
    } else {
      tempo = tempo->m_right;
    }
  }
  tempo = new Node(x);
}

I am trying to insert a new node to the tree. But looks like I am missing something in memory management. There tempo is a pointer to a new node, however it is not being related to m_root. I am confused here. I really love the power of c++ but it bends my logic.

What am I missing here?

Upvotes: 3

Views: 219

Answers (2)

Thomas Sablik
Thomas Sablik

Reputation: 16448

You can't save the pointer in tempo only. Tempo is a copy of your current position in the tree. You have to assign it to actual variable.

My solution to this problem would be to check if child is nullptr before you iterate

void SearchTree::insert(const int &x) {
  if (!m_root) {
      m_root = new Node(x);
      return;
  }
  Node* tempo = m_root;
  while (true) {
    if (tempo->m_info >= x) {
      if (!tempo->m_left) {
        tempo->m_left = new Node(x);
        return;
      }
      tempo = tempo->m_left;
    } else {
      if (!tempo->m_right) {
        tempo->m_right = new Node(x);
        return;
      }
      tempo = tempo->m_right;
    }
  }
}

Also you should use smart pointers instead of raw pointers.

An alternative solution is a pointer to pointer. I didn't test it but you can try

void SearchTree::insert(const int &x) {
  Node** tempo = &m_root;
  while (*tempo) {
    if ((*tempo)->m_info >= x) {
      tempo = &(*tempo)->m_left;
    } else {
      tempo = &(*tempo)->m_right;
    }
  }
  *tempo = new Node(x);
}

enter image description here

In this image you can see. If you use Node* tempo = m_root then tempo contains a copy of the value in m_root. If you change tempo then m_root stays unchanged.

If you use Node** tempo = &m_root then tempo is pointer to m_root. You can change m_root through tempo.

Upvotes: 1

ComicSansMS
ComicSansMS

Reputation: 54589

You keep advancing tempo until it is equal to nullptr. At this point you have left the tree and all you have in hand is a pointer into nothingness. Note that in particular the program has no way of determining which node you last visited that led to tempo becoming null.

What you need to do instead is stop one step earlier: While tempo is still pointing to a node, but the next step would make it point to null. Now you still have a valid node of the tree in your hand and can attach the newly allocated node to it.

Upvotes: 4

Related Questions