java - 如何创建一个完全不可变的树层次结构？建筑先有鸡还是先有蛋

Question

我喜欢使数据类不可变 以使并发编程更容易。但是制作一个完全不可变的层次结构似乎有问题。

考虑这个简单的树类:

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?

在不强制它成为一棵单链树的情况下，是否有任何聪明的方法来构建这样一棵树并且仍然使所有节点完全不可变？

Answer 1

Eric Lippert 最近在博客中谈到了这个问题。查看他的博客文章 Persistence, Facades and Roslyn's Red-Green Trees .以下是摘录:

We actually do the impossible by keeping two parse trees. The "green" tree is immutable, persistent, has no parent references, is built "bottom-up", and every node tracks its width but not its absolute position. When an edit happens we rebuild only the portions of the green tree that were affected by the edit, which is typically about O(log n) of the total parse nodes in the tree.

The "red" tree is an immutable facade that is built around the green tree; it is built "top-down" on demand and thrown away on every edit. It computes parent references by manufacturing them on demand as you descend through the tree from the top. It manufactures absolute positions by computing them from the widths, again, as you descend.