Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees

A sublinear time subquadratic work parallel algorithm for construction of an optimal binary search tree, in a special case of practical interest, namely where the frequencies of items to be stored are not too small, is given. A sublinear time subquadratic work parallel algorithm for construction of an approximately optimal binary search tree in the general case is also given. Sub-quadratic work and sublinear time are achieved using a fast parallel algorithm for the column minima problem for Monge matrices developed by Atallah and Kosaraju. The algorithms given in this paper take O(n 0:6 ) time with n processors in the CREW PRAM model. Our algorithms work well if every subtree of the optimal binary search tree of depth \Omega\Gammapth n) has o(n) leaves. We prove that there is a sequential algorithm with subquadratic average-case complexity, by demonstrating that the "small subtree" condition holds with very high probability for a randomly permuted weight sequence. This solves the co..