Testing the optimality of alphabetic trees

AbstractIn this paper, we consider the worst-case time complexity of constructing optimal alphabetic trees. Hu and Tucker (1971) presented an O(n log n) algorithm for this problem in the linear decision tree model. On the other hand, there are only 2Θ(n different solutions (outputs) for this problem and, so, the only obvious lower bound in the decision tree model is Ω(n). One way to resolve this disparity is to consider the complexity of testing if a given alphabetic tree is optimal (for a given sequence of weights). Using the correctness of the Hu-Tucker algorithm, we derive the necessary and sufficient conditions on the weight sequence for a given tree to be optimal. These conditions are derived from the shape of the tree, level-by-level bottom-up. From this, it is easily seen that the optimality of very skewed trees (i.e. trees in which the number of nodes in each level is bounded by some constant) can be tested in linear time. We show that the optimality of well-balanced trees (i.e. trees in which the maximum difference between the levels of any two leaves is bounded by some constant) can also be tested in linear time. Finally, we consider a class of trees that is neither skewed nor well balanced, and discuss the difficulty and the issues involved in testing its optimality in linear time. It is not clear if the optimality of an arbitrary tree can be tested in linear time