algorithm - 二分木でノードを変更した場合の影響

Question

orange node次のツリーでを変更したいとします。

したがって、他に必要な変更は の だけleft pointerですgreen node。

はblue nodeそのままです。

私はどこか間違っていますか？この記事(ジッパーについて説明しています) によると、青色のノードも変更する必要があるためです。

同様に、同じ記事のこの図 (色を変更)では、(ノードを変更したときに) オレンジ色のノードをまったく変更するのはなぜxですか?

Answer 1

命令型言語では正しいです。緑色のノードのみを変更する必要があります。ただし、純粋に機能的なデータ構造の場合、これは当てはまりません。オレンジ色のノードを変更するには、緑色のノードを変更する必要があります。緑色のノードを変更したため、青色のノードを変更する必要があります (その他)。実際には、変更という言葉は正しくありません。実際には、関連するデータをコピーして新しいノードを作成しています。そのため、新しい青いノード (新しい緑のノードを指す) が作成されるほど、青いノードは変更されていません。

そうすることで永続性が維持されます。つまり、ツリーの以前の状態をすべて保存できます。オレンジ色のノードを変更する前とオレンジ色のノードを変更した後にツリーを保存する場合は、緑と青の両方を変更する必要があります。そうしないと、両方とも同じツリーのコピーになります。

2 番目のケースでも同じことが当てはまりますが、ここで親ポインターも変更する必要があります。ルート ノードを変更したので、すべてのオレンジ色のノードには、新しい親を指すように親ポインターを設定する必要があります。

編集：少し明確にするために、次のように考えてください。純粋に関数型の言語では、何も変更できません。新しいノードを作成するか、コピーすることしかできません。したがって、オレンジ色のノードを変更する場合は、実際には別のデータ (「変更」) を使用してそのコピーを作成します。ここで、緑色のノードがオレンジ色のノードを指す必要があります。これには、新しいオレンジ色のノードを作成する必要があります。これは、新しい緑色のノードを指します。青色のノードについても同様です。