IBM Journal of Research and Development · 1973 · 17 citations · 9 references
Natural SciencesMathematicsAlgorithmsDecision TheoryProbability TheoryCombinatorial OptimizationDecision TreesEntropyProbabilistic CombinatoricsProbability InequalitiesBalanced Binary Search TreesBounding FunctionsEntropy Bounds
It has been shown that the cost W of a weight balanced binary tree satisfies the inequalities, H ≤ W ≤ H + 3, where H is the entropy of the set of the leaves. For a class of “smooth” distributions the inequalities, H ≤ W ≤ H + 2, are derived. These results imply that for sets with large entropy the search times provided by such trees cannot be substantially shortened when binary decisions are being used.
9
A Mathematical Theory of Communication
Claude E. Shannon · Bell System Technical Journal · 1948 · 80.7K citations
<i>Transmission of Information</i>
Robert M. Fano, W. T. Wintringham · Physics Today · 1961 · 540 citations
Donald E. Knuth · Acta Informatica · 1971 · 448 citations
Variable-Length Binary Encodings
E. N. Gilbert, E. F. Moore · Bell System Technical Journal · 1959 · 359 citations