Abstract
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) amortized time and space per deletion, where k is the total number of deque operations, and constant amortized time for other operations. This improves a previous result of Driscoll, Sleator, and Tarjan.
Original language | English (US) |
---|---|
Pages | 155-164 |
Number of pages | 10 |
State | Published - 1993 |
Externally published | Yes |
Event | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993 |
Other
Other | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
City | Austin, TX, USA |
Period | 1/25/93 → 1/27/93 |
All Science Journal Classification (ASJC) codes
- General Engineering