Lopsided trees : algorithms and analyses

Abstract

Lopsided trees are rooted r-ary trees in which the length of the edge from a node to its ith child depends upon the value of i. A lopsided tree with n leaves is optimal if it has minimum esternal path length among all lopsided trees with n leaves. In this thesis we derive some new combinatorial properties of optimal lopsided trees. Knowing these properties will permit us to ⋅ Design an algorithm for constructing optimal trees that is more efficient than those previously known. ⋅ Analyze the asymptotic behavior of the cost of the optimal trees as a function of n, solving an open problem posed by Kapoor and Reingold who only analyzed the binary tree case (when r = 2).

Date of Award	1995
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology