Sequential access in splay trees takes linear time

DOI10.1007/BF02579253MaRDI QIDQ1072706zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Robert E. Tarjan

Publication date 1985

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

dynamic optimality conjecturedynamically updated search treeoutput-restricted dequesself-adjusting binary search tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)

Recommendations

• On the sequential access theorem and deque conjecture for splay trees
• Self-adjusting binary search trees
• A new path from Splay to dynamic optimality
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• A study on splay trees

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• A note on some tree similarity measures
• Amortized Computational Complexity
• Self-adjusting binary search trees

Cited in

(23)

• Randomized splay trees: Theoretical and experimental results.
• scientific article; zbMATH DE number 140488 (Why is no real title available?)
• Self-adjusting multi-way search trees
• scientific article; zbMATH DE number 910910 (Why is no real title available?)
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• Self-adjusting binary search trees: what makes them tick?
• scientific article; zbMATH DE number 2050892 (Why is no real title available?)
• File maintenance: when in doubt, change the layout!
• On the deque conjecture for the splay algorithm
• A history of distribution-sensitive data structures
• A priority queue with the time-finger property
• A unified access bound on comparison-based dynamic dictionaries
• Belga B-trees
• On the hierarchy of distribution-sensitive properties for data structures
• Greedy is an almost optimal deque
• A new path from Splay to dynamic optimality
• scientific article; zbMATH DE number 65701 (Why is no real title available?)
• On the sequential access theorem and deque conjecture for splay trees
• Alternatives to splay trees with \(O(\log n)\) worst-case access times
• Inorder traversal of splay trees
• A study on splay trees
• Smooth heaps and a dual view of self-adjusting data structures

This page was built for publication: Sequential access in splay trees takes linear time

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