Efficient Construction of Near-Optimal Binary and Multiway Search Trees

DOI10.1007/978-3-642-03367-4_21zbMATH Open1253.68102OpenAlexW122288055MaRDI QIDQ3183458FDOQ3183458

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

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

Mathematics Subject Classification ID

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

Cites Work

• A Mathematical Theory of Communication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Organization and maintenance of large ordered indexes
• Biased Search Trees
• Top-down syntax nalysis
• Two New Kinds of Biased Search Trees
• A New Algorithm for Minimum Cost Binary Trees
• Nearly optimal binary search trees
• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• On binary search trees
• Title not available (Why is that?)
• Optimum multiway search trees
• Optimal Multi-Way Search Trees
• Title not available (Why is that?)
• New lower bounds on the cost of binary search trees

Cited In (18)

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