History Overview

Optimal alphabetic binary trees have been studied for a long time. E. N. Gilbert and E. F. Moore first devised an algorithm for building such trees with running time O(n³) in 1959. Later, in 1962, Knuth constructed another algorithm, improving the running time to O(n²). The best time complexity, $O(n\lg n)$, for building optimal alphabetic binary trees is achieved by two algorithms: Hu-Tucker and Garsia-Wachs. T. C. Hu, jointly with A. C. Tucker, published for the first time in 1971 description of the algorithm in [HT71]. A. M. Garsia and M. L. Wachs published their algorithm in [GW77]. The two algorithms are quite similar. Both algorithms consist of three phases. During the first phase they construct an optimal tree, which is not alphabetic. The levels of the terminal nodes in the optimal tree are used to reconstruct another tree which is alphabetic, thus preserving the initial order of the terminal nodes, and also the cost of the tree constructed during the first phase. The two algorithms differ in a way they build the tree in the first phase. The reconstruction phase is the same. The Hu-Tucker algorithm was implemented by J. M. Yohe in Algol 60. Publication of the implementation appears in [Yoh72]. The running time he achieved is O(n²). The Garsia-Wachs algorithm was implemented by R. E. Tarjan in $O(n\lg n)$ time and can be found in [GW77].

B. M. Mumey introduced the idea for finding optimal alphabetic binary tree in linear time for some special classes of inputs in [Mum92]. One example is a simple case solvable in O(n) time when the values of the weights in the initial sequence are all within a factor of two. Mumey showed that the region-based method, described in [Mum92], exhibits $o(n\lg n)$ time performance for a significant variety of inputs. Linear time solutions were discovered for the following special cases: when the input sequence of nodes is sorted sequence, bitonic sequence, weights exponentially separated, and weights within a constant factor, see [LP98] for references.

A parallel construction of optimal alphabetic binary trees is presented by L. L. Larmore, T. M. Przytycka, and W. Rytter in [LPR93]. The algorithm is a parallelization of Garsia-Wachs algorithm and runs in $O(\lg ^3 n)$ time with $n^2 \lg n$ processors. This thesis is concerned with the general case of building optimal alphabetic binary search tree, when the input sequence of nodes does not exhibit any special properties.