Set Orderings Requiring Costliest Alphabetic Binary Trees
Daniel J. Kleitman, Michael Saks · SIAM Journal on Algebraic and Discrete Methods · 1981
It is shown that an ordering of a set with weighted elements which requires the most expensive alphabetic binary tree is a “sawtooth order.” For the set $\{ e_0 ,e_1 , \cdots ,e_t \}$, with the elements indexed from least to greatest weight, this order is $e_0 ,e_t ,e_1 ,e_{t - 1} , \cdots ,e_j ,e_{t - 1} , \cdots $. This result was conjectured by Hwang and leads to an upper bound on the cost of alphabetic binary trees.