- Exponentially Decreasing Number of Operations in Balanced Trees.
- Lars Jacobsen and Kim S. Larsen.
In 7th Italian Conference on Theoretical Computer Science (ICTCS), volume 2202 of Lecture Notes in Computer Science, pages 293-311. Springer, 2001.
While many tree-like structures have been proven
to support amortized constant number of operations after updates, considerably
fewer structures have been proven to support the more general exponentially
decreasing number of operations with respect to distance from the update. In
addition, all existing proofs of exponentially decreasing operations are
tailor-made for specific structures. We provide the first formalization of
conditions under which amortized constant number of operations imply
exponentially decreasing number of operations. Since our proof is
constructive, we obtain the constants involved immediately. Moreover, we
develop a number of techniques to improve these constants.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.