Quick links

Confluently Persistent Deques via Data-Structural Bootstrapping

Report ID:
February 1993
Download Formats:


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.
  • Follow us: Facebook Twitter Linkedin