Alternatives to splay trees with O(log n) worst-case access times

John Iacono

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Splay trees are a self adjusting form of search tree that supports access operations in &Ogr;(log n) amortized time. Splay trees also have several amazing distribution sensitive properties, the strongest two of which are the working set theorem and the dynamic finger theorem. However, these two theorems are shown to poorly bound the performance of splay trees on some simple access sequences. The unified conjecture is presented, which subsumes the working set theorem and dynamic finger theorem, and accurately bounds the performance of splay trees over some classes of sequences where the existing theorems' bounds are not tight. While the unified conjecture for splay trees is unproven, a new data structure, the unified structure, is presented where the unified conjecture does hold. This structure also has a worst case of &Ogr;(log n) per operation, in contrast to the &Ogr;(n) worst case runtime of splay trees. A second data structure, the working set structure, is introduced. The working set structure has the same performance attributed to splay trees through the working set theorem, except the runtime is worst case per operation rather than amortized.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
    Pages516-522
    Number of pages7
    StatePublished - 2001
    Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
    Duration: Apr 30 2001May 1 2001

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other2001 Operating Section Proceedings, American Gas Association
    CountryUnited States
    CityDallas, TX
    Period4/30/015/1/01

    Keywords

    • Algorithms
    • Performance
    • Theory
    • Verification

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Alternatives to splay trees with O(log n) worst-case access times'. Together they form a unique fingerprint.

    Cite this