Optimal Binary Search Trees with Restricted Maximal Depth
Author:
- M. R. GareyMGM. R. Garey
- 1 June 1974
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 3 (2) , 101-110
Abstract
An algorithm is given for constructing a binary tree of minimum weighted path length for n nonnegative weights under the constraint that no path length exceed a given bound L. The number of operations required is proportional to $Ln^2 $. Such problems, which impose an additional constraint on the usual Huffman tree, arise in many applications, including computer file searching and the construction of optimal prefix codes under certain practical conditions.
Keywords
This publication has 8 references indexed in Scilit:
- Path Length of Binary Search TreesSIAM Journal on Applied Mathematics, 1972
- Optimal Computer Search Trees and Variable-Length Alphabetical CodesSIAM Journal on Applied Mathematics, 1971
- Codes based on inaccurate source probabilitiesIEEE Transactions on Information Theory, 1971
- Optimum binary search treesActa Informatica, 1971
- Generating a canonical prefix encodingCommunications of the ACM, 1964
- Minimum-redundancy coding for the discrete noiseless channelIEEE Transactions on Information Theory, 1961
- Variable-Length Binary EncodingsBell System Technical Journal, 1959
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952