Эффекты изменения узла в двоичном дереве

Question

Предположим, я хочу изменить orange node в следующем дереве.

Итак, единственное другое изменение, которое мне нужно будет сделать, это в left pointergreen node.

blue node будет оставаться прежним.

Am Я не так-то? Потому что согласно this article (что объясняет zippers), даже синий узел необходимо изменить.

Точно так же, в этой картине (перекрасили) от same article, почему мы изменяем оранжевые узлы на всех (когда мы изменяем узел x)?

Answer 1

В императивном языке вы правильно, только зеленый узел должен быть изменен. Однако для чисто функциональных структур данных это не так. Чтобы изменить оранжевый узел, вам нужно изменить зеленый узел. Поскольку вы изменили зеленый узел, вам необходимо изменить синий узел (и так далее). Фактически слово изменено неверно, вы действительно копируете соответствующие данные и создаете новый узел. Таким образом, синий узел не изменяется, так как создается новый синий узел (который указывает на новый зеленый узел).

Выполнение этой задачи постоянство, что означает, что вы можете сохранить все предыдущие состояния дерева. Если вы хотите сохранить дерево перед изменением оранжевого узла и после изменения оранжевого узла вам потребуется изменить как зеленый, так и синий цвет, иначе оба будут копиями одного и того же дерева.

Во втором случае применяется то же самое, только теперь вам также необходимо изменить родительские указатели. Поскольку вы изменили корневой узел, все оранжевые узлы должны иметь свои родительские указатели, чтобы указать на своих новых родителей.

Редактировать: немного разъяснить, подумайте об этом. На чисто функциональном языке вы ничего не можете изменить, вы можете создавать только новые узлы или копировать их. Поэтому, когда вы хотите изменить оранжевый узел, вы на самом деле сделаете его копию с разными данными («изменение»). Теперь вам нужно, чтобы зеленый узел указывал на оранжевый узел, для чего вам нужно создать новый оранжевый узел, который указывает на новый зеленый узел. То же самое верно для синего узла.