Assembling approximately optimal binary search trees efficiently using arithmetics

DOI10.1016/J.IPL.2008.08.012zbMATH Open1202.68118OpenAlexW1967146916MaRDI QIDQ989540FDOQ989540

Authors: Jussi Kujala 

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.08.012

Recommendations

• A subquadratic algorithm for constructing approximately optimal binary search trees
• scientific article; zbMATH DE number 1524355
• Algorithms and Computation
• Construction of optimal binary split trees in the presence of bounded access probabilities
• On binary search trees

zbMATH Keywords

data structuresapproximation algorithmsentropy boundsbinary search treesi/o cost models

Mathematics Subject Classification ID

Data structures (68P05) Approximation algorithms (68W25)

Cites Work

• Introduction to algorithms
• Cache-oblivious algorithms
• Arithmetic Coding
• Cache-oblivious string dictionaries
• Title not available (Why is that?)
• Nearly optimal binary search trees
• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• New bounds on the expected length of one-to-one codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• A lower bound on the expected length of one-to-one codes

Cited In (10)

• Building Optimal Binary Search Trees from Sorted Values in O(N) Time
• Efficient reorganization of binary search trees
• Title not available (Why is that?)
• An estimate of mean efficiency of search trees for arbitrary sets of binary words
• Title not available (Why is that?)
• A subquadratic algorithm for constructing approximately optimal binary search trees
• Algorithms and Computation
• A new genetic approach to construct near-optimal binary search trees
• Efficient Construction of Near-Optimal Binary and Multiway Search Trees
• A strategy for searching with different access costs.

This page was built for publication: Assembling approximately optimal binary search trees efficiently using arithmetics

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