Set Orderings Requiring Costliest Alphabetic Binary Trees
Authors:
- D. J. KleitmanDKD. J. Kleitman
- Michael E. SaksMSMichael E. Saks
- 1 June 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 2 (2) , 142-146
Abstract
It is shown that an ordering of a set with weighted elements which requires the most expensive alphabetic binary tree is a “sawtooth order.” For the set $\{ e_0 ,e_1 , \cdots ,e_t \}$, with the elements indexed from least to greatest weight, this order is $e_0 ,e_t ,e_1 ,e_{t - 1} , \cdots ,e_j ,e_{t - 1} , \cdots $. This result was conjectured by Hwang and leads to an upper bound on the cost of alphabetic binary trees.
Keywords
This publication has 7 references indexed in Scilit:
- Binary Trees Optimum Under Various CriteriaSIAM Journal on Applied Mathematics, 1979
- A New Algorithm for Minimum Cost Binary TreesSIAM Journal on Computing, 1977
- A New Proof of the T-C AlgorithmSIAM Journal on Applied Mathematics, 1973
- Coding Theory1973
- Optimal Computer Search Trees and Variable-Length Alphabetical CodesSIAM Journal on Applied Mathematics, 1971
- Variable-Length Binary EncodingsBell System Technical Journal, 1959
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952