Bounds for Weight Balanced Trees

J. Rissanen

IBM Journal of Research and Development · 1973 · 17 citations · 9 references

Concepts

Abstract

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.

References

9