更改二叉树中的节点的影响
假设我想更改以下树中的橙色节点。
因此，我需要进行的唯一其他更改是绿色节点 的左指针。
蓝色节点将保持不变。
我在某个地方错了吗？ 因为根据 这篇文章（解释拉链），甚至蓝色节点也需要更改。
同样，在这张图片（重新着色）中，来自同一篇文章< /a>, 为什么我们要更改橙色节点（当我们更改节点 x 时）？
Suppose I want to change the orange node in the following tree.
So, the only other change I'll need to make is in the left pointer of the green node.
The blue node will remain the same.
Am I wrong somewhere? Because according to this article (that explains zippers), even the blue node needs to be changed.
Similarly, in this picture (recolored) from the same article, why do we change the orange nodes at all (when we change node x)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在命令式语言中，你是正确的，只需要更改绿色节点。然而，对于纯函数式数据结构来说，情况并非如此。为了更改橙色节点，您需要更改绿色节点。因为您更改了绿色节点，所以您需要更改蓝色节点（依此类推）。实际上，“更改”这个词是不正确的，您实际上是在复制相关数据并创建一个新节点。因此，蓝色节点并没有被更改，而是创建了一个新的蓝色节点（指向新的绿色节点）。
这样做可以保持持久性，这意味着您可以存储树的所有先前状态。如果您想在更改橙色节点之前和更改橙色节点之后存储树，则需要同时更改绿色和蓝色 - 否则两者将是同一棵树的副本。
在第二种情况下，同样的情况也适用，只是现在您还需要更改父指针。由于您已经更改了根节点，因此所有橙色节点都需要将其父节点指针设置为指向其新父节点。
编辑：为了澄清一点，这样想一下。在纯函数式语言中，您无法修改任何内容，只能创建新节点或复制它们。因此，当您想要更改橙色节点时，您实际上使用不同的数据创建了它的副本（“更改”）。现在，您需要绿色节点指向橙色节点，这需要您创建一个新的橙色节点 - 该节点指向新的绿色节点。蓝色节点也是如此。
In an imperative language you are correct, only the green node needs to be changed. However for purely functional data structures this is not the case. In order to change the orange node you need to change the green node. Because you changed the green node, you then need to change the blue node (and so on). Actually the word change is incorrect, you are really copying the relevant data and creating a new node. So The blue node isn't being changed so much as a new blue node (which points to the new green node) is being created.
Doing so maintains persistence, meaning that you can store all previous states of the tree. If you wanted to store the tree before changing the orange node and after changing the orange node, you'd need change both the green and blue - otherwise both would be copies of the same tree.
In the second case, the same thing applies, only now you also need to change parent pointers. Since you've changed the root node, all the orange nodes need to have their parent pointers set to point to their new parents.
Edit: to clarify a bit, think about it like this. In a purely functional language you can't modify anything, you can only create new nodes or copy them. So when you want to change the orange node, you actually make a copy of it with different data (the "change"). Now you need the green node to point to the orange node, which requires you to create a new orange node - this one pointing to the new green node. The same is true for the blue node.