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

DOI10.1016/j.tcs.2007.12.015zbMath1136.68020OpenAlexW2009248926MaRDI 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 complexitysplay treesoffline binary search tree algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (1)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The cost of offline binary search tree algorithms and the complexity of the request sequence