java - 分层数据结构设计

Question

我有一个分层数据。像这样的东西:

以下是特点:

1. 一个节点可以有任意数量的 child
2. 节点可以被标记为特殊的。一旦一个节点被标记为特殊，从该节点开始的整个子树就变得特殊。

以下是我要执行的操作:

1. Tree.get("a.b.d.g") 应该给我节点 g
2. Tree.set("a.b.d.g",value) 设置节点g的值
3. 在任何节点我都应该知道谁是根节点
4. 如果我是特殊子树的一部分，我应该在任何节点
5. 我应该能够将子树复制/移动到另一棵树
6. 我可以在每个级别添加新节点或删除新节点
7. 我应该能够序列化这些数据

我目前可以想到“ HashMap 的 HashMap ”这种数据结构。我总是可以在每个节点缓存操作 3 和 4 的答案。当然，当我复制或移动等时，我需要清除缓存...

是否有任何其他实现方式可以通过上述操作以最少的内存占用实现最佳性能。

Answer 1

对于基本建模，您应该使用复合模式:

public class TreeNode {

    private String id;
    private TreeNode parent;
    private List<TreeNode> treeNodes = new ArrayList<>();

    ...
}

每个节点都有一个 String id，一个对其父节点的引用，并引用其子节点。您可以通过迭代 getParent() 直到其为空(使用递归)来获取顶级根。

为了解析路径想象一下:

public TreeNode get(final String path) {
    if (!path.isEmpty()) {
        for (TreeNode treeNode : treeNodes) {
            if (path.startsWith(treeNode.getId())) {
                return treeNode.get(path.substring(...));
            }
        }
    }
    return this;
}

现在，如果您正在寻找一种方法来存储此类数据(类似图形)并对其进行高性能查询，您可以考虑使用图形数据库，正如@sebgymn 提到的:Neo4j 是一个很好的 Java 数据库.

它是关于将连接数据模型与 NOSQL 结合使用的。节点在属性中存储数据，关系也在 Neo4j 中存储和显式命名，并充当节点之间的链接。然后您可以在节点上执行查询(属性、与其他节点的关系...)。

这是演示文稿的链接:http://fr.slideshare.net/neo4j/data-modeling-with-neo4j

一个很棒的教程:http://technoracle.blogspot.fr/2012/04/getting-started-with-neo4j-beginners.html

执行查询的测试图形数据库:http://www.neo4j.org/learn/cypher

例如:您可以尝试在 neo4j 中实现多级模式树(在您的情况下，检查顶根很重要:因此您的模型似乎在树上有不同的级别)。