Bounds for Weight Balanced Trees
J. Rissanen · IBM Journal of Research and Development · 1973
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.