Efficient Construction of Near-Optimal Binary and Multiway Search Trees

DOI10.1007/978-3-642-03367-4_21MaRDI QIDQ3183458zbMATHOpenAlexFDO

Authors Prosenjit Bose, Karim Douïeb

Publication date 20 October 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-03367-4_21

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• On binary search trees
• Algorithms and Computation
• Optimal multiway split trees
• Optimal search trees using two-way key comparisons
• Assembling approximately optimal binary search trees efficiently using arithmetics

Cites work

• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 4210044 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 753967 (Why is no real title available?)
• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• A Mathematical Theory of Communication
• A New Algorithm for Minimum Cost Binary Trees
• Biased Search Trees
• Nearly optimal binary search trees
• New lower bounds on the cost of binary search trees
• On binary search trees
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Optimal Multi-Way Search Trees
• Optimum multiway search trees
• Organization and maintenance of large ordered indexes
• Top-down syntax nalysis
• Two New Kinds of Biased Search Trees

Cited in

(18)

• scientific article; zbMATH DE number 753967 (Why is no real title available?)
• Box-trees and R-trees with near-optimal query time
• Reflections on Optimal and Nearly Optimal Binary Search Trees
• An estimate of mean efficiency of search trees for arbitrary sets of binary words
• Efficient selection on a binary tree
• A new genetic approach to construct near-optimal binary search trees
• Efficient search algorithm on compact S-trees
• On batch-constructing B\(^{+}\)-trees: Algorithm and its performance evaluation
• The estimated cost of a search tree on binary words
• Building Optimal Binary Search Trees from Sorted Values in O(N) Time
• Efficient multiway radix search trees
• Obtaining Optimalk-Cardinality Trees Fast
• Algorithms and Computation
• Optimal Search Trees with 2-Way Comparisons
• A subquadratic algorithm for constructing approximately optimal binary search trees
• New dynamic construction techniques for M-tree
• Box-trees and R-trees with near-optimal query time
• Constructing a binary tree efficiently from its traversals

This page was built for publication: Efficient Construction of Near-Optimal Binary and Multiway Search Trees

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