The Optimal Alphabetic Tree Problem Revisited

✍ Scribed by Lawrence L Larmore; Teresa M Przytycka

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 202 KB
• Volume: 28
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1998.0934

✦ Synopsis

The Optimal 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 in O 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 give O n log P k -time Ž Ž .

. algorithm for the general OABT problem an O S n log k -time algorithm for ' the integer OABT problem where k is a number at most at large as the number of Ž . local minima, P k is the time complexity of priority queue insertrdelete min Ž . operation, and S 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.