Sequential access in splay trees takes linear time

DOI10.1007/BF02579253zbMath0587.68058DBLPjournals/combinatorica/Tarjan85OpenAlexW2078913074WikidataQ56066207 ScholiaQ56066207MaRDI QIDQ1072706

Robert Endre Tarjan

Publication date: 1985

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579253

zbMATH Keywords

dynamic optimality conjecturedynamically updated search treeoutput-restricted dequesself-adjusting binary search tree

Mathematics Subject Classification ID

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

• Unnamed Item
• Unnamed Item
• A note on some tree similarity measures
• Amortized Computational Complexity
• Self-adjusting binary search trees

This page was built for publication: Sequential access in splay trees takes linear time