Fringe thickness and maximum path length of binary trees

摘要

We show how to compute the maximum path length of binary trees with a given size and a given fringe thickness (the difference in length between a longest and a shortest root-to-leaf path). We demonstrate that the key to finding the maximum path length binary trees with size N and fringe thickness Delta is the height h(Delta,N) = [log(2)((N + 1)(2(Delta) - 1)/Delta)]. First we show that trees with height h(Delta,N) exist. Then we show that the maximum path length trees have height h(Delta,N) - 1, h(Delta,N), Or h(Delta,N) + 1. (C) 1998 Elsevier Science B.V. All rights reserved. [References: 8]