Set Orderings Requiring Costliest Alphabetic Binary Trees

Authors:
  • DKD. J. Kleitman
    D. J. Kleitman
  • MSMichael E. Saks
    Michael E. Saks

Abstract
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.

This publication has 7 references indexed in Scilit: