Exponentially Decreasing Number of Operations in Balanced Trees

Lars Jacobsen, Kim Skak Larsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationTheoretical Computer Science, 7th Italian Conference, ICTCS 2001
Number of pages19
Publication date2001
Pages293-311
DOIs
Publication statusPublished - 2001
EventSeventh Italian Conference on Theoretical Computer Science - Torino, Italy
Duration: 4. Oct 20016. Oct 2001

Conference

ConferenceSeventh Italian Conference on Theoretical Computer Science
Country/TerritoryItaly
CityTorino
Period04/10/200106/10/2001
SeriesLecture Notes in Computer Science
Volume2202

Fingerprint

Dive into the research topics of 'Exponentially Decreasing Number of Operations in Balanced Trees'. Together they form a unique fingerprint.

Cite this