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.     

关于具有最大路长限制的顺序二分树

本文给出了一个构造具有最大路长限制的最小价格顺序二分树的算法;引进了分界数的概念。并证明了关于分界数的基本定理,从而使算法的计算量同O(n~2L)成比例,文中还讨论了具有最大路长限制的Huffman树问题,给出相应的算法,计算量也为O(n²L)。     

Congruence preserving functions of Wilke’s tree algebras

As a framework for characterizing families of regular languages of binary trees, Wilke introduced a formalism for defining binary trees that uses six many-sorted operations involving letters, trees and contexts. In this paper a completeness property of these operations is studied. It is shown that all functions involving letters, binary trees and binary contexts which preserve congruence relations of the free tree algebra over an alphabet, are generated by Wilke’s functions, if the alphabet contains at least seven letters. That is to say, the free tree algebra over an alphabet with at least seven letters is affine-complete. The proof yields also a version of the theorem for ordinary one-sorted term algebras: congruence preserving functions on contexts and members of a term algebra are substitution functions, provided that the signature consists of constant and binary function symbols only, and contains at least seven symbols of each rank. Moreover, term algebras over signatures with at least seven constant symbols are affine-complete.Received March 18, 2004; accepted in final form October 8, 2004.     

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.     

Combinatorics of non-ambiguous trees

This article investigates combinatorial properties of non-ambiguous trees. These objects we define may be seen either as binary trees drawn on a grid with some constraints, or as a subset of the tree-like tableaux previously defined by Aval, Boussicault and Nadeau. The enumeration of non-ambiguous trees satisfying some additional constraints allows us to give elegant combinatorial proofs of identities due to Carlitz, and to Ehrenborg and Steingrímsson. We also provide a hook formula to count the number of non-ambiguous trees with a given underlying tree. Finally, we use non-ambiguous trees to describe a very natural bijection between parallelogram polyominoes and binary trees.     

Exponentially many supertrees

The amalgamation of leaf-labelled trees into a single supertree that displays each of the input trees is an important problem in classification. Clearly, there can be more than one (super) tree for a given set of input trees, in particular if a highly unresolved supertree exists. Here, we show (by explicit construction) that even if every supertree of a given collection of input trees is binary, there can still be exponentially many such supertrees.     

The Splits in the Neighborhood of a Tree

A phylogenetic tree represents historical evolutionary relationships between different species or organisms. The space of possible phylogenetic trees is both complex and exponentially large. Here we study combinatorial features of neighbourhoods within this space, with respect to four standard tree metrics. We focus on the splits of a tree: the bipartitions induced by removing a single edge from the tree. We characterize those splits appearing in trees that are within a given distance of the original tree, demonstrating close connections between these splits, the Whitney number of a tree, and the binary characters with a given parsimony length.AMS Subject Classification: 68R10, 05C05, 68Q25, 92D15.     

The rotation graph of binary trees is Hamiltonian

In this paper we study the rotation transformation on binary trees and consider the properties of binary trees under this operation. The rotation is the universal primitive used to rebalance dynamic binary search trees. New binary search tree algorithms have recently been introduced by Sleator and Tarjan. It has been conjectured that these algorithms are as efficient as any algorithm that dynamically restructures the tree using rotations. We hope that by studying rotations in binary trees we shall gain a better understanding of the nature of binary search trees, which in turn will lead to a proof of this “dynamic optimality conjecture”. We define a graph, RG(n), whose vertex set consists of all binary trees containing n nodes, and which has an edge between two trees if they differ by only one rotation. We shall introduce a new characterization of the structure of RG(n) and use it to demonstrate the existence of a Hamiltonian cycle in the graph. The proof is constructive and can be used to enumerate all binary trees with n nodes in constant time per tree.     

Maximal Flow in Branching Trees and Binary Search Trees

A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal flow that can pass through a given path is the minimun capacity on the path. Antal and Krapivski (Phys Rev E 74:051110, 2006) study the distribution for the maximal flow from the root to a leaf in the case of a deterministic binary tree with independent and identically distributed random capacities. In this paper their result is extended to three classes of trees with a random number of children and dependent random capacities: binary trees with general capacities distribution, branching trees with exchangeable capacities and random binary search trees.     

Ranking and unranking of non-regular trees with a prescribed branching sequence

