Menu
I am developing a tree/graph like data structure. It should be more like a directed acyclic graph. One of the requirements is to find the path from root to a specific node, which means when user pick a node, the path from the root would be highlighted.
So, the question is shall I store a parent pointer in each node? Or a more general question would be when should I store a parent pointer in each node? What are the advantages and disadvantages?
Thanks in advance!
ps. parent pointer == a pointer to the parent node.
488
In computer science, an in-tree or parent pointer tree is an N-ary tree data structure in which each node has a pointer to its parent node, but no pointers to child nodes.
Approach: Write a recursive function that takes the current node and its parent as the arguments (root node is passed with -1 as its parent). If the current node is equal to the required node then print its parent and return else call the function recursively for its children and the current node as the parent.
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side.
For any given node index N , the children of that node will always be in locations 2N+1 and 2(N+1) in the same array. Therefore, The parent of any node N > 0 in such an array will always be at index (N-1)/2 .
Generally, you store a pointer back to the parent only if you are going to be using algorithms that require it. Otherwise, it is unnecessary overhead both in terms of the memory used to store the pointer and the extra complexity of updating those pointers when you insert a node or rebalance/reorganize the tree.
The typical algorithms used with trees (breadth-first and depth-first search and traversal) don't require parent pointers, which is why your average run-of-the-mill tree implementations generally don't include them.
Your "highlight path from the root" requirement might make parent pointers useful, although there are other ways to implement that. In general, one should avoid putting redundant information into data structures until it is proven that they are necessary for performance reasons.
79
To elaborate on Kristopher Johnson's reply: "you should only keep a pointer to the parent of you need it".
Remember that for many algorithms that traverse a tree/graph, during the traversal, you are traveling from the parent to the child, so you actually have the parent pointer in hand. You can use this parent pointer (for example passing it to a recursive function) instead of paying the costs of keeping it in your structure.
Another point: for general graphs this question is the same as "should I store the in-edges (in addition to the out-edges) in my nodes?". If you look at the boost graph library, you will find a template library that allows you this choice at compile time.
39
The overhead of storing a parent pointer is relative to how often you update the tree/graph, and how many nodes are in it. The overhead of not storing a parent pointer for some algorithms depends on how often they're run. I can't tell you how often you update the map or how often you need a parent pointer, but my advice would be to implement both and run a profiler, or make some kind of logical decision based on which operations take more time.
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
