Height Restricted Optimal Binary Trees
Copyright policy )Height Restricted Optimal Binary Trees
Summary: An algorithm that constructs an optimal height-restricted binary tree for a set of n weights in \(O(n^{3/2} L \log^{1/2} n)\) time, where L is the maximum permitted height, is presented. This is an improvement over the fastest previously known algorithm, which requires O(n 2 L) time. The algorithm is a hybrid, combining a technique by \textit{T. C. Hu} and \textit{K. C. Tan} [SIAM Appl. Math. 22, 225-234 (1972; Zbl 0239.94009)] with a technique by \textit{M. R. Garey} [SIAM J. Comput. 3, 101-110 (1974; Zbl 0288.68058)].
binary tree, Information storage and retrieval of data, Huffman coding, Analysis of algorithms and problem complexity, Searching and sorting, Theory of error-correcting codes and error-detecting codes
binary tree, Information storage and retrieval of data, Huffman coding, Analysis of algorithms and problem complexity, Searching and sorting, Theory of error-correcting codes and error-detecting codes
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).21 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!