Optimal binary search trees with costs depending on the access paths.

DOI10.1016/S0304-3975(02)00084-1MaRDI QIDQ1401195zbMATH OpenOpenAlexFDO

Authors Jayme L. Szwarcfiter, Gonzalo Navarro, Joísa de S. Oliveira, Walter Cunto, Ricardo Baeza-Yates, Nivio Ziviani

Publication date 17 August 2003

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

Full work available at URL https://doi.org/10.1016/s0304-3975(02)00084-1

zbMATH Keywords

AlgorithmsGenerating functionsOptimal binary search trees

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 2011834
• Optimal binary search trees
• Optimal search trees using two-way key comparisons
• Weighted Binary Trees for Concurrent Searching
• Expected Costs in Some Classes of Binary Search Trees

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A subquadratic algorithm for constructing approximately optimal binary search trees
• Binary searching with nonuniform costs and its application to text retrieval
• Heuristics for optimum binary search trees and minimum weight triangulation problems
• On binary searching with non-uniform costs
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Optimal binary search trees
• Optimum binary search trees

Cited in

(10)

• An approximation algorithm for binary searching in trees
• Optimal binary search trees
• Dynamic programming bi-criteria combinatorial optimization
• scientific article; zbMATH DE number 2011834 (Why is no real title available?)
• A new genetic approach to construct near-optimal binary search trees
• Operations research applications of dichotomous search
• The cost of offline binary search tree algorithms and the complexity of the request sequence
• On the Matter of Dynamic Optimality in an Extended Model for Tree Access Operations
• scientific article; zbMATH DE number 3909754 (Why is no real title available?)
• Expected Costs in Some Classes of Binary Search Trees

This page was built for publication: Optimal binary search trees with costs depending on the access paths.

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