Problem on my binary tree class' nodes

Question

I'm trying to code a class for binary tree representation. Each node has a value (key), an index, and a Node* pointer for parent(p), left-child(left) and right-child(right). The problem is on pointers. It's easier giving my example problem than explaining.

I coded a print() function that prints out each node in the tree. Here is the class header file. And here is the main test file.

The problem is, when i call T.print(), it prints only 10, 5 and 7.

Uhm... no, they shouldn't. It go in a forever loop if i do this. n is actually the number of nodes. They are stored in a vector, so, if the node 3 is stored, i can access through T[n-1] = 2. — user824476
– user824476, Commented Jul 1, 2011 at 8:35
have you tested the return values of your insert calls to make sure they're returning true? — jswolf19
– jswolf19, Commented Jul 1, 2011 at 8:43

Sander De Dycker · Accepted Answer · 2011-07-01 09:01:39Z

1

The problem is that you're using a vector, which internally (re-)allocates storage as needed.

So, when pushing back into a vector, it could very well be that the whole internal data is copied to some other memory location - making all pointers that still point to the old locations invalid.

An easy "fix" would be to reserve a certain amount of space for the vector, so you can at least store a certain amount of nodes in it without re-allocation.

For example by adding this at the start of your RootedTree constructors :

T.reserve(64);

Note that that is not a robust solution (if you try to put more than 64 nodes in the vector, you're still likely to have the same problem) - but it'll confirm the above analysis.

edited Jul 1, 2011 at 9:01

answered Jul 1, 2011 at 8:55

Sander De Dycker

16.3k1 gold badge37 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Sander De Dycker Over a year ago

@user824476 : I do not recommend the reserve approach though - for the reasons stated at the end of the answer. You might be better off storing the nodes explicitly as a tree - without using a vector for storage.

Captain Giraffe · Accepted Answer · 2011-07-01 09:34:05Z

0

You have to decide what kind of structure you want to represent your binary tree.

Either of

a vector
pointers

Not both!

So your options are

Removing all pointer related stuff and stick with the vector, treat the Node at index i as the parent to the Nodes at i*2, i*2 + 1. and the opposite for the child -> parent relationship.
Stop using the vector. Have a root node Node * root inside your RootedTree class.

They two approaches have different strengths and weaknesses, in particular, the array case lets you get rid of all the pointers, in the pointer case you don't have to worry about the performance of reallocations, and trickier manipulations like deletion is a lot easier.

edited Jul 1, 2011 at 9:34

answered Jul 1, 2011 at 9:12

Captain Giraffe

14.8k7 gold badges42 silver badges69 bronze badges

Collectives™ on Stack Overflow

Problem on my binary tree class' nodes

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related