我正在使用 C++ 中的不可变树结构制作可撤销的数据结构。通过共享未更改的子节点，我可以非常有效地派生出新的不可变树。在创建撤消快照时实际上比可变树更有效。但是，我仍然需要重新创建从根到更新目标的所有节点。这是负担得起的，但我想做得更好。
我看了Zipper结构。据我了解，Zipper是专门针对节点的特定位置的，如果目标点发生变化，则需要重构。会更昂贵，因为我需要更新随机节点。
什么样的结构可以满足我的需求？不可变树的更有效随机更新。
更新
正如@SB 提到的，具有反向操作的可变结构会满足我的需求，但由于调试难度和保持反向操作的正确性，我想避免可变结构。所以我不再寻找可变方法。
最佳答案
“更改转发列表”如何？
因此，当您想要修改树时，您只需将操作附加到“更改列表”，而无需修改树。定期将“更改列表”中的整组更改应用于树并创建新的树快照。这只有在每次遍历树时都可以考虑到“更改列表”中的更改时才有可能。大多数情况下，“撤消”只是从“更改列表”中删除项目。
不知道你在用树做什么，很难说这种方法是否有意义。
更新:看来这种结构已经被发明出来了。看看Bw Tree
关于c++ - 不可变树的高效随机更新，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17936869/