# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### A best possible bound for the weighted path length of binary search trees

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Mehlhorn, K. (1977). A best possible bound for the weighted path length of binary search
trees.* SIAM Journal on Computing,* *6*, 235-239.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-AFA7-A

##### 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.