I've implemented a structural sharing algorithm for creating Clojure style persistent trees, but it relies on the child node knowing its own parent.
function fork return new Node children: this.children value: this.value parent: this.parent.fork()
Calling fork on a node in the tree will give you a new node, with a forked parent, recursively up until the root. This way you can take any node, change it and then have access to an immutable version of the whole tree.
However, the fundamental idea for this data structure is that it should be a directed acyclic graph, having a reference to a parent would give the graph cycles. I've also had some problems with creating the new parent. The node should know about the forked parent, but to fork the parent, it should know about its new child. This is pretty much a circular dependency, but I've managed to circumvent it with some references and mutation.
Is there a more sane way to do this?