我应该将父指针存储在树/图节点中吗？
我正在开发类似树/图的数据结构。 它应该更像是有向无环图。 要求之一是找到从根到特定节点的路径，这意味着当用户选择一个节点时，从根开始的路径将突出显示。
那么，问题是我应该在每个节点中存储一个父指针吗？ 或者一个更普遍的问题是我什么时候应该在每个节点中存储父指针？ 有什么优点和缺点？
提前致谢！
附注父指针==指向父节点的指针。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
一般来说，只有当您要使用需要它的算法时，您才存储返回父级的指针。否则，在用于存储指针的内存以及插入节点或重新平衡/重新组织树时更新这些指针的额外复杂性方面，都是不必要的开销。
树使用的典型算法（广度优先和深度优先搜索和遍历）不需要父指针，这就是为什么普通的树实现通常不包含它们。
您的“突出显示从根开始的路径”要求可能会使父指针变得有用，尽管还有其他方法可以实现这一点。一般来说，人们应该避免将冗余信息放入数据结构中，直到证明它们出于性能原因是必要的。
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.
详细说明克里斯托弗·约翰逊的回答：“你应该只保留一个指向你需要它的父级的指针”。
请记住，对于许多遍历树/图的算法，在遍历过程中，您是从父级移动到子级，因此您实际上拥有父级指针。您可以使用此父指针（例如将其传递给递归函数），而不必支付将其保留在结构中的成本。
另一点：对于一般图，这个问题与“我应该在节点中存储入边（除了出边）吗？”相同。如果您查看 Boost 图形库，您会发现一个模板库允许您在编译时进行此选择。
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.
存储父指针的开销与更新树/图的频率以及其中的节点数有关。某些算法不存储父指针的开销取决于它们的运行频率。我无法告诉您更新映射的频率或需要父指针的频率，但我的建议是实现两者并运行探查器，或者根据哪些操作需要更多时间来做出某种逻辑决策。
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.
如果将来可以更改（扩展）此结构（对于大多数代码来说这是可能的），我建议推迟添加此链接，直到明确需要它为止。
在使用代码时添加某些内容比删除内容要简单得多...
但是在设计数据结构时记住几个潜在的扩展仍然很有用...
If it will be possible to change (extend) this structure in future (and for most of code it is possible), I would suggest to postpone adding this link until it will be clearly needed.
It's much simpler to add something than to remove when code is in use...
But it's still useful to have several potential extensions in mind when designing data structures...