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

DOI10.1016/J.TCS.2007.12.015MaRDI QIDQ2481968zbMATH OpenOpenAlexFDO

Authors Jussi Kujala, Tapio Elomaa

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

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

Recommendations

• scientific article; zbMATH DE number 3868632
• New lower bounds on the cost of binary search trees
• scientific article; zbMATH DE number 2011834
• The estimated cost of a search tree on binary words
• Optimal binary search trees with costs depending on the access paths.
• An Approximation Algorithm for Binary Searching in Trees
• An approximation algorithm for binary searching in trees
• The amortized complexity of non-blocking binary search trees
• Expected Costs in Some Classes of Binary Search Trees
• Search cost for a nearly optimal path in a binary tree

Cites work

• scientific article; zbMATH DE number 1670671 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A note on some tree similarity measures
• Alternatives to splay trees with \(O(\log n)\) worst-case access times
• Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers
• Lower Bounds for Accessing Binary Search Trees with Rotations
• On paging with locality of reference
• 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
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Self-adjusting binary search trees
• Static optimality and dynamic search-optimality in lists and trees

Cited in

(2)

• Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees
• scientific article; zbMATH DE number 1670671 (Why is no real title available?)

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

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