Explain the concept of Persistent Data Structures and their applications.

Instruction: Discuss what persistent data structures are, including their types (partially and fully persistent), and provide examples of their applications.

Context: Candidates are assessed on their knowledge of persistent data structures, which allow for accessing previous versions of themselves, and their ability to apply this concept in real-world applications.

Updated

Official Answer

A persistent data structure preserves earlier versions after an update. Here, persistence means access to versions, not necessarily storage that survives a process restart.

  • Partial persistence: read any version, but update only the latest version.
  • Full persistence: read any version and create a new version by updating any earlier one, permitting branches.

For example, path copying in an immutable binary search tree creates new nodes along the updated root-to-leaf path and shares unchanged subtrees. Keeping the old root preserves the old version. Updating an old root can create a separate branch without changing either existing version. Copying takes O(h) new nodes for a path of height h; a balanced structure needs its own balancing rules.

Useful applications include snapshots, undo, speculative computations and versioned indexes. The trade-off is allocation and retention of nodes still reachable from old versions. Concurrency, garbage collection and storage durability are separate design concerns.

A product's “version history” feature alone does not establish which persistence model its underlying data structure implements.

Source

Driscoll, Sarnak, Sleator and Tarjan: Making Data Structures Persistent.

Related Questions