我只是在看 Eric Lippert 的简单实现 不可变二叉树，我有一个关于它的问题。在展示了实现之后，Eric 指出
请注意，另一个不错的功能
不可变的数据结构是
不可能意外地（或
故意！）创建一棵树
包含一个循环。
看来Eric实现的这个特性不仅仅来自于不变性，还来自于树是由叶子构建而成的。这自然会阻止节点将其任何祖先作为子节点。似乎如果你以另一个方向构建树，就会引入循环的可能性。
我的想法是否正确，或者在这种情况下循环的不可能性是否仅仅来自于不变性？考虑到来源，我想知道我是否遗漏了一些东西。
编辑：经过更多思考，似乎从叶子开始构建可能是创建不可变树的唯一方法。我说得对吗？
I was just looking at Eric Lippert's simple implementation of an immutable binary tree, and I have a question about it. After showing the implementation, Eric states that
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.
It seems that this feature of Eric's implementation does not come from the immutability alone, but also from the fact that the tree is built up from the leaves. This naturally prevents a node from having any of its ancestors as children. It seems that if you built the tree in the other direction, you'd introduce the possibility of cycles.
Am I right in my thinking, or does the impossibility of cycles in this case come from the immutability alone? Considering the source, I wonder whether I'm missing something.
EDIT: After thinking it over a bit more, it seems that building up from the leaves might be the only way to create an immutable tree. Am I right?
发布评论
评论（4）
如果您使用不可变的数据结构，则在严格（而不是惰性）语言中，不可能创建循环；因为您必须按某种顺序创建元素，并且一旦创建了元素，您就无法将其更改为指向稍后创建的元素。因此，如果您创建了节点 n，然后创建了指向 n 的节点 m（可能是间接的），则您永远无法通过导致n 指向 m，因为您不允许改变 n，也不允许改变 n 已经指向的任何内容。
是的，你是对的，你只能通过从叶子开始构建来创建一棵不可变的树；如果您从根开始，则必须在创建根时修改根以指向其子级。只有从叶子开始，创建每个节点以指向其子节点，才能从不可变节点构造一棵树。
If you're using an immutable data structure, in a strict (as opposed to lazy) language, it's impossible to create a cycle; as you must create the elements in some order, and once an element is created, you cannot mutate it to point at an element created later. So if you created node n, and then created node m which pointed at n (perhaps indirectly), you could never complete the cycle by causing n to point at m as you are not allowed to mutate n, nor anything that n already points to.
Yes, you are correct that you can only ever create an immutable tree by building up from the leaves; if you started from the root, you would have to modify the root to point at its children as you create them. Only by starting from the leaves, and creating each node to point to its children, can you construct a tree from immutable nodes.
如果你真的想努力尝试，你可以创建一棵包含不可变循环的树。例如，您可以定义一个不可变的图类，然后说：
嘿，您有一棵带有“循环”的“树” - 因为当然您一开始就没有树，您已经得到一个有向图。
但是，对于实际上使用二叉树的传统“左子树和右子树”实现的数据类型，则无法制作循环树（当然，模数是使用反射或不安全代码等偷偷摸摸的技巧。）
If you really want to try hard at it you could create a tree with cycles in it that is immutable. For example, you could define an immutable graph class and then say:
And hey, you've got a "tree" with "cycles" in it - because of course you haven't got a tree in the first place, you've got a directed graph.
But with a data type that actually uses a traditional "left and right sub trees" implementation of a binary tree then there is no way to make a cyclic tree (modulo of course sneaky tricks like using reflection or unsafe code.)
当你说“从叶子构建”时，我想你包括了这样一个事实：构造函数接受子级，但从不接受父级。
不，因为那样你就会有相反的约束：构造函数必须采用父级，但不能采用子级。因此，在创建后代的所有祖先之前，您永远无法创建后代。因此不可能有循环。
不……请参阅我对 Brian 和 ergosys 的评论。
对于许多应用程序来说，子节点指向其父节点的树并不是很有用。我同意。如果您需要按照树的层次结构确定的顺序遍历树，则向上指向的树会使这变得困难。
然而对于其他应用程序，这种树正是我们想要的类型。例如，我们有一个文章数据库。每篇文章可以有一个或多个翻译。每个翻译都可以有翻译。我们将此数据结构创建为关系数据库表，其中每个记录都有一个指向其父记录的“外键”（指针）。这些记录都不需要更改其指向其父记录的指针。添加新文章或翻译时，将创建带有指向相应父项的指针的记录。
一个常见的用例是查询翻译表，查找特定文章的翻译或特定语言的翻译。啊，你说，翻译表是一个可变的数据结构。
当然是。但它与树是分开的。我们使用（不可变）树来记录层次关系，并使用可变表来迭代项目。在非数据库情况下，您可以有一个指向树节点的哈希表。不管怎样，树本身（即节点）永远不会被修改。
这是此数据结构的另一个示例，包括如何有效地访问节点。
我的观点是，OP 问题的答案是“是”，我同意你们其他人的观点，即循环的预防确实仅来自于不变性。虽然您可以在另一个方向（自上而下）构建一棵树，但如果这样做，并且它是不可变的，它仍然不能有循环。
当你谈论强大的理论保证时，例如
“这样的树不会很有用”相比之下就相形见绌了——即使它是真的。
人们总是无意中创建无用的数据结构，更不用说故意创建所谓无用的数据结构了。假定的无用性并不能保护程序免受数据结构中循环陷阱的影响。理论上的保证确实如此（假设您确实满足其规定的标准）。
PS 向上指向的树的一个很好的功能是，您可以保证树定义的一个方面，而向下指向的树数据结构（如 Eric Lippert 的）则不能保证：每个节点至多有一个父节点。 （请参阅大卫的评论和我的回应。）
When you say "built up from the leaves", I guess you're including the fact that the constructor takes children but never takes a parent.
No, because then you'd have the opposite constraint: the constructor would have to take a parent but never a child. Therefore you can never create a descendant until all its ancestors are created. Therefore no cycles are possible.
No... see my comments to Brian and ergosys.
For many applications, a tree whose child nodes point to their parents is not very useful. I grant that. If you need to traverse the tree in an order determined by its hierarchy, an upward-pointing tree makes that hard.
However for other applications, that sort of tree is exactly the sort we want. For example, we have a database of articles. Each article can have one or more translations. Each translation can have translations. We create this data structure as a relational database table, where each record has a "foreign key" (pointer) to its parent. None of these records need ever change its pointer to its parent. When a new article or translation is added, the record is created with a pointer to the appropriate parent.
A common use case is to query the table of translations, looking for translations for a particular article, or translations in a particular language. Ah, you say, the table of translations is a mutable data structure.
Sure it is. But it's separate from the tree. We use the (immutable) tree to record the hierarchical relationships, and the mutable table for iteration over the items. In a non-database situation, you could have a hash table pointing to the nodes of the tree. Either way, the tree itself (i.e. the nodes) never get modified.
Here's another example of this data structure, including how to usefully access the nodes.
My point is that the answer to the OP's question is "yes", I agree with the rest of you, that the prevention of cycles does come from immutability alone. While you can build a tree in the other direction (top-down), if you do, and it's immutable, it still cannot have cycles.
When you're talking about powerful theoretical guarantees like
"such a tree wouldn't be very useful" pales in comparison -- even if it were true.
People create un-useful data structures by accident all the time, let alone creating supposedly-useless ones on purpose. The putative uselessness doesn't protect the program from the pitfalls of cycles in your data structures. A theoretical guarantee does (assuming you really meet the criteria it states).
P.S. one nice feature of upward-pointing trees is that you can guarantee one aspect of the definition of trees that downward-pointing tree data structures (like Eric Lippert's) don't: that every node has at most one parent. (See David's comment and my response.)
您无法从根开始构建它，它需要您更改已添加的节点。
You can't build it from the root, it requires you to mutate nodes you already added.