New Ways to Construct Binary Search Trees

摘要

We give linear-time algorithms for re-ordering and height-restricting a binary search tree with only a small increase in cost, constructing a nearly optimal binary search tree given the rank by probability of each possible outcome, arid height-restricting an optimal binary search tree when the increase in cost is restricted. Whereas most algorithms for constructing good binary search trees need the probabilities of outcomes as input, our algorithms do not.