The cost of offline binary search tree algorithms and the complexity of the request sequence

DOI10.1016/j.tcs.2007.12.015zbMath1136.68020MaRDI QIDQ2481968

Tapio Elomaa, Jussi Kujala

Publication date: 15 April 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.12.015

zbMATH Keywords

Kolmogorov complexity; splay trees; offline binary search tree algorithms

Mathematics Subject Classification ID

68P10: Searching and sorting

68R10: Graph theory (including graph drawing) in computer science

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

Related Items

Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on some tree similarity measures
• Static optimality and dynamic search-optimality in lists and trees
• Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers
• 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
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• On paging with locality of reference