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

DOI10.1016/J.TCS.2007.12.015zbMATH Open1136.68020OpenAlexW2009248926MaRDI QIDQ2481968FDOQ2481968

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

Recommendations

• scientific article
• 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

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)

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees

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)