Donald Bren School of Information and Computer Sciences

A binary split tree is a search structure combining features of heaps and binary search trees. Building an optimal binary split tree was originally conjectured to be intractable due to difficulties in applying dynamic programming techniques to the problem. However, two algorithms have recently been published which purportedly generate optimal trees in O(n^5) time, for records with distinct access probabilities. An extension allowing non-distinct access probabilities required exponential time. These algorithms consider a range of values when only a single value is possible, and may select an infeasible value which leads to an incorrect result. A dynamic programming method for determining the correct value is given, resulting in an algorithm which builds an optimal binary split tree in O(n^5) time for non-distinct access probabilities and Θ(n^4) time for distinct access probabilities.