# What are applications of alphabetic trees?

Earlier this week a paper was released describing an algorithm for building optimal alphabetic ternary trees. The alphabetic property as described on Wikipedia as

Alphabetic trees are Huffman trees with the additional constraint on order, or, equivalently, search trees with the modification that all elements are stored in the leaves. Faster algorithms exist for optimal alphabetic binary trees (OABTs).

From this, I understand that an alphabetic binary tree will produce shorter paths from root to element for elements that have been inserted into the tree more times than elements that haven't, and the alphabetic property would be described the same way for a ternary tree.

I haven't been able to find a lot of discussion about applications for the alphabetic property outside of Huffman coding but it is not a requirement to implement the algorithm. Are there any applications where the alphabetic property would be a requirement, and if not, are there any benefits to guaranteeing the alphabetic property that justifies increased implementation complexity?

One example application is storing textual data in alphabetic order. The complete works of Shakespeare were stored in an OAT (optimal alphabetic tree), which was constructed using the Hu-Tucker algorithm. See here for another $O(n \log n)$ algorithm for constructing OATs.
The queries constructed by Huffman's algorithm can be completely arbitrary, which makes it hard to implement them. In contrast, the queries in an alphabetic tree correspond to simple comparisons: we can identify each internal node with an object $x_i$ in the domain, and given an input $x$ to be encoded, we take the edge labeled "0" if $x \leq x_i$, and the edge labeled "1" if $x > x_i$. By storing the $x_i$ in the node, we facilitate efficient encoding.