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

Question

Я делаю отменную структуру данных с неизменной структурой дерева в C++. Делясь неизмененными субномами, я мог бы получить новое неизменяемое дерево довольно эффективно. На самом деле гораздо эффективнее, чем изменяемое дерево при создании моментального снимка отмены. Тем не менее, мне все равно нужно воссоздать все узлы от root до обновления целевого объекта. Это доступно, но я хочу быть лучше.

Я смотрел структуру застежки -молнии. Насколько я понимаю, Zipper специализируется на конкретной позиции узла и нуждается в реструктуризации, если целевая точка изменена. Было бы дороже, потому что мне нужно обновить случайный узел.

Какая структура доступна для моих нужд? Более эффективное случайное обновление неизменяемого дерева.

Update

Как уже упоминался @SB, изменяемая структура с обратной операцией будет соответствовать моим потребностям, но я хочу, чтобы избежать изменяемых структур из-за твердости отладки и поддержание корректности обратной операции. Поэтому я больше не ищу изменчивого подхода.

Answer 1

Как насчет наличия «пересылаемого списка изменений».

Поэтому, когда вы хотите изменить дерево, вы просто добавляете операцию в «список изменений» без изменения дерева. Периодически вы должны применить весь набор изменений в «списке изменений» к дереву и создать новый снимок дерева. Это возможно только в том случае, если вы можете принимать во внимание изменения в вашем «списке изменений» каждый раз, когда вы пересекаете дерево. Этот способ «отменить» просто удаляет элемент из «списка изменений» большую часть времени.

Не зная, что вы делаете с деревом, сложно сказать, имеет ли этот подход смысл.

ОБНОВЛЕНИЕ: Похоже, что такая конструкция уже была изобретена. Посмотрите на Bw Tree