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

Kurt Mehlhorn

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.
BibTeX
@article{mehlhorn1977best,
  author = {Kurt Mehlhorn},
  title = {{A Best Possible Bound for the Weighted Path Length of Binary Search Trees}},
  journal = {SIAM Journal on Computing},
  year = {1977},
  doi = {10.1137/0206017},
}

Loading related content...

Figure