Making data structures persistent

From MaRDI portal





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.




Cited in
(only showing first 100 items - show all)








This page was built for publication: Making data structures persistent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1117690)