# The ICICS/CS Reading Room

## UBC CS TR-89-25 Summary

- No on-line copy of this technical report is available.

- Efficient Construction of Binary Trees with Almost Optimal Weighted Path Length, January 1989 David G. Kirkpatrick and Teresa Maria Przytycka
We present sequential and parallel algorithms to construct binary trees with almost optimal
weighted path length. Specifically, assuming that weights are normalized (to sum up to
one) and error refers to the (absolute) difference between the weighted path length of a
given tree and the optimal tree with the same weights, we present: an $O(\log n)$ time and
\n\( n \frac{\log \log n}{\log n} \)EREW processor algorithm which constructs a tree with error less than 0.172; an
$O(k \log n \log^{*} n)$ time and $n^{2}$ CREW processor algorithm which produces a tree with error at
most $ \frac{1}{n^{k}} $, and an $O(k^{2} \log n) $ time and $n^{2}$ CREW processor algorithm which produces a tree
\n\nwith error at most $\frac{1}{n^{k}} $ As well, we present two sequential algorithms: an $O(kn)$ time
algorithm which produces a tree with error at most $\frac{1}{n^{2^{k}}}$ and $O(kn)$ time algorithm which
produces a tree with error at most $ \frac{1}{2^{n^{2^{k}}}} $ .The last two algorithms use different computation
models.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.