On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences

DOI10.1137/S0097539797326988MaRDI QIDQ4507338zbMATH OpenOpenAlexWikidataFDO

Authors Bud Mishra, Jeanette P. Schmidt, Richard Cole, Alan Siegel

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539797326988

zbMATH Keywords

amortized analysisbinary search treefinger search treesplay tree

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• On the sequential access theorem and deque conjecture for splay trees
• Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
• scientific article; zbMATH DE number 2050892
• On the deque conjecture for the splay algorithm
• Randomized splay trees: Theoretical and experimental results.
• Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees
• scientific article; zbMATH DE number 65701
• scientific article; zbMATH DE number 1953882
• scientific article; zbMATH DE number 1305510

Cited in

(22)

• On the deque conjecture for the splay algorithm
• Randomized splay trees: Theoretical and experimental results.
• A unified access bound on comparison-based dynamic dictionaries
• A study on splay trees
• Better analysis of binary search tree on decomposable sequences
• Layered working-set trees
• Maximum-weight planar boxes in \(O(n^2)\) time (and better)
• The cost of offline binary search tree algorithms and the complexity of the request sequence
• A history of distribution-sensitive data structures
• In pursuit of the dynamic optimality conjecture
• Rank-Sensitive Priority Queues
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Greedy is an almost optimal deque
• Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees
• Multi-Finger Binary Search Trees
• Smooth heaps and a dual view of self-adjusting data structures
• scientific article; zbMATH DE number 7651167 (Why is no real title available?)
• Belga B-trees
• Proximate point searching
• Competitive Online Search Trees on Trees
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying

This page was built for publication: On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences

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