A systematic analysis of splaying

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)

    Abstract

    In this paper we perform an amortized analysis of a functional program for splaying. We construct a potential function that yields the same bound for the amortized cost of splaying as given by D.D. Sleator and R.E. Tarjan - the inventors of splay trees. In addition, we show that this bound is minimal for the class of "sum of logs" potentials. Our approach also applies to the analysis of path reversal and pairing heaps.
    Original languageEnglish
    Pages (from-to)41-50
    JournalInformation Processing Letters
    Volume45
    Issue number1
    DOIs
    Publication statusPublished - 1993

    Fingerprint

    Dive into the research topics of 'A systematic analysis of splaying'. Together they form a unique fingerprint.

    Cite this