3

I am wondering if the Tree data structure has a dual. Something that 'starts at the leaves and converge on the root'.

If so, what's it called?

Maybe I'm missing something completely obvious. I could not find anything useful is searching on Google. Maybe that's because I'm not a native English speaker.

  • 2
    Well, if a tree starts at the root and branches out to the leaves, I suppose the dual would have to start at the leaves and converge on the root. I don't know if that data structure has a name or is useful. – Doval Feb 20 '15 at 20:59
  • @Doval That is the question indeed – EECOLOR Feb 20 '15 at 21:00
  • 3
    Your question presumes that there is some opposite of a tree. There isn't. You would have to qualify your question further in order to get a meaningful answer. What would an anti-tree look like? – Robert Harvey Feb 20 '15 at 21:29
  • 3
    @Doval that was my thoughts as well... unfortunate this question's getting a bunch of close votes just because people don't understand what's being asked here... – Jimmy Hoffa Feb 20 '15 at 21:31
  • 1
    @Telastyn remember your inverses? co. This is a cotree which is...sort of exactly...like you describe. Only it also has edges that skip levels becoming fully-cyclic. Go write an answer, I don't want to... – Jimmy Hoffa Feb 20 '15 at 22:07
5

If you view a tree as undirected graph without loops, then the opposite of that is just the same tree - it's completely isomorphic.

If you speak about an actual data structure which uses directed graphs, then, again, it can be just named "tree" which has it's links inverted: normally you have children referencing their parents (like is SQL database you'd have parent_id column referencing id column of the same table), but here you have parents have references of all their children. That would require having an array of references (parent->child), whereas in "normal" trees each element has just one reference (child->parent).

In git, for example, "true" merge commits have multiple parents, which is just what you've described. Although, git repository generally is not a tree, but some of its' parts can be.

EDIT: from Wikipedia:

tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

That means that parent-child relations in my git and SQL examples are actually considered inverted. As @Wyzard says, it is actually an "anti-tree" you've described. Yet, it is still called "tree".

Inversion in these examples allows using just one reference (to a parent) per node instead of list of references (to children). Also, it is convenient to add children in one step, without having to add a reference into a children references list of its' parent.

  • It's funny that you mention Git merges, because I think the structure of a Git repository without merges is a better example of an "anti-tree" as described in the question. Each branch head is a leaf, and each commit points to its parent (just one parent, if it's not a merge). If you follow those parent links, all the branches typically converge on a single initial commit (the "root"). – Wyzard Feb 21 '15 at 5:25
  • @Wyzard good point. Typically I see tree-like structures where children reference their parents (it's just more convenient, since just one reference per node required), but I've just read wiki and it says "where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root" – scriptin Feb 21 '15 at 7:15
  • This is just wrong. Everybody's answers here are just wrong... A co-tree has every relation not in the tree, and none of the relations in the tree. So this means instead of a parent referencing it's children, the children reference the parents - and every other child and parent except their own children - because in the tree they would have referenced their own children. As someone said - a tree represents hierarchy, so a co-tree would lack it. In the structure I described there'd be no hierarchy because each node would have references to everything except it's "children". – Jimmy Hoffa Mar 16 '15 at 15:35
  • @JimmyHoffa so you speak of inverted adjacency matrix, right? Why not post an answer explaining this? – scriptin Mar 16 '15 at 17:40
2

There sorta kind of is and isn't! But we need to refine our terminology to understand what's going on.

We have a hierarchy like this in graph theory, which flows from general at the top to more specific/restricted at the bottom:

Graph: a collection of nodes (vertex) and paths (connections between vertex)

Connected graph: a collection of nodes where you can pick any one start node and reach any other end node. The choice of start and end is arbitrary.

Tree: A connected graph where there is one and only one unique path between any one start node and any one end node. There are no alternate paths which do not backtrack (visit a node twice).

Rooted Tree: Just as a tree, but there is one specific item picked as being the root. From these we also define leaves, which is any node that must be an end-node when visited from the root - without visiting a node twice once you hit a leaf you cannot go anywhere, and the path is terminated. Leaves can also be called a "terminal vertex".

Note that even a rooted tree does not necessarily have direction - you are free to start at a leaf and proceed to the root, etc.

If a tree is implemented as a single-linked data structure, this can be thought of as a directed tree if there is no back-link available - once you leave the root for one of the connected nodes, you can't get back!

But such an implementation of a tree is not necessary in the definition of a tree! One can implement a tree with double-linked lists, such that you are free to do things like move towards the root (often referred to as a Parent) or away from the root (Child).

So if you want a data structure where you can start at a leaf and work to the root, you just need one that supports a "visit parent" function. You can also trivially define a system which does not permit moving from root (Parent) to Child, only from Child to Parent, and this sounds like what you are looking for. You basically just remove "visit child" functionality.

However, I am not aware of any formal name for such a structure, or what use such a structure would have. Trees that start from a root are useful, and ones that allow walking up and down are useful, but ones that only allow one-way movement towards the root is of such specialized/limited usefulness that I doubt it has a special name reserved for it. But I suppose anything is possible!

As a practical matter, you can easily implement one from existing directed trees or directed rooted trees.

0

I'm not sure of an exact mathematical concept for what you are describing, but it does seem to match pretty closely to the concept of a directed acyclic graph aka DAG. Many programmers actually use DAGs every day in their work, in the form of version control software. Git (and Mercurial and etc) commit histories form a DAG. We track the leaf nodes (in Git, the refs and branches; in Mercurial, the heads; etc) and traverse back to the root node. Each node has a pointer to to its parent, rather than the other way around.

A DAG does not need to be strictly tree-like in that it can have nodes with multiple parents (a merge commit in Git, for example).

-1

I'm not really sure what the meaningful difference would be, nor how you would go about implementing such a thing. The two ways I have seen trees implemented is either with an array or a by reference.

In an array implementation, the first element is the root and child nodes can be located by a fairly simple transformation of the parent's index. You could presumably reverse that easily enough so that the first element is the right most leaf and find the parent of any child by use of the array length and index. The only problem is that the array length and thus tree size is fixed and it is much harder to dynamically increase the size.

It's much easier to do with references though. You could easily create an AntiTree class that, say, provides a list of all leaves, and then each leaf references it's parent, and so on, until you reach the root which has no parent. But that just seems like a different traversal order.

Just had another thought. In terms of what to call it, isn't what you are describing just a funnel?

  • 1
    Maybe it's better to look at it differently. A tree has hierarchy as a fundamental concept. The opposite may be that structure that does not. – caveman Feb 20 '15 at 22:11
-1

From a purely technical standpoint, an anti-tree is what you have every time you choose to represent a tree not by equipping each parent node with an array of pointers to its child nodes, but by equipping each child node with a single pointer to its parent node.

Trees are commonly represented this way, for example, in relational databases.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.