algorithm - 更改二叉树中节点的影响

Question

假设我想更改以下树中的 orange 节点。

因此，我唯一需要做的其他更改是 green node 的 left pointer。

蓝色节点将保持不变。

我哪里错了吗？ 因为根据 this article (这解释了 zippers )，甚至需要更改蓝色节点。

同样，在这张来自 same article 的图片(重新着色)中，为什么我们要更改橙色节点(当我们更改节点 x 时)？

Answer 1

在命令式语言中，您是正确的，只需要更改绿色节点。然而，对于纯功能数据结构，情况并非如此。为了更改橙色节点，您需要更改绿色节点。因为您更改了绿色节点，所以您需要更改蓝色节点(依此类推)。实际上改变这个词是不正确的，你实际上是在复制相关数据并创建一个新节点。所以蓝色节点并没有被改变太多，因为一个新的蓝色节点(指向新的绿色节点)正在被创建。

这样做可以保持持久性，这意味着您可以存储树的所有先前状态。如果您想在更改橙色节点之前和更改橙色节点之后存储树，则需要同时更改绿色和蓝色 - 否则两者将是同一棵树的副本。

在第二种情况下，同样适用，只是现在您还需要更改父指针。由于您已经更改了根节点，因此所有橙色节点都需要将其父节点指针设置为指向它们的新父节点。

编辑:澄清一点，这样想。在纯函数式语言中，您不能修改任何内容，只能创建新节点或复制它们。因此，当您想要更改橙色节点时，实际上是用不同的数据(“更改”)制作了它的副本。现在你需要绿色节点指向橙色节点，这需要你创建一个新的橙色节点——这个指向新的绿色节点。蓝色节点也是如此。