Path copying shares unchanged subtrees between versions. If you update one leaf in a tree of nodes:
- Path length: for balanced trees
- New nodes created:
- Shared nodes:
After updates:
- Total nodes:
- Each version still has "logical" nodes
This is dramatically better than for full copies.
Here's the trick: immutability enables sharing. If a subtree never changes, all versions can point to the same physical subtree.