英文:
Suitable tree data structure
问题
哪种树形数据结构最适合模拟层次（包含关系）内容？我的语言有点不正式，因为我对这些没有太多的理论背景。
- 父节点可以有多个子节点。
- 唯一的父节点。
- 树结构很少改变，所以重新创建而不是添加/重新排列节点是可以的。
- 双向遍历。
- 主要关注查找父节点、查找子节点、查找具有唯一标识的节点。
- 每个节点都有唯一的标识。
- 总共可能只有几百个节点，所以性能可能不会有太大影响。
- 持久性可能是有好处的，但不是必需的，因为我计划在从数据库读取数据后在内存中使用它。
我选择的语言是Go（golang），所以可用的库有限。请给出一个不考虑语言的建议，最适合上述要求。
http://godashboard.appspot.com/ 列出了一些可用的树库。不确定它们的质量和活跃程度。我读过关于以下两个库的信息：
请告知是否需要任何其他信息。
英文:
Which is the most suitable tree data structure to model a hierarchical (containment relationship) content. My language is bit informal as I don't have much theoretical background on these
- Parent node can have multiple children.
- Unique parent
- Tree structure is rarely changed, os it is ok to recreate than add/rearrange nodes.
- Two way traversal
- mainly interested in, find parent, find children, find a node with a unique id
- Every node has a unique id
- There might be only hundreds of nodes in total, so performance may not be big influence
- Persistence may be good to have, but not necessary as I plan to use it in memory after reading the data from DB.
My language of choice is go (golang), so available libraries are limited. Please give a recommendation without considering the language which best fit the above requirement.
http://godashboard.appspot.com/ lists some of the available tree libraries. Not sure about the quality and how active they are. I read god about
Please let know any additional information required.
答案1
得分: 3
由于只有数百个节点，只需按照您描述的方式构建结构即可。
- 每个节点都有一个唯一的父节点引用。
- 每个节点都有一个子节点列表。
- 每个节点都有一个id。
- 有一个（外部）从id到节点的映射。可能甚至不需要。
由于已知父节点和子节点，可以进行双向遍历。查找父节点和子节点也是一样的。如果没有映射，可以通过遍历整个树来查找id。或者您可以使用映射快速找到节点。
添加节点很容易，因为每个节点都有一个子节点列表。重新排列也很容易，因为您可以自由地从子节点列表中添加/删除节点并重新分配父节点。
我从语言无关的角度回答这个问题。这是一个没有任何限制的树结构，所以实现并不那么流行。
英文:
Since there are only hundreds of nodes, just make the structure the same as you have described.
- Each node has a unique reference to parent node.<br>
- Each node has a list of child node.<br>
- Each node has an id<br>
- There is a (external) map from id --> node. May not even necessary.<br>
2 way traversal is possible, since parent and child nodes are know. Same for find parent and find child.<br>
Find id can be done by traverse the whole tree, if no map. Or you can use the map to quickly find the node.
Add node is easy, since there is a list in each node. Rearrange is also easy, since you can just freely add/remove from list of child nodes and reassign the parent node.
I'm answering this question from a language-agnostic aspect. This is a tree structure without any limit, so implementation is not that popular.
答案2
得分: 0
我认为B-Tree是满足您要求的最佳选择。http://en.wikipedia.org/wiki/B-tree
点1、2、3：B-Tree本身就支持这一点（多个子节点，唯一的父节点，允许插入/删除元素）。
点4、5：每个节点默认实现都会有指向其子节点的指针。此外，您还可以为每个节点维护指向父节点的指针。您可以借助这些指针实现BFS/DFS的搜索/遍历操作。
点6：取决于您的插入方法的实现，如果不允许重复记录，则不会出现问题。
点7、8：对于您提到只有数百条记录的情况，这不是问题。尽管B-Tree也是外部磁盘存储的很好的数据结构。
英文:
I think B-Tree is way to go for your requirements. http://en.wikipedia.org/wiki/B-tree
<br>
Point 1,2,3: B-Tree inherently support this. (multiple children, unique parent, allows insertion/deletion of elements <br>
Point 4,5: each node will have pointers for its child by default implementation . Additionally you can maintain pointer of parent for each node. you can implement your search/travers operations with BFS/DFS with help of these pointers<br>
Pomit 6: depends on implementation of your insert method if you dont allow duplicate records<br>
Pont 7,8: not a issue as for you have mentioned that you have only hundreds of records. Though B-Trees are quite good data structure for external disk storage also.<br>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论