Search

We present an O(n4)-time algorithm for the following problem: Given a set of items with known access frequencies, find the optimal binary search tree under the realistic assumption that each comparison can only result in a two-way decision: either an equality comparison or a less-than comparisons. This improves the best known result of O(n5) time, which is based on split tree algorithms. Our algorithm relies on establishing thresholds on the frequency of an item that can occur as an equality comparison at the root of an optimal tree.

The paper studies the computational complexity and efficient algorithms for the twist?rotation transformations of binary trees, which is equivalent to the transformation of arithmetic expressions over an associative and commutative binary operation. The main results are (1) a full binary tree with n labeled leaves can be transformed into any other in at most 3nlogn+2n twist and rotation operations, (2) deciding the twist?rotation distance between two binary trees is NP-complete, and (3) the twist?rotation transformation can be approximated with ratio 6logn+4 in polynomial time for full binary trees with n uniquely labeled leaves.

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(n1.6) if the frequency of each item is at least e n for some constant e > 0. A second algorithm is presented which constructs an approximately optimal binary search tree. This algorithm has one parameter, and exhibits a trade-off between speed and accuracy. It is possible to choose the parameter such that time = O(n1.6) and error = o(1).

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 ( n 5 ) 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 ( n 5 ) time for nondistinct access probabilities and Θ ( n 4 ) time for distinct access probabilities.

A binary storage tree has a set or bucket of possible items associated with each node. The buckets at deeper levels are refinements of the partitionings at earlier levels. When these buckets are established a priori, rather than determined by the particular items stored, we obtain a storage data structure which is a generalized binary digital tree as well as a binary storage tree. Thus the binary key-values of the items along a path in a fixed-bucket binary storage tree have successively longer common prefixes. This synthesis of two schemes inherits all the desirable properties of both methods. The method is analyzed for uniformly-distributed input and shown to have the same cost statistics as binary digital trees.

A split tree is a special kind of a binary search tree introduced by B. A. Sheil ( Comm. ACM 21 (1978), 947–958). He conjectured that constructing an optimum split tree is an intractable problem since there is a difficulty in applying the dynamic programming technique. It is realized that the difficulty arises since top down decisions are required while applying the bottom up dynamic programming technique. It is demonstrated that it is possible in this case to overcome such a difficulty, and a polynomial algorithm for constructing an optimum split tree is presented. This algorithm incorporates top down decisions into a dynamic programming procedure similar to D. E. Knuth's ( Acta Inform . 1 (1971), 14–25) algorithm for constructing an optimum binary search tree. The probabilities of unsuccessful searches are taken into account. A modification for the case that equiprobable keys are permitted is discussed.