Persistent Data Structures - Temporal Data Structures - Persistence (Time Travel)

The goal for Persistence is to remember everything. The data structure may be changed, but for persistence, all versions of the data structure (through their changes) are remembered, all old versions are kept, not destroyed. All data structure operations (like programming instructions on the data) are relative to the specified version. An update makes and returns a new version. For example, an insert to the data structure specifies a version and the output is a new version. Therefore, it is possible to go back to the old version and then modify that, where you would get a new version outputted again. There are 4 levels of persistence: 1. Partial Persistence (easiest) - only allowed to update the latest version (versions are linearly ordered, the old versions are never updated, so they can be queried). 2. Full Persistence - Update any version. The versions will form a tree because any of the old versions, when updated will branch off and start a new series of versions, once the next ones are updated. This can be recursive. 3. Confluent Persistence: Two versions can be combined to create a new version. The new versions form a DAG (Directed Acyclic Graph). If branches were created, versions at the branches can be recombined to merge the branches into a single branch. Hard to do. 4. Functional: Cannot modify anything (nodes). The only operation that is possible is to make new nodes.