C++ で不変のツリー構造を持つ元に戻すことができるデータ構造を作成しています。変更されていないサブノードを共有することで、新しい不変ツリーをかなり効率的に派生させることができました。元に戻すスナップショットを作成するときは、可変ツリーよりもはるかに効率的です。ただし、ルートから更新ターゲットまでのすべてのノードを再作成する必要があります。これは手頃な価格ですが、もっと良くしたいです。
見た目はジッパー構造。私の知る限り、Zipper はノードの特定の位置に特化しており、ターゲット ポイントが変更された場合は再構築が必要です。ランダムノードを更新する必要があるため、より高価になります。
ニーズに合わせてどのような構造を利用できますか? 不変ツリーのより効率的なランダム更新。
アップデート
@SBが述べたように、リバース操作を伴う可変構造は私のニーズに合っていますが、デバッグの難しさとリバース操作の正確さを維持するために、可変構造は避けたいです。だから私はもう可変的なアプローチを探していません。