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

Question

假设我想改变 orange node 在下面的树中。

所以，我需要做的唯一的其他改变是 left pointer 的 green node.

这 blue node 将保持不变。

我有什么地方说错了吗？ 因为根据 本文 （这解释了 拉链），连蓝色节点也需要改变。

同样，在这张图片（重新着色）中 同一篇文章, 为什么我们要改变橙色节点（当我们改变节点 x)?

Answer 1

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

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

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

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