Efficient Construction of Near-Optimal Binary and Multiway Search Trees

DOI10.1007/978-3-642-03367-4_21MaRDI QIDQ3183458zbMATH OpenOpenAlexFDO

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

• 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
• 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?)
• 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

(19)

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

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)