Please pardon my complete lack of knowledge. Please provide some suggestions/pointers so that I can improve myself.

Given a table containing three values (ie, myName, myId, parentId), how does one insert those values into a tree such that the parent/child relationship defined in the table is maintained? Basically I'm given a file containing parents and children in no particular order. I would like to print all children of a given parent regardless of where they fall on the tree.

Note, this is not a school related question, simply a retard trying to learn how to do things more efficiently.

Thanks

On Fri, 11 Feb 2011 14:28:47 -0500, %u <no@spam.com> wrote:

> Please pardon my complete lack of knowledge. Please provide some
> suggestions/pointers so that I can improve myself.
>
> Given a table containing three values (ie, myName, myId, parentId),
> how does one insert those values into a tree such that the
> parent/child relationship defined in the table is maintained?
> Basically I'm given a file containing parents and children in no
> particular order. I would like to print all children of a given
> parent regardless of where they fall on the tree.
>
> Note, this is not a school related question, simply a retard trying
> to learn how to do things more efficiently.

With a many-to-one relationship of parent to child, I'd suggest each tree node having a array of child node pointers:

struct Node
{
   int id;
   string myName;
   Node *parent; // only needed if you want to go up the tree.
   Node *[] children;
}

-Steve

On 2/11/11, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> struct Node
> {
>     int id;
>     string myName;
>     Node *parent; // only needed if you want to go up the tree.
>     Node *[] children;
> }
>
> -Steve
>

What are the benefits of using struct pointers instead of classes in this case?

On Fri, 11 Feb 2011 14:49:41 -0500, Andrej Mitrovic <andrej.mitrovich@gmail.com> wrote:

> On 2/11/11, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>> struct Node
>> {
>>     int id;
>>     string myName;
>>     Node *parent; // only needed if you want to go up the tree.
>>     Node *[] children;
>> }
>>
>> -Steve
>>
>
> What are the benefits of using struct pointers instead of classes in this case?

Classes are more heavyweight (hidden vtable ptr, monitor) and have less control over their allocation.  For example, I used to use classes to represent tree nodes in dcollections' RBTree (which later became std.container.RedBlackTree), but I found structs use up less space and I can create custom allocators for them which significantly increase performance.

The only real downside is you occasionally have to deal with the pointer aspect (but most of the time not, since the dot operator auto-dereferences).

Plus, classes are good if you need polymorphism, or want to restrict allocation of nodes to the heap.  You don't need polymorphism for tree node, and the restriction isn't necessary in all cases.  It might be a good idea to make the "tree root" a class, but the nodes work better as structs.

-Steve

Cool, thanks for the insight. :)

On 02/11/2011 09:21 PM, Steven Schveighoffer wrote:
> On Fri, 11 Feb 2011 14:49:41 -0500, Andrej Mitrovic
> <andrej.mitrovich@gmail.com> wrote:
>
>> On 2/11/11, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>> struct Node
>>> {
>>> int id;
>>> string myName;
>>> Node *parent; // only needed if you want to go up the tree.
>>> Node *[] children;
>>> }
>>>
>>> -Steve
>>>
>>
>> What are the benefits of using struct pointers instead of classes in this case?
>
> Classes are more heavyweight (hidden vtable ptr, monitor) and have less control
> over their allocation. For example, I used to use classes to represent tree
> nodes in dcollections' RBTree (which later became std.container.RedBlackTree),
> but I found structs use up less space and I can create custom allocators for
> them which significantly increase performance.

I noticed once another overhead, namely time of method call (certainly due to runtime lookup of so-called virtual methods). Was significant, about 3x IIRC.

> The only real downside is you occasionally have to deal with the pointer aspect
> (but most of the time not, since the dot operator auto-dereferences).
>
> Plus, classes are good if you need polymorphism, or want to restrict allocation
> of nodes to the heap. You don't need polymorphism for tree node, and the
> restriction isn't necessary in all cases. It might be a good idea to make the
> "tree root" a class, but the nodes work better as structs.

...as long as nodes are all of the same type. But isn't it a very common case to have a hierarchy of node types (which /must/ have a common supertype to all fit into Node* and/or Node*[] slots)?
I started my last app with struct nodes, then switched to class because was to much mess to maintain (type annotations and such, manual castings all the way down, somewhat like hand-made tag unions).

denis
-- 
_________________
vita es estrany
spir.wikidot.com