Reflections on Optimal and Nearly Optimal Binary Search Trees

DOI10.1007/978-3-642-03456-5_7MaRDI QIDQ3644717zbMATH OpenOpenAlexFDO

Authors J. Ian Munro

Publication date 12 November 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03456-5_7

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Optimal binary search trees
• Optimal binary search trees
• A subquadratic algorithm for constructing approximately optimal binary search trees
• scientific article; zbMATH DE number 2011834
• Optimal Search Trees with 2-Way Comparisons

Cites work

• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• A Method for the Construction of Minimum-Redundancy Codes
• A New Algorithm for Minimum Cost Binary Trees
• Efficient Construction of Near-Optimal Binary and Multiway Search Trees
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3490460 (Why is no real title available?)
• scientific article; zbMATH DE number 3497801 (Why is no real title available?)
• scientific article; zbMATH DE number 3607502 (Why is no real title available?)
• scientific article; zbMATH DE number 3390245 (Why is no real title available?)
• Nearly optimal binary search trees
• New lower bounds on the cost of binary search trees
• On binary search trees
• On the costs of optimal and near-optimal binary search trees
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Optimum binary search trees
• Recognition and parsing of context-free languages in time n3

Cited in

(12)

• The optimal binary search tree for Andersson's search algorithm
• Box-trees and R-trees with near-optimal query time
• Smoothed analysis of binary search trees
• Optimal Search Trees with 2-Way Comparisons
• The Expected Performance of Traversal Algorithms in Binary Trees
• A subquadratic algorithm for constructing approximately optimal binary search trees
• Lower Bounds for Accessing Binary Search Trees with Rotations
• Box-trees and R-trees with near-optimal query time
• Building Optimal Binary Search Trees from Sorted Values in O(N) Time
• scientific article; zbMATH DE number 5237331 (Why is no real title available?)
• Optimal binary search trees
• Binary search trees of almost optimal height

This page was built for publication: Reflections on Optimal and Nearly Optimal Binary Search Trees

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