On the sequential access theorem and deque conjecture for splay trees

DOI10.1016/j.tcs.2004.01.019zbMath1072.68034OpenAlexW2024924983WikidataQ56066205 ScholiaQ56066205MaRDI QIDQ1826644

Amr Elmasry

Publication date: 6 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.01.019

zbMATH Keywords

AlgorithmsData structuresCombinatorial problemsAmortized analysisSplay trees

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (7)

Greedy Is an Almost Optimal Deque ⋮ 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

Cites Work

• Sequential access in splay trees takes linear time
• On the deque conjecture for the splay algorithm
• Amortized Computational Complexity
• Self-adjusting binary search trees

This page was built for publication: On the sequential access theorem and deque conjecture for splay trees