DIMACS TR: 93-16

Confluently Persistent Deques via Data-Structural Bootstrapping

Authors: Adam L. Buchsbaum and Robert E. Tarjan


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