Garsia-Wachs Algorithm

The Garsia-Wachs algorithm is an efficient method for constructing an optimal binary search tree or an optimal alphabetic Huffman code, running in O(n log n), or linearithmic, time. Given a sequence of weights attached to items that must keep their given order, it builds a binary tree that minimizes the weighted sum of the external path lengths, which corresponds to building a binary search tree with the lowest expected search cost for ordered keys, or a variable-length binary code with the shortest expected length for coding those items in order. It was developed by Adriano Garsia and Michelle L. Wachs, who published it in 1977 in the SIAM Journal on Computing, simplifying an earlier method for the same problem due to T. C. Hu and Alan Tucker; the original proof of the algorithm's correctness was itself difficult, and was later simplified by other researchers, including work by Kingston in 1988 and by Karpinski, Larmore and Rytter in 1997. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/