A Best Possible Bound for The Weighted Path Length of Binary Search Trees

Abstract

The weighted path length of optimum binary search trees is bounded above by $\sum \beta_i + 2\sum \alpha_j + H$ where H is the entropy of the frequency distribution, $\sum \beta _i $ is the total weight of the internal nodes, and $\sum \alpha_j$ is the total weight of the leaves. This bound is best possible. A linear time algorithm for constructing nearly optimal trees is described.