A Best Possible Bound for the Weighted Path Length of Binary Search Trees
Lists
Only you see this
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...