A new algorithm for building alphabetic minimax trees

DOI10.3233/FI-2009-204MaRDI QIDQ3400581zbMATH OpenOpenAlexFDO

Authors Travis Gagie

Publication date 5 February 2010

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.5064

zbMATH Keywords

alphabetic minimax treesdata structures

Mathematics Subject Classification ID

Data structures (68P05) Formal languages and automata (68Q45)

Abstract: We show how to build an alphabetic minimax tree for a sequence (W = w_1, >..., w_n) of real weights in (O (n d log log n)) time, where $d$ is the number of distinct integers (lceil w_i ceil). We apply this algorithm to building an alphabetic prefix code given a sample.

Recommendations

• Alphabetic minimax trees in linear time
• Minimax trees in linear time with applications
• Partial alphabetic trees
• Minimax Trees in Linear Time with Applications
• scientific article; zbMATH DE number 437543

Cited in

(6)

• Operations research applications of dichotomous search
• Minimax trees in linear time with applications
• The Optimal Alphabetic Tree problem revisited
• Upper and Lower Bounds on Constructing Alphabetic Binary Trees
• Alphabetic minimax trees in linear time
• Old and new results on alphabetic codes

This page was built for publication: A new algorithm for building alphabetic minimax trees

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