www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Inserting nodes into a tree

reply %u <no spam.com> writes:
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
Feb 11 2011
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Feb 11 2011
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Feb 11 2011
prev sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Cool, thanks for the insight. :)
Feb 11 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
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?
Feb 11 2011
prev sibling parent spir <denis.spir gmail.com> writes:
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
Feb 11 2011