The Optimal Alphabetic Tree Problem Revisited
Lawrence L. Larmore, Teresa M. Przytycka · Journal of Algorithms · 1998
TheOptimal Alphabetic Binary Tree(OABT) problem is equivalent to the Optimal Binary Search Tree problem where the weights are associated only with the leaves. The problem can be solved inO(n log n) time, while the best known lower bound is Ω(n). In this paper we relate the complexity of the problem to the complexity of priority queue operations and the complexity of sorting. We giveO(n log P(k))-time algorithm for the general OABT problem an-time algorithm for the integer OABT problem wherekis a number at most at large as the number of local minima,P(k) is the time complexity of priority queue insert/delete_min operation, andS(n) is the complexity of sorting in the given domain of weights. Our algorithms also give rise to linear time algorithms for some special cases.