Confluently persistent deques via data-structural bootstrapping

Adam L. Buchsbaum, Robert Endre Tarjan

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

We introduce data-structural bootstrapping, a technique to design data structures recursively, and use it to design confluently persistent deques. Our data structure requires O(log* k) worst-case time and space per deletion, where k is the total number of deque operations, and constant worst-case time and space for other operations. Further, the data structure allows a purely functional implementation, with no side effects. This improves a previous result of Driscoll, Sleator, and Tajan (in “Proceedings 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1991,„ pp. 89-99).

Original languageEnglish (US)
Pages (from-to)513-547
Number of pages35
JournalJournal of Algorithms
Volume18
Issue number3
DOIs
StatePublished - Jan 1 1995

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Confluently persistent deques via data-structural bootstrapping'. Together they form a unique fingerprint.

  • Cite this