In this paper we continue the study of the path length of trees with known fringe as initiated by Klein and Wood (1989) and De Santis and Persiano (1994). We compute the path length of the minimal tree with given number of leaves N and fringe Delta for the case Delta greater than or equal to N/2. This complements the result of De Santis and Persiano (1994) that studied the case Delta less than or equal to N/2. Our methods also yield a linear time algorithm for constructing the minimal tree when Delta greater than or equal to N/2. [References: 7]
展开▼
