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
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
parent reply 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
parent reply "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
next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Cool, thanks for the insight. :)
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