Optimal Alphabetic Trees
Author:
- Alon ItaiAIAlon Itai
- 1 March 1976
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 5 (1) , 9-18
Abstract
An algorithm of Knuth for finding an optimal binary tree is extended in several directions to solve related problems. The first case considered is restricting the depth of the tree by some predetermined integer K, and a $Kn^2 $ algorithm is given. Next, for trees of degree $\sigma $, rather than binary trees, $Kn^2 \log \sigma $ and $n^2 \log \sigma $ algorithms are found for the restricted and nonrestricted cases, respectively. For alphabetic trees with letters of unequal cost, $\sigma ^2 n^2 $ algorithm is proposed. We conclude with a comparison of alphabetic and nonalphabetic trees and their respective complexities.
Keywords
This publication has 6 references indexed in Scilit:
- Optimal Binary Search Trees with Restricted Maximal DepthSIAM Journal on Computing, 1974
- A New Proof of the T-C AlgorithmSIAM Journal on Applied Mathematics, 1973
- Optimal Computer Search Trees and Variable-Length Alphabetical CodesSIAM Journal on Applied Mathematics, 1971
- Optimum binary search treesActa Informatica, 1971
- Minimum-redundancy coding for the discrete noiseless channelIEEE Transactions on Information Theory, 1961
- Variable-Length Binary EncodingsBell System Technical Journal, 1959