Persistent Data Structures

Path Copying & Structural Sharing

1:00

How path copying and structural sharing let every update produce a new version in O(log n) time while keeping all past versions alive and queryable.

By the end, you can

Explain the difference between storage durability ("disk persistence") and version persistence.
Describe structural sharing and explain why shared nodes must be immutable.
Trace a path-copying update on a balanced tree, identifying which nodes are copied and which are shared.
Calculate the number of new nodes created by one update given n and the tree height.
Distinguish partial, full, and confluent persistence and rank them by capability.
Explain why the naive deep-copy approach costs O(n) while path copying costs O(log n).
Identify real-world applications: undo/redo systems, Git-style versioning, and persistent segment trees.

Up next in Advanced Data Structures