  Alphabetic codes and binary search trees are combinatorial structures that
abstract search procedures in ordered sets endowed with probability
distributions. In this paper, we design new linear-time algorithms to construct
alphabetic codes, and we show that the obtained codes are not too far from
being optimal. Moreover, we exploit our results on alphabetic codes to provide
new bounds on the average cost of optimal binary search trees. Our results
improve on the best-known bounds on the average cost of optimal binary search
trees present in the literature.
