Efficient random update on immutable tree

Question

I am making undoable data structure with immutable tree structure in C++. By sharing unchanged subnodes, I could derive new immutable tree pretty efficiently. Actually far more efficient than mutable tree when creating undo snapshot. However, I still need to recreate all nodes from root to updating target. This is affordable but I want to be better.

I looked Zipper structure. As far as I understand, Zipper is specialized for specific position of node, and needs restructuring if target point is changed. Would be more expensive because I need to update random node.

What kind of structure is available for my needs? More efficient random updating of immutable tree.

Update

As @SB mentioned, mutable structure with reverse operation would fit to my needs, but I want to avoid mutable structure due to hardness of debugging and keeping correctness of reverse operation. So I don't look for mutable approach anymore.

Answer 1

How about having 'forward list of changes'.

So when you want to modify the tree you simply append operation to the 'list of changes' without modifying the tree. Periodically you would apply entire set of changes in the 'list of changes' to the tree and create new tree snapshot. This is only possible if you can take into account changes in your 'list of changes' every time you traverse the tree. This way 'undo' is just removing item from the 'list of changes' most of the time.

Not knowing what you are doing with the tree it is diffucult to say whether this approach makes sense.

UPDATE: It appears that such structure was already invented. Take a look at Bw Tree