Optimal binary split trees

Split trees are a technique for storing records with fixed frequency distributions. It was previously believed that no polynomial time algorithms to construct optimal representations of split trees were likely (B. A. Sheil, Median split trees: A fast lookup technique for frequently occurring keys, Comm. ACM (1978), p.949). In this paper we present an O(n⁵) algorithm to construct optimal binary split trees. Other efficient algorithms to construct suboptimal split trees are also discussed. The definition of split trees is later generalized to a larger class of trees so that we can compare several important classes of trees.     

A note on optimal multiway split trees

Split trees are suitable data structures for storing records with different access frequencies. Under assumption that the access frequencies are all distinct, Huang has proposed anO(n ⁴ logm) time algorithm to construct an (m+1)-way split tree for a set ofn keys. In this paper, we generalize Huang's algorithm to deal with the case of non-distinct access frequencies. The technique used in the generalized algorithm is a generalization of Hesteret al.'s, where the binary case was considered. The generalized algorithm runs inO(n ⁵ logm) time.     

Thresholds and optimal binary comparison search trees

We present an O(n⁴)-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(n⁵) 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.     

Pointed binary encompassing trees: Simple and optimal

For n disjoint line segments in the plane we construct in optimal O(nlogn) time and linear space an encompassing tree of maximum degree three such that at every vertex v all edges of the tree that are incident to v lie in a halfplane bounded by the line through the input segment which v is an endpoint of. In particular, this tree is pointed since every vertex has an incident angle greater than π. Such a pointed binary tree can be augmented to a minimum pseudo-triangulation. It follows that every set of disjoint line segments in the plane has a constrained minimum pseudo-triangulation whose maximum vertex degree is bounded by a constant.     

A subquadratic algorithm for constructing approximately optimal binary search trees

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 trade-off between speed and accuracy. It is possible to choose the parameter such that time = O(n^1.6) and error = o(1).     

Optimum split trees

A split tree is a special kind of a binary search tree introduced by B. A. Sheil (Comm. ACM21 (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.     

Optimal multiway split trees

A class of multiway split trees is defined. Given a set of n weighted keys and a node capacity m, an algorithm is described for constructing a multiway split tree with minimum access cost. The algorithm runs in time O(mn⁴) and requires O(mn³) storage locations. A further refinement of the algorithm enables the factor m in the above costs to be reduced to log m.     

Simple and optimal output-sensitive construction of contour trees using monotone paths

Contour trees are used when high-dimensional data are preprocessed for efficient extraction of isocontours for the purpose of visualization. So far, efficient algorithms for contour trees are based on processing the data in sorted order. We present a new algorithm that avoids sorting of the whole dataset, but sorts only a subset of so-called component-critical points. They form only a small fraction of the vertices in the dataset, for typical data that arise in practice. The algorithm is simple, achieves the optimal output-sensitive bound in running time, and works in any dimension. Our experiments show that the algorithm compares favorably with the previous best algorithm.     

On optimal trees

The merits of different shapes of trees as data storage structures are compared. Given a tree data structure, the worst-case cost of searching the tree is studied, under weak assumptions about the cost of searches. In particular, it is assumed that the cost of a search path is the sum of the costs of the nodes on it, and that the cost of a node depends only on the outdegree of that node. The main results of the paper are that there are regular trees (as defined in the paper) which are nearly optimal among trees with a given number of nodes, and that minimal-cost trees are often nearly regular.     

Fixed-bucket binary storage trees

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.     

Restructuring ordered binary trees

We consider the problem of restructuring an ordered binary tree T, preserving the in-order sequence of its nodes, so as to reduce its height to some target value h. Such a restructuring necessarily involves the downward displacement of some of the nodes of T. Our results, focusing both on the maximum displacement over all nodes and on the maximum displacement over leaves only, provide (i) an explicit tradeoff between the worst-case displacement and the height restriction (including a family of trees that exhibit the worst-case displacements) and (ii) efficient algorithms to achieve height-restricted restructuring while minimizing the maximum node displacement.     

Slim sets of binary trees

A classical problem in phylogenetic tree analysis is to decide whether there is a phylogenetic tree T that contains all information of a given collection P of phylogenetic trees. If the answer is “yes” we say that P is compatible and T displays P. This decision problem is NP-complete even if all input trees are quartets, that is binary trees with exactly four leaves. In this paper, we prove a sufficient condition for a set of binary phylogenetic trees to be compatible. That result is used to give a short and self-contained proof of the known characterization of quartet sets of minimal cardinality which are displayed by a unique phylogenetic tree.     

Supersolvable LL-lattices of binary trees

Some posets of binary leaf-labeled trees are shown to be supersolvable lattices and explicit EL-labelings are given. Their characteristic polynomials are computed, recovering their known factorization in a different way.     

Counting labels in binary trees

We investigate properties of binary (search) trees related to the inorder labelling of the nodes. Both permutation and uniform trees are considered. We give explicit formulas to count the number of interior, middle and final nodes (leaves) containing a specific label. Possible applications are discussed.This work was supported by the Italian Ministry for Public Education.     

Pattern avoidance in binary trees

This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts n-leaf binary trees avoiding a given binary tree pattern t. Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective n-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns.     

On growing random binary trees

A sequence {T_n}_{n = 1}^∞ of nested binary trees generated by an infinite sequence of i.i.d. random variables is studied. Two absolute constants β₁,β₂ are shown to exist (0.37 < β₁ < 0.50, 3.58 < β₂ < 4.32), such that $\text{lim}\text{h}{}_{\mathrm{n}}\text{ln}\text{n = β}{}_1\text{,}\text{lim}\text{H}{}_{\mathrm{n}}\text{/}\text{ln}\text{n = β}{}_2$ with probability one; here h_n and H_n are respectively the lengths of the shortest and the longest branches of the tree T_n.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

Wiener indices of balanced binary trees

We study a new family of trees for computation of the Wiener indices. We introduce general tree transformations and derive formulas for computing the Wiener indices when a tree is modified. We present several algorithms to explore the Wiener indices of our family of trees. The experiments support new conjectures about the Wiener indices.