On the deque conjecture for the splay algorithm

DOI10.1007/BF01191208MaRDI QIDQ1193537zbMATH OpenDBLPWikidataFDO

Authors Rajamani Sundar

Publication date 27 September 1992

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

rotationssearching binary search treestree reorganization

Mathematics Subject Classification ID

Data structures (68P05) Combinatorics in computer science (68R05)

Recommendations

• On the sequential access theorem and deque conjecture for splay trees
• Sequential access in splay trees takes linear time
• A new path from Splay to dynamic optimality
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• scientific article; zbMATH DE number 65701

Cites work

• A note on some tree similarity measures
• Amortized Computational Complexity
• Lower Bounds for Accessing Binary Search Trees with Rotations
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Self-adjusting binary search trees
• Sequential access in splay trees takes linear time

Cited in

(17)

• Right-arm rotation distance between binary trees
• Stacks, queues, and deques with order-statistic operations
• On the sequential access theorem and deque conjecture for splay trees
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• A unified access bound on comparison-based dynamic dictionaries
• A direct algorithm for restricted rotation distance
• A study on splay trees
• A relationship between generalized Davenport-Schinzel sequences and interval chains
• Greedy is an almost optimal deque
• Three generalizations of Davenport-Schinzel sequences
• Effective splaying with restricted rotations
• 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
• Smooth heaps and a dual view of self-adjusting data structures
• An efficient algorithm for estimating rotation distance between two binary trees
• 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 deque conjecture for the splay algorithm

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