On the deque conjecture for the splay algorithm

DOI10.1007/BF01191208zbMath0753.68031DBLPjournals/combinatorica/Sundar92WikidataQ56066206 ScholiaQ56066206MaRDI QIDQ1193537

Rajamani Sundar

Publication date: 27 September 1992

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

rotationssearching binary search treestree reorganization

Mathematics Subject Classification ID

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

Related Items (13)

A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations ⋮ Greedy Is an Almost Optimal Deque ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ A unified access bound on comparison-based dynamic dictionaries ⋮ A direct algorithm for restricted rotation distance ⋮ An efficient algorithm for estimating rotation distance between two binary trees ⋮ A study on splay trees ⋮ Effective splaying with restricted rotations ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ A relationship between generalized Davenport-Schinzel sequences and interval chains ⋮ Right-arm rotation distance between binary trees ⋮ On the sequential access theorem and deque conjecture for splay trees

Cites Work

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

This page was built for publication: On the deque conjecture for the splay algorithm