TheGarsia–Wachs algorithm is an efficient method for computers to constructoptimal binary search trees andalphabetic Huffman codes, inlinearithmic time. It is named afterAdriano Garsia andMichelle L. Wachs.

The input to the problem, for an integer${\displaystyle n}$, consists of a sequence of${\displaystyle n+1}$ non-negative weights${\displaystyle w_0,w_1,\dots ,w_n}$. The output is a rootedbinary tree with${\displaystyle n}$ internal nodes, each having exactly two children. Such a tree has exactly${\displaystyle n+1}$ leaf nodes, which can be identified (in the order given by the binary tree) with the${\displaystyle n+1}$ input weights.The goal of the problem is to find a tree, among all of the possible trees with${\displaystyle n}$ internal nodes, that minimizes the weighted sum of theexternal path lengths. These path lengths are the numbers of steps from the root to each leaf. They are multiplied by the weight of the leaf and then summed to give the quality of the overall tree.^[1]

This problem can be interpreted as a problem of constructing abinary search treefor${\displaystyle n}$ ordered keys, with the assumption that the tree will be used only to search for values that are not already in the tree. In this case, the${\displaystyle n}$ keys partition the space of search values into${\displaystyle n+1}$ intervals, and the weight of one of these intervals can be taken as the probability of searching for a value that lands in that interval. The weighted sum of external path lengths controls theexpected time for searching the tree.^[1]

Alternatively, the output of the problem can be used as aHuffman code, a method for encoding${\displaystyle n+1}$ given values unambiguously by using variable-length sequences ofbinary values. In this interpretation, the code for a value is given by the sequence of left and right steps from a parent to the child on the path from the root to a leaf in the tree (e.g. with 0 for left and 1 for right). Unlike standard Huffman codes, the ones constructed in this way arealphabetical, meaning that the sorted order of these binary codes is the same as the input ordering of the values. If the weight of a value is its frequency in a message to be encoded, then the output of the Garsia–Wachs algorithm is the alphabetical Huffman code thatcompresses the message to the shortest possible length.^[1]

Overall, the algorithm consists of three phases:^[1]

1. Build a binary tree having the values as leaves but possibly in the wrong order.
2. Compute each leaf's distance from the root in the resulting tree.
3. Build another binary tree with the leaves at the same distances but in the correct order.

The first phase of the algorithm is easier to describe if the input is augmented with twosentinel values,${\displaystyle \mathrm{\infty }}$ (or any sufficiently large finite value) at the start and end of the sequence.^[2]

The first phase maintains a forest of trees, initially a single-node tree for each non-sentinel input weight, which will eventually become the binary tree that it constructs. Each tree is associated with a value, the sum of the weights of its leavesmakes a tree node for each non-sentinel input weight. The algorithm maintains a sequence of these values, with the two sentinel values at each end. The initial sequence is just the order in which the leaf weights were given as input.It then repeatedly performs the following steps, each of which reduces the length of the input sequence, until there is only one tree containing all the leaves:^[1]

• Find the first three consecutive weights${\displaystyle x}$,${\displaystyle y}$, and${\displaystyle z}$ in the sequence for which${\displaystyle x\le z}$. There always exists such a triple, because the final sentinel value is larger than any previous two finite values.
• Remove${\displaystyle x}$ and${\displaystyle y}$ from the sequence, and make a new tree node to be the parent of the nodes for${\displaystyle x}$ and${\displaystyle y}$. Its value is${\displaystyle x+y}$.
• Reinsert the new node immediately after the rightmost earlier position whose value is greater than or equal to${\displaystyle x+y}$. There always exists such a position, because of the left sentinel value.

To implement this phase efficiently, the algorithm can maintain its current sequence of values in anyself-balancing binary search tree structure. Such a structure allows the removal of${\displaystyle x}$ and${\displaystyle y}$, and the reinsertion of their new parent, in logarithmic time. In each step, the weights up to${\displaystyle y}$ in the even positions of the array form a decreasing sequence, and the weights in the odd positions form another decreasing sequence. Therefore, the position to reinsert${\displaystyle x+y}$ may be found in logarithmic time by using the balanced tree to perform twobinary searches, one for each of these two decreasing sequences. The search for the first position for which${\displaystyle x\le z}$ can be performed in linear total time by using asequential search that begins at the${\displaystyle z}$ from the previous triple.^[1]

It is nontrivial to prove that, in the third phase of the algorithm, another tree with the same distances exists and that this tree provides the optimal solution to the problem. But assuming this to be true, the second and third phases of the algorithm are straightforward to implement in linear time. Therefore, the total time for the algorithm, on an input of length${\displaystyle n}$, is${\displaystyle O(n\log n)}$.

The Garsia–Wachs algorithm is named afterAdriano Garsia andMichelle L. Wachs, who published it in 1977.^[1][3] Their algorithm simplified an earlier method ofT. C. Hu andAlan Tucker,^[1][4] and (although it is different in internal details) it ends up making the same comparisons in the same order as the Hu–Tucker algorithm.^[5] The original proof of correctness of the Garsia–Wachs algorithm was complicated, and was later simplified byKingston (1988)^[1][2]andKarpinski, Larmore & Rytter (1997).^[6]

• Filliatre, Jean-Christophe (2008), "A functional implementation of the Garsia–Wachs algorithm (functional pearl)",Proceedings of the 2008 ACM SIGPLAN Workshop on ML (ML '08), New York, NY, USA: Association for Computing Machinery, pp. 91–96,doi:10.1145/1411304.1411317,ISBN 978-1-60558-062-3,S2CID 1541092

• Combinatorial algorithms
• Binary trees
• Search trees
• Lossless compression algorithms