1

这是最适合对分层（包含关系）内容建模的树数据结构。我的语言有点不正式，因为我没有太多关于这些的理论背景

  1. 父节点可以有多个子节点。
  2. 唯一父级
  3. 树结构很少更改，重新创建比添加/重新排列节点还可以。
  4. 双向遍历
  5. 主要感兴趣，找父母，找孩子，找一个唯一id的节点
  6. 每个节点都有一个唯一的 id
  7. 可能总共只有几百个节点，所以性能影响可能不大
  8. 持久性可能很好，但不是必需的，因为我计划在从数据库读取数据后在内存中使用它。

我选择的语言是 go (golang)，所以可用的库是有限的。请在不考虑最符合上述要求的语言的情况下给出建议。

http://godashboard.appspot.com/列出了一些可用的树库。不确定质量和它们的活跃程度。我读过上帝

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

请告知所需的任何其他信息。

4

2 回答 2

3

由于只有数百个节点，因此只需将结构与您描述的相同。

  • 每个节点都有一个对父节点的唯一引用。
  • 每个节点都有一个子节点列表。
  • 每个节点都有一个id
  • 有一个来自 id --> 节点的（外部）映射。甚至可能没有必要。

2 路遍历是可能的，因为父节点和子节点是已知的。查找父母和查找孩子也是如此。
如果没有地图，则可以通过遍历整个树来查找 id。或者您可以使用地图快速找到节点。

添加节点很容易，因为每个节点都有一个列表。重新排列也很容易，因为您可以自由地从子节点列表中添加/删除并重新分配父节点。

我从与语言无关的方面回答这个问题。这是一个没有任何限制的树形结构，因此实现并不那么流行。

于 2012-06-27T12:11:08.253 回答
0

我认为 B-Tree 可以满足您的要求。http://en.wikipedia.org/wiki/B-tree

第 1,2,3 点：B-Tree 天生就支持这一点。（多个孩子，唯一的父母，允许插入/删除元素

第 4,5 点：默认情况下，每个节点都有指向其子节点的指针。此外，您可以维护每个节点的父级指针。您可以借助这些指针使用 BFS/DFS 实现搜索/遍历操作

Pomit 6：如果您不允许重复记录，则取决于您的插入方法的实现

Pont 7,8：这不是问题，因为您提到您只有数百条记录。虽然 B-Trees 对于外部磁盘存储也是非常好的数据结构。

于 2012-06-27T12:11:34.900 回答