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