mar*_*hon 16 java tree immutability data-structures
我喜欢使数据类不可变,以使并发编程更容易.但是,制定完全不可变的层次结构似乎存在问题.
考虑这个简单的树类:
public class SOTree {
private final Set<SOTree> children = new HashSet<>();
private SOTree parent;
public SOTree(SOTree parent) {
this.parent = parent;
}
public SOTree(Set<SOTree> children) {
for (SOTree next : children)
children.add(next);
}
public Set<SOTree> getChildren() {
return Collections.unmodifiableSet(children);
}
public SOTree getParent() {
return parent;
}
}
现在,如果我想创建这些层次结构,当我构造它时,父节点必须存在于当前节点之前,或者子节点必须首先存在.
SOTree root = new SOTree((SOTree)null);
Set<SOTree> children = createChildrenSomehow(root);
//how to add children now? or children to the children?
要么
Set<SOTree> children = createChildrenSomehow(null);
SOTree root = new SOTree(children);
//how to set parent on children?
在没有强制将它作为单个链接的树的情况下,是否有任何聪明的方法来构造这样的树并且仍然使所有节点完全不可变？
两个想法:
使用某种树工厂.您可以使用可变结构来描述树,然后有一个工厂来组装一个不可变树.在内部,工厂可以访问不同节点的字段,因此可以根据需要重新连接内部指针,但生成的树将是不可变的.
围绕可变树构建不可变树包装器.也就是说,让树构造使用可变节点,然后构建一个包装类,然后提供树的不可变视图.这类似于(1),但没有明确的工厂.
希望这可以帮助!
Eric Lippert最近发表了关于这个问题的博文.看他的博客文章Persistence,Facades和Roslyn的Red-Green Trees.这是一段摘录:
我们实际上通过保留两个解析树来做不可能的事."绿色"树是不可变的,持久的,没有父引用,是"自下而上"构建的,并且每个节点都跟踪其宽度而不是其绝对位置.当编辑发生时,我们只重建受编辑影响的绿树部分,这通常是树中总解析节点的O(log n).
"红色"树是一个不变的立面,围绕绿树建造; 它根据需要 "自上而下"构建,并在每次编辑时丢弃.它通过在从顶部向下穿过树时按需制造它们来计算父引用.它通过从宽度计算它们来制造绝对位置,同样,当你下降时.
您已正确地将您的问题描述为鸡和蛋之一。重述可能会导致解决方案的问题的另一种方法是，您想要种植一棵树（根、树干、树叶和所有 - 一次全部）。
一旦你接受了计算机只能一步一步地处理事情，一系列可能的解决方案就会出现：
看看 Clojure 如何创建不可变的数据结构。在 Clojure 的情况下，对树的每个操作（例如添加节点）都会返回一棵新树。
使树创建原子化。您可以创建特殊格式，然后反序列化树。由于所有序列化方法都是内部的，因此您不必公开任何可变方法。
就在工厂返回构建的树之前，先用标志将其锁定。这是原子操作的模拟。
使用包级方法来构造树。这样外部包就无法访问节点上的变异方法。
在访问节点时动态创建节点。这意味着您的内部树表示永远无法更改，因为更改节点对您的树结构没有影响。
小智 5
我最近遇到了类似的问题 - https://medium.com/hibob-engineering/from-list-to-immutable-hierarchy-tree-with-scala-c9e16a63cb89
该方法是自底向上构建树，首先构建底部节点，然后向上构建顶部节点。
阶段 1 - 按深度排序为了从底部开始，算法按节点在层次结构中的深度对节点进行排序（如您将在链接中看到的那样，有一种 O(n) 方法）。
阶段 2 - 从底部构建树底部节点没有子节点，因此该算法构建底部节点。
然后，向上一层，用之前处理过一层的节点构造有子节点的节点。算法继续直到它到达顶部节点。