Dense sets and embedding binary trees into hypercubes

The purpose of this paper is to describe a method for embedding binary trees into hypercubes based on an iterative embedding into their subgraphs induced by dense sets. As a particular application, we present a class of binary trees, defined in terms of size of their subtrees, whose members allow a dilation two embedding into their optimal hypercubes. This provides a partial evidence in favor of a long-standing conjecture of Bhatt and Ipsen which claims that such an embedding exists for an arbitrary binary tree.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Hereditarily finite sets and identity trees

Some asymptotic results about the sizes of certain sets of hereditarily finite sets, identity trees, and finite games are proven.     

On edge star sets in trees

Let A be a Hermitian matrix whose graph is G (i.e. there is an edge between the vertices i and j in G if and only if the (i,j) entry of A is non-zero). Let λ be an eigenvalue of A with multiplicity m_A(λ). An edge e=ij is said to be Parter (resp., neutral, downer) for λ,A if m_A(λ)−m_A−e(λ) is negative (resp., 0, positive ), where A−e is the matrix resulting from making the (i,j) and (j,i) entries of A zero. For a tree T with adjacency matrix A a subset S of the edge set of G is called an edge star set for an eigenvalue λ of A, if |S|=m_A(λ) and A−S has no eigenvalue λ. In this paper the existence of downer edges and edge star sets for non-zero eigenvalues of the adjacency matrix of a tree is proved. We prove that neutral edges always exist for eigenvalues of multiplicity more than 1. It is also proved that an edge e=uv is a downer edge for λ,A if and only if u and v are both downer vertices for λ,A; and e=uv is a neutral edge if u and v are neutral vertices. Among other results, it is shown that any edge star set for each eigenvalue of a tree is a matching.     

One-sided variations on binary search trees

We investigate incomplete one-sided variants of binary search trees. The (normed) size of each variant is studied, and convergence to a Gaussian law is proved in each case by asymptotically solving recurrences. These variations are also discussed within the scope of the contraction method with degenerate limit equations. In an incomplete tree the size determines most other parameters of interest, such as the height and the internal path length.     

Patterns in random binary search trees

In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturbation asymptotics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 : 223–244, 1997     

Interpretable clustering using unsupervised binary trees

We herein introduce a new method of interpretable clustering that uses unsupervised binary trees. It is a three-stage procedure, the first stage of which entails a series of recursive binary splits to reduce the heterogeneity of the data within the new subsamples. During the second stage (pruning), consideration is given to whether adjacent nodes can be aggregated. Finally, during the third stage (joining), similar clusters are joined together, even if they do not share the same parent originally. Consistency results are obtained, and the procedure is used on simulated and real data sets.     

Generating binary trees with uniform probability

A binary tree is characterized as a sequence of graftings. This sequence is used to construct a Markov chain useful for generating trees with uniform probability. A code for the Markov chain gives a characteristic binary string for the trees. The main result is the calculation of the transition probabilities of the Markov chain. Some applications are pointed out.