Making data structures persistent (Q1117690)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Making data structures persistent |
scientific article |
Statements
Making data structures persistent (English)
0 references
1989
0 references
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.
0 references
persistent data structures
0 references
binary search trees
0 references