On the sequential access theorem and deque conjecture for splay trees

DOI10.1016/J.TCS.2004.01.019MaRDI QIDQ1826644zbMATH OpenOpenAlexWikidataFDO

Authors 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

AlgorithmsAmortized analysisCombinatorial problemsData structuresSplay trees

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• scientific article; zbMATH DE number 2050892
• Sequential access in splay trees takes linear time
• On the deque conjecture for the splay algorithm
• scientific article; zbMATH DE number 65701
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof

Cites work

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

Cited in

(14)

• Sequential access in splay trees takes linear time
• On the deque conjecture for the splay algorithm
• A priority queue with the time-finger property
• A unified access bound on comparison-based dynamic dictionaries
• On the hierarchy of distribution-sensitive properties for data structures
• A study on splay trees
• Greedy is an almost optimal deque
• scientific article; zbMATH DE number 2050892 (Why is no real title available?)
• On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees
• Smooth heaps and a dual view of self-adjusting data structures
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• Hardness amplification for dynamic binary search trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1826644)