Re: Nary trees

[etienne buxin <ebuxin yahoo com>]

--- "Eric M. Monsler" <emonsler beamreachnetworks com> wrote:
> etienne buxin wrote:
> > hi,
> > 
> > i'd like to use a structure similar to glib's Nary tree, but with the difference that many
> parent
> > nodes can share one or several children nodes.
> > any clue?
> 
> 
> This is going to be rather difficult.
> 
> Unless you enforce a policy that only sibling-nodes can share child 
> nodes, you are going to have a lot of trouble.  Even then, any trivial 
> operation on a child node (e.g., remove from tree) will require 
> searching over the full set of parent-siblings and checking the child 
> pointers against the full set of siblings for the child-node.
> 
> Don't do it.
> 
> If a fellow developer at work suggested such a data-storage approach, I 
> would require a tone of convincing that this was a reasonable thing to do.
> 
> If you do, I strongly suggest that you do not base it off of the current 
> glib n-ary tree implimentation.  At a minimum, I would enforce a policy 
> that a node has a numbered depth N, that all children are depth N+1 and 
> parents are N-1.  This may seem obvious, but in a multi-parent scenario 
> it would be easy to violate if moving a set of nodes within the tree.
> 
> A suggested structure:
> 
> struct eb_manymany {
>    uint			node_level;
>    uint			num_parents;
>    uint			num_par_max;
>    struct eb_manymany	**par_ptr_array;
>    uint			num_children;
>    uint			num_child_max;
>    struct eb_manymany	**chd_ptr_array;
>    gpointer		data;
> }
> 
> That lets you reference count the parents and children, so that, for 
> example, when removing a node you can go to all the parents and remove 
> that child from their list of children.
> 
> The _max allows dynamix allocation of the pointer arrays, if you 
> previously allocated space for 12 children and need a 13th, you can 
> reallocate that array up to size 24 or somthing, with 13 places occupied.
> 
> If the above doesn't make sense after a few readings, you're not ready 
> to tackle this.  I have done a two-level parent-child that was 
> many-to-many, where entities were by definitions either parents or 
> children, and by the time I had the appropriate API and error checking 
> all in place it was very cumersome.
> 
> For example, what policy do you generically implement if a the last 
> parent of a node is freed?  In my application, that meant that the child 
> was now a discard and could be freed, but that may or may not be 
> appropriate for a generic storage library.  Specify a calllback for the 
> child node in that situation, defaulting to freeing?  Complexity!
> 
> If you do get it working as infinite level many-to-many, please post the 
> code. :)
> 
> Eric
> 

hello,

in fact, i'd like to create a structure to represent events.  i investigated trees because i need
a parent-child relationship between events, with the parent event being a consequence of his child
events.  Because one event may have several consequences, it must be able to have many parents (of
different depht levels, moreover). i could duplicate the child for each of his parents, but this
is not too good, because each event has _a lot_ of info carried with ( *data in glib's Nary tree)
and this will consume a lot of ressources.

has someone an idea?

thanks,
E.


__________________________________________________
Do you Yahoo!?
Faith Hill - Exclusive Performances, Videos & More
http://faith.yahoo.com