Persistent data structures

This thesis discusses persistent data structures, that is structures which preserve their own history. We focus on pointer-based structures, where it is possible to reach both full and partial persistence in constant amortized time and space per operation. Persistent arrays are also discussed, but the existence of optimal persistent arrays remains an open problem. We also include specific applications of the general techniques and also examples of use of persistent data structures