I've looked at some code for BSTs and I can see that each node is a struct. Is this necessary?
+4
A:
No, it could be a class. It can't be a primitive, because it needs to store a value and also point to children.
Well, I should say that you could also represent your BST as an array, where the left and right children of the node at position i are in positions 2 * i + 1 and 2 * i + 2, respectively. But then you would have to worry about resizing, and you would need a special value to represent null, and delete operations become pretty complicated. I don't recommend this approach as anything other than an academic exercise.
danben
2010-02-08 05:17:47
Oops, I didn't see your answer. I think you meant **3** * i + 2, though.
Potatoswatter
2010-02-08 05:39:15
No, 2 is correct.
danben
2010-02-08 05:46:49
3 seems better... This confusion is a good argument why one should use structs.
Thilo
2010-02-08 05:48:07
John R. Strohm
2010-02-08 06:17:34
Oh, I see now. That's more like an inside-out heap. For a black-box algorithm it might be analogous to a tree, but something requiring rebuilding rather than relinking can't properly be called a tree.
Potatoswatter
2010-02-08 08:27:58
Of course it can be called a tree. A tree doesn't have any particular implementation - it is just a directed, acyclic graph.
danben
2010-02-08 14:21:20
+4
A:
Its not mandatory.
But since the data a node contains along with the two links together form a logical entity they are usually put together in a struct. So that it becomes easier to code functions that take a node as an argument or return a node.
codaddict
2010-02-08 05:24:21
+7
A:
int flat_tree[ 1000 ][ 3 ];
// for each tree node, value is stored in element [id][0]
// id of left_child stored in element [id][1]
// id of right_child stored in element [id][2]
…
I'm not gonna go any further with this.
Generally speaking, structs/classes are used for any kind of linked data structure. Also generally, any feature of the type system may be defeated or ignored and you can do everything (heap allocation, etc) in one array of ints in very painful fashion.
Potatoswatter
2010-02-08 05:33:46
Best answer so far: at the same time, it shows two answers. Theoretically no, practically yes.
MSalters
2010-02-08 09:45:40
A second dimension may make this easier, where the index values can be 0 for left, 1 for data, and 2 for right.
Thomas Matthews
2010-02-08 19:42:17
+1
A:
No, not strictly speaking. In the FORTRAN days, people used parallel arrays, or two-dimensional arrays.
Tony Hoare's section of "Structured Programming" by Dahl, Dijkstra, and Hoare, talked about data structuring and record types.
John R. Strohm
2010-02-08 05:40:43
A:
You can do simpler than parallel arrays if your payload admits a sentinal value: you can use a implicit tree (that is, not bother with links at all).
payload_type a[tree_size];
Just a long flat array containing only payload values, with position in the array coding for link structure:
a[0]is roota[1]is root->lefta[2]is root->righta[3]is root->left->lefta[4]is root->left->right- ...
For the node at position i, go to 2*i+1 for left and 2*i+2 for right
You initialize it to all sentinal values, and start adding things...
dmckee
2010-02-10 20:06:04