Printable PDF
Department of Mathematics,
Department of Mathematics,
University of California San Diego
****************************
Math 269 - Combinatorics
T.C. Hu
UCSD
Optimum Alphabetic Binary Trees
Abstract:
Given a sequence of leaf nodes with positive weights, the optimumalphabetic binary tree can be constructed in O( nlogn) time in the worstcase and in O(n) time in most cases.The open question is: if the weight distribution is random,what percentageof cases be solved in linear time?
Host:
February 4, 2003
3:00 PM
AP&M 7321
****************************
