Search

We consider two tree statistics that extend in a natural way the parameters depth of a node resp. distance between two nodes. The ancestor-tree of p given nodes in a rooted tree T is the subtree of T, spanned by the root and these p nodes and generalizes the depth (ancestor-tree of a single node), whereas the spanning subtree induced by p given nodes in a tree T generalizes the distance (induced spanning subtree of two nodes). We study the random variables size of the ancestor-tree resp. spanning subtree size for two tree families, the simply generated trees and the recursive trees. We will assume here the random tree model and also that all () possibilities of selecting p nodes in a tree of size n are equally likely. For random simply generated trees we can then characterize for a fixed number p of chosen nodes the limiting distribution of both parameters as generalized Gamma distributions, where we prove the convergence of the moments too. For some specific simply generated tree families we can give exact formulae for the first moments. In the instance of random recursive trees, we will show that the considered parameters are asymptotically normally distributed, where we can give also exact formulae for the expectation and the variance. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004

A random suffix search tree is a binary search tree constructed for the suffixes Xi = 0. BiBi+1Bi+2 ... of a sequence B1, B2, B3 .... of independent identically distributed random b-ary digits Bj. Let Dn denote the depth of the node for Xn in this tree when B1 is uniform on Zb. We show that for any value of b > 1, EDn = 2 log n + O(log2log n), just as for the random binary search tree. We also show that Dn/EDn → 1 in probability.

Asymptotics are obtained for the mean, variance, and higher moments as well as for the distribution of the Wiener index of a random tree from a simply generated family (or, equivalently, a critical Galton-Watson tree). We also establish a joint asymptotic distribution of the Wiener index and the internal path length, as well as asymptotics for the covariance and other mixed moments. The limit laws are described using functionals of a Brownian excursion. The methods include both Aldous' theory of the continuum random tree and analysis of generating functions.

The Horton-Strahler number naturally arose from problems in various fields, e.g., geology, molecular biology and computer science. Consequently, detailed investigations of related parameters for different classes of binary tree structures are of interest. This paper shows one possibility of how to perform a mathematical analysis for parameters related to the Horton-Strahler number in a unified way such that only a single analysis is needed to obtain results for many different classes of trees. The method is explained by the examples of the expected Horton-Strahler number and the related rth moments, the average number of critical nodes, and the expected distance between critical nodes.

We establish an almost sure large deviations theorem for the depth of the external nodes of binary search trees (BSTs). To achieve this, a parametric family of martingales is introduced. This family also allows us to get asymptotic results on the number of external nodes at deepest level. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 112–127, 2001

Multidimensional binary trees represent a symbiosis of trees and tries, and they essentially arise in the construction of search trees for multidimensional keys. The set of nodes in a d-dimensional binary tree can be partitioned into layers according to the nodes appearing in the ith dimension. We determine the exact distribution of the number of nodes with zero, one, and two sons in a specified layer and show that jointly the three types of nodes asymptotically have a trivariate normal distribution in each layer. That trivariate normal distribution is completely characterized. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13: 261–283, 1998

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 functions subjected to singularity perturbation asymptotics.

In this paper typical properties of large random Boolean AND/OR formulas are investigated. Such formulas with n variables are viewed as rooted binary trees chosen from the uniform distribution of all rooted binary trees with m leaves, where n is fixed and m tends to infinity. The leaves are labeled by literals and the inner nodes by the connectives AND/OR, both uniformly at random. In extending the investigation to infinite trees, we obtain a close relation between the formula size complexity of an arbitrary Boolean function f and the probability of its occurrence under this distribution, i.e., the negative logarithm of this probability differs from the formula size complexity of f only by a polynomial factor.

We study the distribution Q on the set Bn of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in Bn when successive requests are independent and identically distributed with each record equally likely. We identify the minimum and maximum values of the functional Q and the trees achieving those values and argue that Q is a crude measure of the “shape” of the tree. We study the distribution of Q(T) for two choices of distribution for random trees T; uniform over Bn and Q. In the latter case, we obtain a limiting normal distribution for −ln Q(T). © 1996 John Wiley & Sons, Inc.

Meir and Moon studied the distribution of the maximum degree for simply generated families of trees. We have sharper results for the special case of labelled trees. © 1994 John Wiley & Sons, Inc.

Consider a tree partitioning process in which n elements are split into b at the root of a tree (b a design parameter), the rest going recursively into two subtrees with a binomial probability distribution. This extends some familiar tree data structures of computer science like the digital trie and the digital search tree. The exponential generating function for the expected size of the tree satisfies a difference-differential equation of order b, The solution involves going to ordinary (rather than exponential) generating functions, analyzing singularities by means of Mellin transforms and contour integration. The method is of some general interest since a large number of related problems on digital structures can be treated in this way via singularity analysis of ordinary generating functions. 0 1992 John Wiley & Sons, Inc.

Grow a tree on n vertices by starting with no edges and successively adding an edge chosen uniformly from the set of possible edges whose addition would not create a cycle. This process is closely related to the classical random graph process. We describe the asymptotic structure of the tree, as seen locally from a given vertex. In particular, we give an explicit expression for the asymptotic degree distribution. Our results an be applied to study the random minimum-weight spanning tree question, when the edge-weight distribution is allowed to vary almost arbitrarily with n.

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height Hn of these trees by applying the theory of branching random walks. in particular, it is shown that Hn/log nγ in probability as n∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.