About

A data structure is said to be persistent if it always preserves the previous version of itself when it is modified. The term “persistent data structure” was first introduced in Driscoll, Sarnak, Sleator, and Tarjans’ 1986 article

I first heard about persistent data structures while having a conversation with a former senior colleague. I got really curious and wanted to learn more about them! Erik Demaine’s lecture in MIT OCW was a good place to start.

Aim

The goal of this project was to understand “persistence” in data structures by implementing a partially persistent BST.
I achieve partial persistence using the “Fat Node” method as explained in the 1986 article

Implementation

Since partial persistence is a “read-only” persistence, the implementation is not that complicated.
In the fat node method, all changes are recorded in the fat node along with the version numbers, thereby allowing the nodes to become arbitrarily “fat”. Every time a previous version needs to be accessed, I simply return the values corresponding to that version in every fat node. If no values corresponding to a version are found, it can either mean that the node was never created or was deleted before that version.

In the above image, the BST is printed level-wise and None represents a NULL node.
Initially, there were 3 nodes in the BST with 5 as the root. Once 5 was deleted, 6 became the new root and parent of 4 was updated to 6. When I access a previous version (version 3 here), I can read what was the state in that previous version. Here, 5 was the root in version 3 of the tree and hence the BST before deleting node 5 is printed again.

What I learned

I learned about the different types of persistence in data structures - partial, full and confluent. I also learned about the different methods to implement persistence in data structures.