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.
DIMACS Home Page