On the costs of optimal and near-optimal binary search trees

Summary We show that the cost of an optimal binary search tree can vary substantially, depending only on the left-to-right order imposed on the probabilities. We also prove that the costs of some common classes of near-optimal trees cannot be bounded above by the cost of an optimal tree plus a constant. This work was supported by the National Research Council of Canada, while the author was at the University of Waterloo