duanjiyun7391 2012-06-27 11:56
浏览 32
已采纳

合适的树数据结构

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

  1. Parent node can have multiple children.
  2. Unique parent
  3. Tree structure is rarely changed, os it is ok to recreate than add/rearrange nodes.
  4. Two way traversal
  5. mainly interested in, find parent, find children, find a node with a unique id
  6. Every node has a unique id
  7. There might be only hundreds of nodes in total, so performance may not be big influence
  8. 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

  1. https://github.com/petar/GoLLRB
  2. http://www.stathat.com/src/treap

Please let know any additional information required.

  • 写回答

2条回答 默认 最新

  • dougezhua0017 2012-06-27 12:11
    关注

    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.
    • Each node has a list of child node.
    • Each node has an id
    • There is a (external) map from id --> node. May not even necessary.

    2 way traversal is possible, since parent and child nodes are know. Same for find parent and find child.
    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.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 我这模型写的不对吗?为什么lingo解出来的下面影子价格这一溜少一个变量
  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波