Sequential access in splay trees takes linear time
From MaRDI portal
Publication:1072706
DOI10.1007/BF02579253zbMath0587.68058OpenAlexW2078913074WikidataQ56066207 ScholiaQ56066207MaRDI QIDQ1072706
Publication date: 1985
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579253
dynamic optimality conjecturedynamically updated search treeoutput-restricted dequesself-adjusting binary search tree
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (14)
Greedy Is an Almost Optimal Deque ⋮ Self-Adjusting Binary Search Trees: What Makes Them Tick? ⋮ A unified access bound on comparison-based dynamic dictionaries ⋮ On the hierarchy of distribution-sensitive properties for data structures ⋮ A priority queue with the time-finger property ⋮ A study on splay trees ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Self-adjusting multi-way search trees ⋮ On the deque conjecture for the splay algorithm ⋮ Belga B-trees ⋮ On the sequential access theorem and deque conjecture for splay trees ⋮ A History of Distribution-Sensitive Data Structures ⋮ Randomized splay trees: Theoretical and experimental results.
Cites Work
This page was built for publication: Sequential access in splay trees takes linear time
