Is there a standard name for this tree structure?

Patrick Maupin pmaupin at gmail.com
Sun Apr 4 17:41:25 CEST 2010


On Apr 4, 9:06 am, Duncan Booth <duncan.bo... at invalid.invalid> wrote:
> Do you have any carniverous apes? If so it's a directed acyclic graph.

Well, since he has a root node, he's really only described the *use*
of this data structure implementation for a rooted tree.

As you point out, the implementation itself is more general than a
rooted tree, and could be used for any DAG.  But you don't go far
enough.  This particular implementation could be used for any directed
graph -- there is nothing (other than the problem domain) requiring
that data in this dict be acyclic.  In fact, there are sometimes good
reasons for using this sort of structure for cyclic data.  Having a
name for each node, and always indirectly referring to the node by its
name, can sometimes greatly simplify the implementation of problems
requiring a cyclic graph (starting with the really basic problem of
wanting to dump the whole structure out in a reasonable fashion for
debugging).

The primary differences between this structure and just haphazardly
wiring up random objects into a directed graph are that (1) there may
be some performance differences (but when the garbage collector has to
figure out how to break cycles, these difference might or might not be
in the direction you expect) and (2) with this structure, every object
needs a globally unique name for indexing purposes.

Having said all that, I don't know what the proper name for this data
structure is, either :-)

However, in determining the name, I would probably focus on the data
structure being represented (in Steven's case, a tree), and the data
structure used to represent it (a Python dict), and *why/how* the
underlying structure is used.  So I would probably call it something
like an "associatively addressed tree".

Regards,
Pat



More information about the Python-list mailing list