Ordered trees are called non-regular trees with a prescribed branching sequence (or non-regular trees for short) if their internal nodes have a pre-specified degree sequence in preorder list. This article presents two main results. First, we develop a simple algorithm to generate all non-regular trees in lexicographic order using RD-sequences defined by [R.-Y. Wu, J.-M. Chang, Y.-L. Wang, Loopless generation of non-regular trees with a prescribed branching sequence, The Computer Journal 53 (2010) 661–666]. Then, by analyzing the structure of a coding tree, this algorithm is proved to run in constant amortized time. Next, we propose efficient ranking algorithm (i.e., determining the rank of a given non-regular tree in such an order) and unranking algorithm (i.e., converting a positive integer to its corresponding RD-sequence).     

Approximate inference in Bayesian networks using binary probability trees

The present paper introduces a new kind of representation for the potentials in a Bayesian network: Binary Probability Trees. They enable the representation of context-specific independences in more detail than probability trees. This enhanced capability leads to more efficient inference algorithms for some types of Bayesian networks. This paper explains the procedure for building a binary probability tree from a given potential, which is similar to the one employed for building standard probability trees. It also offers a way of pruning a binary tree in order to reduce its size. This allows us to obtain exact or approximate results in inference depending on an input threshold. This paper also provides detailed algorithms for performing the basic operations on potentials (restriction, combination and marginalization) directly to binary trees. Finally, some experiments are described where binary trees are used with the variable elimination algorithm to compare the performance with that obtained for standard probability trees.     

Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees

. Leaf-labelled trees are widely used to describe evolutionary relationships, particularly in biology. In this setting, extant species label the leaves of the tree, while the internal vertices correspond to ancestral species. Various techniques exist for reconstructing these evolutionary trees from data, and an important problem is to determine how "far apart" two such reconstructed trees are from each other, or indeed from the true historical tree. To investigate this question requires tree metrics, and these can be induced by operations that rearrange trees locally. Here we investigate three such operations: nearest neighbour interchange (NNI), subtree prune and regraft (SPR), and tree bisection and reconnection (TBR). The SPR operation is of particular interest as it can be used to model biological processes such as horizontal gene transfer and recombination. We count the number of unrooted binary trees one SPR from any given unrooted binary tree, as well as providing new upper and lower bounds for the diameter of the adjacency graph of trees under SPR and TBR. We also show that the problem of computing the minimum number of TBR operations required to transform one tree to another can be reduced to a problem whose size is a function just of the distance between the trees (and not of the size of the two trees), and thereby establish that the problem is fixed-parameter tractable.     

完全二叉树理论的计算复杂度

完全二叉树的一阶理论已被证明具有量词消去的性质,进而计算了完全二叉树模型中元素的CB秩.本文利用有界Ehrenfeucht-Frassé博弈研究完全二叉树的一阶理论,证明了此理论的时间计算复杂度上界为22cn,空间计算复杂度上界为2dn(其中n为输入长度,c,d为合适的常数).     

Minimum average congestion of enhanced and augmented hypercubes into complete binary trees

We study the embedding problem of enhanced and augmented hypercubes into complete binary trees. Using tree traversal techniques, we compute the minimum average edge congestion of enhanced and augmented hypercubes into complete binary trees.     

Binary search trees with limited rotation

A parameterized binary search tree callediR tree is defined in this paper. A user is allowed to select a level of balance he desires. SR tree is a special case ofiR tree wheni=1. There are two new concepts in SR trees: (1) local balancing scheme that balances the tree locally; (2) consecutive storage for brother nodes that reduces pointer space. Although we may introduce empty nodes into the tree, we can show that only 1/8 of the nodes may be empty on the average, so it may still be advantageous in cases when record sizes are small. Insertion (and deletion) into SR trees can be done in timeh + O(1) whereh is the height of the tree. The average searching time for SR trees is shown to be 1.188 log₂ k wherek is the number of keys. Generalization of the results of SR trees toiR in general is also given.     

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.     

Some asymptotically optimal one-sided embeddings of trees of similar formulas into rectangular lattices

We consider the problem of optimally placing trees of formulas in rectangular lattices. We construct and study two types of these trees and corresponding ways of placing (embedding) them into such lattices. The first is based on perfect binary trees, while the second is based on special binary trees. For the second type of tree embeddings, we prove asymptotic optimality among the trees of all formulas similar to the initial formula of no greater depth.     

Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

A condition for assured 3-face-colorability of infinite plane graphs with a given spanning tree

Given an infinite leafless tree drawn on the plane, we ask whether or not one can add edges between the vertices of the tree obtaining a non-3-face-colorable graph. We formulate a condition conjectured to be necessary and sufficient for this to be possible. We prove that this condition is indeed necessary and sufficient for trees with maximal degree 3, and that it is sufficient for general trees. In particular, we prove that every infinite plane graph with a spanning binary tree is 3-face-colorable.     

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.