| Title | Exponentially Decreasing Number of Operations in Balanced Trees |
| Authors | Lars Jacobsen, University of Southern
Denmark, Odense
Kim S. Larsen, University of Southern Denmark, Odense |
| Main Fields | 6. data types and structures |
| Other Main Fields | |
| Abstract + Keywords | 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. Keywords: Searchtrees, Exponentially
Decreasing Rebalancing,
|