algorithm - 为什么 Eric Lippert 的不可变二叉树中没有循环？

Question

我只是在看 Eric Lippert 的 immutable binary tree 的简单实现，我对此有疑问。在展示了实现之后，Eric 表示

Note that another nice feature of immutable data structures is that it is impossible to accidentally (or deliberately!) create a tree which contains a cycle.

Eric 实现的这个特性似乎不仅仅来自不变性，还来自于树是从叶子建立起来的。这自然会阻止节点将其任何祖先作为子节点。看起来如果你在另一个方向构建树，你会引入循环的可能性。

我的想法是否正确，或者在这种情况下循环的不可能性是否仅来自不变性？考虑到来源，我想知道我是否遗漏了什么。

编辑:在仔细考虑之后，似乎从叶子开始构建可能是创建不可变树的唯一方法。我对吗？

Answer 1

如果您使用的是不可变数据结构，在严格(相对于惰性)语言中，就不可能创建循环；因为您必须按某种顺序创建元素，并且一旦创建了一个元素，您就不能改变它以指向稍后创建的元素。因此，如果您创建了节点 n，然后创建了指向 n 的节点 m(可能是间接的)，您将永远无法通过导致n 指向 m，因为您不允许改变 n，也不允许改变 n 已经指向的任何东西。

是的，你是对的，你只能通过从叶子开始构建来创建一棵不可变的树；如果您从根开始，则必须在创建子项时修改根以指向其子项。只有从叶子开始，创建每个节点并指向其子节点，才能从不可变节点构建树。