Making data structures persistent
作者： J R Driscoll , N Sarnak , D D Sleator , R E Tarjan
DOI: 10.1145/12130.12142
关键词:
摘要: Abstract This paper is a study of persistence in data structures. Ordinary structures are ephemeral the sense that change to structure destroys old version, leaving only new version available for use. In contrast, persistent allows access any or new, at time. We develop simple, systematic, and efficient techniques making linked persistent. use our devise forms binary search trees with logarithmic access, insertion, deletion times O (1) space bounds insertion deletion.
acm.org
princeton.edu
core.ac.uk
cglab.ca参考文章(31)
Neil Ivor Sarnak, Persistent data structures New York University. ,(1986)
Scott Huddleston, Kurt Mehlhorn, Robust Balancing in B-Trees Theoretical Computer Science. pp. 234- 244 ,(1981) , 10.1007/BFB0017315
Robert Endre Tarjan, Data Structures and Network Algorithms ,(1983)
M.H. Overmars, Searching in the past I Unknown Publisher. ,(1981)
Bernard Chazelle, Leonidas J. Guibas, Fractional Cascading: A Data Structuring Technique with Geometric Applications international colloquium on automata, languages and programming. pp. 90- 100 ,(1985) , 10.1007/BFB0015734
Jon Louis Bentley, James B Saxe, Decomposable searching problems I. Static-to-dynamic transformation Journal of Algorithms. ,vol. 1, pp. 301- 358 ,(1980) , 10.1016/0196-6774(80)90015-2
Richard Cole, Searching and Storing Similar Lists ,(2011)
Robert Endre Tarjan, Amortized Computational Complexity Siam Journal on Algebraic and Discrete Methods. ,vol. 6, pp. 306- 318 ,(1985) , 10.1137/0606031
Eugene W Myers, None, An applicative random-access stack☆ Information Processing Letters. ,vol. 17, pp. 241- 248 ,(1983) , 10.1016/0020-0190(83)90106-0
S. Rao Kosaraju, Localized search in sorted lists Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. pp. 62- 69 ,(1981) , 10.1145/800076.802458