A New Examination of Persistent Data Structures

Abstract

This thesis revisits algorithms for making pointer-based data structures persistent, specifically the node-copying and node-splitting algorithms developed in the late 1980s. A primary source of complexity in these algorithms is the necessity of maintaining inverse pointers from each node to its predecessors in the persistent data structure. One of the main focuses of this thesis is the role of these inverse pointers, with the ultimate goal of eliminating them from the data structure without affecting the amortized space and time bounds. Ultimately, we present a new, lazier algorithm derived from the original node-splitting algorithm which eliminates inverse pointers and runs in comparable space and time. We also present a simplified algorithm for the special case of making binary trees partially persistent, which takes advantage of the special structure of trees and partial persistence to eliminate amortization from the analysis and instead produce worst-case bounds.