Making data structures persistent
James R. Driscoll, Neil Sarnak, Daniel D. Sleator et al. · 1986
This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version available for use. In contrast, a persistent structure allows access to any version, old or new, at any time. We develop simple, systematic, and effiient techniques for making linked data structures persistent. We use our techniques to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O(1) space bounds for insertion and deletion.
Cited by 687 works. doi:10.1145/12130.12142
Authors
References
- Data Structures and Network Algorithms
- Organization and maintenance of large ordered indexes
- A dichromatic framework for balanced trees
- Amortized Computational Complexity
- Binary Search Trees of Bounded Balance
- A new data structure for representing sorted lists
- Decomposable searching problems I. Static-to-dynamic transformation
- Fractional cascading: I. A data structuring technique
- Design and Analysis of a Data Structure for Representing Sorted Lists
- Planar point location using persistent search trees