Donald Bren School of Information and Computer Sciences

An algorithm is presented which constructs an optimal binary search tree for an ordered list of n items, and which requires subquadratic time if there is no long sublist of very low frequency items. For example, time = O(n^1.6) if the frequency of each item is at least ε/ n for some constant ε > 0.

A second algorithm is presented which constructs an approximately optimal binary search tree. This algorithm has one parameter, and exhibits a tradeoff between speed and accuracy. It is possible to choose the parameter such that time = O(n^1.6) and error = o(l).