The power and limitations of static binary search trees with lazy finger

DOI10.1007/s00453-016-0224-xzbMath1352.68070arXiv1304.6897OpenAlexW1793615280MaRDI QIDQ727988

Karim Douïeb, Stefan Langerman, John Iacono, Prosenjit Bose, Presenjit Bose

Publication date: 21 December 2016

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.6897

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items

Unnamed Item ⋮ Unnamed Item ⋮ Belga B-trees ⋮ Multi-Finger Binary Search Trees ⋮ In Pursuit of the Dynamic Optimality Conjecture ⋮ Competitive Online Search Trees on Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearly optimal binary search trees
• Preserving order in a forest in less than logarithmic time and linear space
• Randomized search trees
• Worst-case optimal tree layout in external memory
• Optimum binary search trees
• A locality-preserving cache-oblivious dynamic dictionary
• Self-adjusting binary search trees
• Lower Bounds for Accessing Binary Search Trees with Rotations
• How to Pack Trees
• 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
• Combining Binary Search Trees