Faster construction of optimal binary split trees

Abstract

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 generate optimal trees in O(n5) time, for records with distinct access probabilities. An extension allowing nondistinct access probabilities required exponential time. These algorithms consider a range of values when only a single value is possible. A dynamic programming method for determining the correct value is given, resulting in an algorithm which builds an optimal binary split tree in O(n5) time for nondistinct access probabilities and Θ(n4) time for distinct access probabilities. © 1986.