Department of Computer Science

Technical Report No. 1, October 1987 - Abstract

Rolf Klein, Derick Wood:
On the Path Length of Binary Trees

This report is not available in electronic form!

We show that the external path length of a binary tree is closely related to the ratios of means of certain integers and establish the upper bound

External Path Length <= N*(log_2 N + Delta - log_2 Delta - 0.6623)

where N denotes the number of external nodes in the tree and Delta is the difference in length between a longest and a shortest path. Then we prove that this bound is (almost) achieved if N and Delta are arbitrary integers that satisfy Delta <= sqrt(N). If Delta > sqrt(N), we construct binary trees whose external path length is at least as large as

N*(log_2 N + Phi(N,Delta)*Delta - log_2 Delta - 4),

where

Phi(N,Delta) = (1 + Theta(Delta/N))^(-1).