The weighted path length of optimum binary search trees is bounded above by ∑ βᵢ + 2∑ αⱼ + H where H is the entropy of the frequency distribution, ∑ β ᵢ is the total weight of the internal nodes, and ∑ αⱼ is the total weight of the leaves. This bound is best possible. A linear time algorithm for constructing nearly optimal trees is described.
No takes yet. Share an insight, caveat, or question.
Kurt Mehlhorn (1977) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: