Эффективное случайное обновление неизменного дерева
Я делаю отменяемую структуру данных с неизменяемой древовидной структурой в C ++. Разделяя неизмененные подузлы, я мог довольно эффективно получить новое неизменяемое дерево. На самом деле гораздо эффективнее, чем изменяемое дерево при создании снимка отмены. Однако мне все еще нужно воссоздать все узлы от корня до цели обновления. Это доступно, но я хочу быть лучше.
Я посмотрел структуру молнии. Насколько я понимаю, Zipper специализируется на конкретной позиции узла и нуждается в реструктуризации, если целевая точка изменяется. Было бы дороже, потому что мне нужно обновить случайный узел.
Какая структура доступна для моих нужд? Более эффективное случайное обновление неизменяемого дерева.
Обновить
Как упомянул @SB, изменяемая структура с обратной операцией подойдет для моих нужд, но я хочу избежать изменяемой структуры из-за сложности отладки и сохранения правильности обратной операции. Так что я больше не ищу изменчивый подход.
Решение
Как насчет «переслать список изменений».
Поэтому, когда вы хотите изменить дерево, вы просто добавляете операцию в «список изменений», не изменяя дерево. Периодически вы применяете весь набор изменений в «списке изменений» к дереву и создаете новый снимок дерева. Это возможно только в том случае, если вы можете учитывать изменения в «списке изменений» каждый раз, когда вы проходите по дереву. Таким образом, «отменить» большую часть времени просто удаляет элемент из «списка изменений».
Не зная, что вы делаете с деревом, трудно сказать, имеет ли этот подход смысл.
ОБНОВЛЕНИЕ: кажется, что такая структура уже была изобретена. Взгляни на Bw Tree
Другие решения
Других решений пока нет …