Persistence, amortization and randomization
Paul F. Dietz, Rajeev Raman · UR Research (University of Rochester) · 1991
We explore several problems associated with persistent data structures, deriving our motivation from problems left open by Driscoll, Sarnak, Sleator and Tarjan in [15]. We exhibit simple methods to completely eliminate amortization from one of the data structures of Driscoll et. al.. We show new methods for making some data structures, including disjoint-set union-find, partially persistent in optimal time and space. We discuss some motivations for eliminating amortization from data structures in general, and explore a family of "pebble" games associated with eliminating amortization from data structures in general and from persistent data structures in particular. One relevant version of this pebble game shows that randomization may be a useful tool for elimination of amortization. The