DIMACS TR: 93-16
Confluently Persistent Deques via Data-Structural Bootstrapping
Authors: Adam L. Buchsbaum and Robert E. Tarjan
ABSTRACT
We introduce {\em 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.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-16.ps
DIMACS Home Page