On the public citation graph

Sequential access in splay trees takes linear time

https://doi.org/10.1007/bf02579253
0 signed · 75 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1016/0020-0190(82)90083-7openalex-snapshot
A note on some tree similarity measures
inferredcites →https://doi.org/10.1137/0606031openalex-snapshot
Amortized Computational Complexity
inferredcites →https://doi.org/10.1137/1.9781611970265openalex-snapshot
Data Structures and Network Algorithms
inferredcites →https://doi.org/10.1145/3828.3835openalex-snapshot
Self-adjusting binary search trees
inferredcites →https://doi.org/10.1145/800061.808752openalex-snapshot
Self-adjusting binary trees
inferredcites →https://doi.org/10.2307/2283757openalex-snapshot
The Art of Computer Programming. Volume 1: Fundamental Algorithms.
inferredcites →https://doi.org/10.2307/2552118openalex-snapshot
Computer Simulation Techniques.

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/jagm.1993.1045openalex-snapshot
On Rotations and the Generation of Binary Trees
inferred← citeshttps://doi.org/10.1006/jagm.1995.1026openalex-snapshot
Self-Adjusting k-ary Search Trees
inferred← citeshttps://doi.org/10.1007/0-387-25036-0_2openalex-snapshot
Problems in Data Structures and Algorithms
inferred← citeshttps://doi.org/10.1007/11940128_29openalex-snapshot
Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance
inferred← citeshttps://doi.org/10.1007/3-540-36136-7_19openalex-snapshot
Queaps
inferred← citeshttps://doi.org/10.1007/3-540-44985-x_5openalex-snapshot
Improved Upper Bounds for Pairing Heaps
inferred← citeshttps://doi.org/10.1007/3-540-51542-9_32openalex-snapshot
Self-adjusting k-ary search trees
inferred← citeshttps://doi.org/10.1007/3-540-53101-7_23openalex-snapshot
Globally partitionable attribute grammars
inferred← citeshttps://doi.org/10.1007/3-540-60692-0_60openalex-snapshot
Pattern matching in compressed texts
inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_263openalex-snapshot
O(log log n)‐competitive Binary Search Tree
inferred← citeshttps://doi.org/10.1007/978-1-4612-4808-8_36openalex-snapshot
Rotation Distance
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_263openalex-snapshot
O(log log n)-Competitive Binary Search Tree
inferred← citeshttps://doi.org/10.1007/978-3-030-19955-5_9openalex-snapshot
Belga B-Trees
inferred← citeshttps://doi.org/10.1007/978-3-030-24766-9_37openalex-snapshot
Splaying Preorders and Postorders
inferred← citeshttps://doi.org/10.1007/978-3-319-21840-3_13openalex-snapshot
Greedy Is an Almost Optimal Deque
inferred← citeshttps://doi.org/10.1007/978-3-540-45078-8_10openalex-snapshot
Distribution-Sensitive Binomial Queues
inferred← citeshttps://doi.org/10.1007/978-3-642-22300-6_35openalex-snapshot
Upper Bounds for Maximally Greedy Binary Search Trees
inferred← citeshttps://doi.org/10.1007/978-3-642-25011-8_17openalex-snapshot
A Unifying Property for Distribution-Sensitive Priority Queues
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_263-2openalex-snapshot
O(log logn)-Competitive Binary Search Tree
inferred← citeshttps://doi.org/10.1007/978-3-642-31833-7_9openalex-snapshot
Application of Sleator-Tarjan Dynamic Trees in a Monitoring System for the Arctic Region Based on Remote Sensing Data
inferred← citeshttps://doi.org/10.1007/978-3-642-33090-2_67openalex-snapshot
A Self-adjusting Data Structure for Multidimensional Point Sets
inferred← citeshttps://doi.org/10.1007/978-3-642-40273-9_10openalex-snapshot
A History of Distribution-Sensitive Data Structures
inferred← citeshttps://doi.org/10.1007/978-3-662-48350-3_26openalex-snapshot
Self-Adjusting Binary Search Trees: What Makes Them Tick?
inferred← citeshttps://doi.org/10.1007/978-981-15-5400-1_33openalex-snapshot
GMusic Player Using Self-adjusting Graph Data Structures
inferred← citeshttps://doi.org/10.1007/bf01191208openalex-snapshot
On the deque conjecture for the splay algorithm
inferred← citeshttps://doi.org/10.1007/bfb0029563openalex-snapshot
Self-organizing data structures
inferred← citeshttps://doi.org/10.1007/s00224-020-09991-8openalex-snapshot
Belga B-Trees
inferred← citeshttps://doi.org/10.1007/s00236-013-0180-8openalex-snapshot
On the hierarchy of distribution-sensitive properties for data structures
inferred← citeshttps://doi.org/10.1007/s10107-003-0436-0openalex-snapshot
Online algorithms: a survey
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90235-aopenalex-snapshot
Self-adjusting multi-way search trees
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50011-4openalex-snapshot
Data Structures
inferred← citeshttps://doi.org/10.1016/j.jda.2012.04.014openalex-snapshot
A priority queue with the time-finger property
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.01.019openalex-snapshot
On the sequential access theorem and deque conjecture for splay trees
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.03.002openalex-snapshot
A unified access bound on comparison-based dynamic dictionaries
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.12.020openalex-snapshot
A study on splay trees
inferred← citeshttps://doi.org/10.1016/s0020-0190(01)00230-7openalex-snapshot
Randomized splay trees: Theoretical and experimental results
inferred← citeshttps://doi.org/10.1016/s0927-0507(05)80204-xopenalex-snapshot
Chapter 7 Fundamental algorithms and data structures
inferred← citeshttps://doi.org/10.1109/focs.2004.23openalex-snapshot
Dynamic Optimality — Almost
inferred← citeshttps://doi.org/10.1109/focs.2015.32openalex-snapshot
Pattern-Avoiding Access in Binary Search Trees
inferred← citeshttps://doi.org/10.1109/sfcs.1986.28openalex-snapshot
Lower bounds for accessing binary search trees with rotations
inferred← citeshttps://doi.org/10.1109/sfcs.1989.63534openalex-snapshot
Twists, turns, cascades, deque conjecture, and scanning theorem
inferred← citeshttps://doi.org/10.1111/tgis.12754openalex-snapshot
A proposal to minimize the cost of processing big geospatial data in public cloud providers
inferred← citeshttps://doi.org/10.1137/0218004openalex-snapshot
Lower Bounds for Accessing Binary Search Trees with Rotations
inferred← citeshttps://doi.org/10.1137/0219060openalex-snapshot
Postorder Disjoint Set Union is Linear
inferred← citeshttps://doi.org/10.1137/1.9781611977073.75openalex-snapshot
Splay trees on trees
inferred← citeshttps://doi.org/10.1137/18m1195188openalex-snapshot
Smooth Heaps and a Dual View of Self-Adjusting Data Structures
inferred← citeshttps://doi.org/10.1137/s0097539705447347openalex-snapshot
Dynamic Optimality—Almost
inferred← citeshttps://doi.org/10.1137/s0097539797326988openalex-snapshot
On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n -Block Sequences
inferred← citeshttps://doi.org/10.1137/s009753979732699xopenalex-snapshot
On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
inferred← citeshttps://doi.org/10.1145/100216.100218openalex-snapshot
On the dynamic finger conjecture for splay trees
inferred← citeshttps://doi.org/10.1145/1005686.1005742openalex-snapshot
Performance analysis of BSTs in system software
inferred← citeshttps://doi.org/10.1145/156063.156067openalex-snapshot
Splaying a search tree in preorder takes linear time
inferred← citeshttps://doi.org/10.1145/327164.328803openalex-snapshot
On preorder splaying in binary search trees(abstract and references only)
inferred← citeshttps://doi.org/10.1145/3618260.3649631openalex-snapshot
Optimization with Pattern-Avoiding Input
inferred← citeshttps://doi.org/10.1145/3828.3835openalex-snapshot
Self-adjusting binary search trees
inferred← citeshttps://doi.org/10.1155/s0161171290000254openalex-snapshot
Splaying a search tree in preorder takes linear time
inferred← citeshttps://doi.org/10.1155/s0161171291000741openalex-snapshot
Splaying a search tree in preorder takes linear time
inferred← citeshttps://doi.org/10.1184/r1/6605009openalex-snapshot
Dynamic optimality and multi-splay trees
inferred← citeshttps://doi.org/10.17712/nsj.2017.1.20170006openalex-snapshot
Past, current and future
inferred← citeshttps://doi.org/10.22215/etd/2012-09696openalex-snapshot
Exploiting non-uniform query distributions in data structuring problems
inferred← citeshttps://doi.org/10.48550/arxiv.0707.2160openalex-snapshot
Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
inferred← citeshttps://doi.org/10.48550/arxiv.1102.4884openalex-snapshot
Upper Bounds for Maximally Greedy Binary Search Trees
inferred← citeshttps://doi.org/10.48550/arxiv.1503.03105openalex-snapshot
Self-Adjusting Binary Search Trees: What Makes Them Tick?
inferred← citeshttps://doi.org/10.48550/arxiv.1506.08319openalex-snapshot
Greedy Is an Almost Optimal Deque
inferred← citeshttps://doi.org/10.48550/arxiv.1603.04892openalex-snapshot
The landscape of bounds for binary search trees
inferred← citeshttps://doi.org/10.48550/arxiv.2108.05666openalex-snapshot
A coefficient related to splay-to-root traversal, correct to thousands of decimal places
inferred← citeshttps://doi.org/10.5555/1109557.1109600openalex-snapshot
O(log log n)-competitive dynamic binary search trees
inferred← citeshttps://doi.org/10.5555/365411.365522openalex-snapshot
Alternatives to splay trees with O(log n) worst-case access times
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.