Concepedia

Splay Tree Analysis

Splay Tree Analysis is a method in amortized analysis that evaluates the efficiency of splay trees by accounting for the aggregate cost of a sequence of operations, distinguishing itself through its use of potential functions to demonstrate that self-adjusting binary search trees achieve logarithmic amortized time complexity despite individual operations potentially requiring linear time.

20

Publications

2.2K

Citations

30

Authors

18

Institutions

Publications per year

2017–2026

0

Parents

Publications

20

Self-adjusting binary search trees

Daniel D. Sleator, Robert E. Tarjan · Journal of the ACM · 1985 · 1.2K citations · Full text

, , +14

Baggy bounds checking: an efficient and backwards-compatible defense against out-of-bounds errors

Periklis Akritidis, Manuel Costa, Miguel Castro et al. · 2009 · 217 citations

, , +12

A comparative study of parallel and sequential priority queue algorithms

Robert Rönngren, Rassul Ayani · ACM Transactions on Modeling and Computer Simulation · 1997 · 119 citations

, , +17

On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof

Richard Cole · SIAM Journal on Computing · 2000 · 104 citations

, , +12

Sequential access in splay trees takes linear time

Robert E. Tarjan · COMBINATORICA · 1985 · 86 citations

, , +7

1–5 of 20

Authors

30

  1. RC
    Richard Cole

    New York University, United States

    3 publications · 228 citations

    3

    h-index

  2. SZ
    Safaa Zeidan

    United Arab Emirates University, United Arab Emirates

    2 publications · 44 citations

    2

    h-index

  3. GE
    Gary Eddy

    The University of Melbourne, Australia

    2 publications · 39 citations

    2

    h-index

  4. ZT
    Zouheir Trabelsi

    United Arab Emirates University, United Arab Emirates

    2 publications · 44 citations

    2

    h-index

  5. RE
    Robert E. Tarjan

    Princeton University, United States

    2 publications · 1.3K citations

    2

    h-index

1–5 of 30

Institutions

18

  1. New York University

    New York, United States

    3 h-index

    3 publications

    138 citations

  2. The University of Melbourne

    Melbourne, Australia

    2 h-index

    4 publications

    78 citations

  3. United Arab Emirates University

    Al Ain, United Arab Emirates

    2 h-index

    6 publications

    120 citations

  4. University of Crete

    Rethymno, Greece

    2 h-index

    2 publications

    33 citations

  5. Courant Institute of Mathematical Sciences

    New York, United States

    2 h-index

    2 publications

    62 citations

  6. Lund University

    Lund, Sweden

    2 h-index

    2 publications

    39 citations

  7. AT&T (United States)

    Bedminster, United States

    2 h-index

    3 publications

    2.6K citations

  8. TU Dortmund University

    Dortmund, Germany

    1 h-index

    1 publications

    28 citations

1–8 of 18

Venues

  1. SIAM Journal on Computing

    3 publications · 194 citations

    3

    h-index

  2. Information Processing Letters

    2 publications · 47 citations

    2

    h-index

  3. COMBINATORICA

    2 publications · 123 citations

    2

    h-index

  4. Software Practice and Experience

    2 publications · 39 citations

    2

    h-index

  5. ACM Transactions on Modeling and Computer Simulation

    TOMACS · 1 publications · 119 citations

    1

    h-index

1–5