Making data structures persistent (Q1117690)

Making a change in an ordinary data structure destroys the old version, leaving only the new one. This paper investigates the problem of realizing persistent data structures in the sense that all the versions in the history of the data structure are available for use. Two kind of persistence are identified: partial persistence in which only the newest version may be updated and fully persistence in which an update operation may apply to any version. The authors study the case of linked data structures for which they propose two paradigms for making them persistent. These techniques are used to devise persistent forms of binary search trees with efficient implementations of the access, insertion and deletion operations.