Should I store the parent pointer in the tree / graph node?

Question

I am developing a data structure like tree / graph. It should be more like an oriented acyclic graph. One of the requirements is finding the path from root to a specific node, which means that when the user selects a node, the path from the root will be highlighted.

So the question is, should I store the parent pointer in each node? Or a more general question may arise when to store the parent pointer in each node? What are the advantages and disadvantages?

Thanks in advance!

ps. parent pointer == pointer to the parent node.

Answer 1

As a rule, you save the pointer back to the parent only if you intend to use algorithms that require it. Otherwise, this is unnecessary overhead both from the point of view of the memory used to store the pointer, and with the additional complexity of updating these pointers when inserting a node or rebalancing / reorganizing the tree.

Typical algorithms used with trees (width and depth search and traversal) do not require parent pointers, so your average realistic tree-like implementations usually don't include them.

Your request to “highlight the path from the root” can make parent pointers useful, although there are other ways to implement it. In general, adding redundant information to data structures should be avoided until it is proven that they are necessary to improve performance.

Answer 2

To talk about Christopher Johnson, answer: "you should only keep a pointer to the parent that you need."

Remember that for many algorithms that cross a tree / graph, you travel from parent to child during a walk, so you actually have a parent pointer. You can use this parent pointer (for example, passing it to a recursive function) instead of paying the cost of storing it in your structure.

Another point: for general graphs, this question is the same as "should I store inline edges (in addition to the outer edges) in my nodes?". If you look at the advanced graphics library , you will find a template library that allows you to select this option at compile time.

Answer 3

The overhead of maintaining a parent pointer regarding how often you update the tree / graph and how many nodes are in it. The overhead of storing the parent pointer for some algorithms depends on how often they are executed. I can’t tell you how often you update the map or how often you need a parent pointer, but my advice was to implement and run the profiler, or to make some kind of logical decision based on which operations take longer.

Answer 4

If in the future it is possible to change (expand) this structure (and for most of the code this is possible), I would suggest postponing the addition of this link until it is clearly needed.

It is much easier to add something than to delete when the code is used ...

But when designing data structures, it’s still useful to have several potential extensions ...