Confluently Persistent Deques via Data-Structural Bootstrapping
Report ID: TR-420-93Author: Buchsbaum, Adam L. / Tarjan, Robert E.
Date: 1993-03-00
Pages: 22
Download Formats: |Postscript|
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 Tarjan.
- This technical report has been published as
- Confluently Persistent Deques via Data-Structural Bootstrapping.
Adam L. Buchsbaum and Robert E. Tarjan,
- Proc. Fourth Annual ACM-SIAM Symp. on Discrete Alorithms (1993) 155-164 and
- J. Algorithms 18 (1995) 513-547.