algorithm - 合适的树数据结构

Question

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

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

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

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

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

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

Answer 1

由于只有数百个节点，所以将结构与您描述的相同即可。

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

2 种遍历是可能的，因为父节点和子节点是已知的。查找父项和查找子项相同。
如果没有 map ，可以通过遍历整棵树来查找 id。或者您可以使用 map 快速找到节点。

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

我是从与语言无关的角度来回答这个问题的。这是一个没有任何限制的树结构，所以实现不是很流行。