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

Question

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

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

将blue node保持不变。

我在某个地方错了吗？因为根据这篇文章（解释zippers），即使是蓝色节点也需要更改。

同样，在同一篇文章的这张图片（重新着色）中，为什么我们要更改橙色节点（当我们更改节点时x）？

Answer 1

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

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

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

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