Algorithms and Data Structures · Senior · Question 38 of 75
What does structural sharing in persistent data structures give you?
- 1Data is shared between threads without any synchronization cost
- 2All versions share one mutable copy that's locked on write
- ✓Correct answer: New versions reuse unchanged parts, so updates don't copy everything
Explanation
Updating one leaf of a tree copies only the path to the root, O(log n), and old versions stay valid. Immutable updates in Redux, Immer and Clojure collections rely on this; it also makes === change checks cheap.