Confluently persistent deques via data structuaral bootstrapping
Adam L. Buchsbaum, Robert Endre Tarjan · Symposium on Discrete Algorithms · 1993
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 Tajan (in Proceedings 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1991, pp. 89-99).