Search

A new class of binary search trees, called trees of bounded balance, is introduced. These trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is only moderately longer than in completely balanced trees. Trees of bounded balance differ from other classes of binary search trees in that they contain a parameter which can be varied so the compromise between short search time and infrequent restructuring can be chosen arbitrarily.

A mathematical model is developed for the mean and variance of the number of trials to recover a given document in a randomly received list of files. The search method described is binary in nature and offers new potential for information retrieval systems.

Let Tn denote a tree with n(≧ 2) labelled points: we assume Tn is rooted at a given point x, say the point labelled 1 (see [3] for definitions not given here). If we remove some edge e of Tn, then Tn falls into two subtrees one of which, say Tk, contains the root x. If k ≧ 2 we can remove some edge of Tk and obtain an even smaller subtree of Tn that contains x. If we repeat this process we will eventually obtain the subtree consisting of x itself. Let λ = λ(Tn) denote the number of edges removed from Tn before the root x is isolated. Our main object here is to determine the expected value μ(n) and variance σ2(n) of λ(Tn) under the assumptions (1) Tn is chosen at random from the set of nn−2 trees with n labelled points that are rooted at point x, and (2) at each stage the edge removed is chosen at random from the edges of the remaining subree containing x. It follows from our results that μ(n) ~ (½πn)½ and (2−½π)n ~ (2−½π)n as n tends to infinity. We also consider the corresponding problem for forests of rooted trees and for trees in which the degree of the root is specified. We are indebted to Professor Alistair Lachlan for suggesting the original problem to us.

A class of binary trees is described for maintaining ordered sets of data. Random insertions, deletions, and retrievals of keys can be done in time proportional to log N where N is the cardinality of the data-set. Symmetric B-Trees are a modification of B-trees described previously by Bayer and McCreight. This class of trees properly contains the balanced trees.

—This paper considers the problem of determining whether a sequential machine, given by its flow table, can be realized in the form of a single binary shift register. One-to-one and many-to-one assignments are considered. Binary partitions are introduced, and shift registers are characterized in terms of binary partitions. An algorithm is given for the determination of the required partitions for a shift-register assignment. Binary set systems are introduced and shift registers are characterized in terms of binary set systems. It is proven that there exists a sequential machine that cannot be realized by a single binary shift register of finite length. Methods for determining the set systems necessary for a single shift-register assignment are given. For machines where every state has two distinct next states, a method is presented whereby a number of machines can be easily eliminated as being not fsr realizable. It is then shown how this can be extended to all machines.

A method of generating all complete trees of a pair of linear graphs representing an active network is given. This method is a repetition of two processes, one of which is to obtain a complete tree and the other is to generate all possible complete trees of distance one from the complete tree that is obtained by the first process. These two processes are easily carried out by the use of computers, and there will be no duplications in the generated complete trees. Furthermore, complete trees are generated by sets of complete trees classified by edges in initial complete tree to. Thus, it will be easy to factorize the result according to the weights of these edges.

Two upper bounds for the total path length of binary trees are obtained. One is for node-trees, and bounds the internal (or root-to-node) path length; the other is for leaf-trees, and bounds the external (or root-to-leaf) path length. These bounds involve a quantity called the balance, which allows the bounds to adapt from the n log n behavior of a completely balanced tree to the n 2 behavior of a most skewed tree. These bounds are illustrated for the case of Fibonacci trees.

Let T(n, k) denote the number of trees n with n labelled nodes of which exactly k have degree two. We shall derive a formula for T(n, k) and then determine the asymptotic behaviour of T(n,0); this will enable us to calculate the limiting distribution of Xn the number of nodes of degree two in a random tree n. Renyi [5] has treated the corresponding problem for nodes of degree one in random trees.

The ordinary binary search method is shown to be one of a class of optimal binary search methods, supposing equiprobable search keys. For certain values of the numbern of records this class may be rather large. Thus forn=2 K +2 K−1−1 the number of optimal methods is of order $$2^{2^K }$$ ∼ 22n/3.

Let T denote one of the nn−2 trees with n labelled nodes that is rooted at a given node x (see [6] or [8] as a general reference on trees). If i and j are any two nodes of T, we write i ∼ j if they are joined by an edge in T. We want to consider random walks on T; we assume that when we are at a node i of degree d the probability that we proceed to node j at the next step is di–1 if i ∼ j and zero otherwise. Our object here is to determine the first two moments of the first return and first passage times for random walks on T when T is a specific tree and when T is chosen at random from the set of all labelled trees with certain properties.

We shall derive a formula for the expected value μ(n) of the node-independence number of a random tree with n labelled nodes and we shall determine the asymptotic behaviour of μ(n) as n tends to infinity.

An algorithm is given for constructing an alphabetic binary tree of minimum weighted path length (for short, an optimal alphabetic tree). The algorithm needs $4n^2 + 2n$ operations and $4n$ storage locations, where n is the number of terminal nodes in the tree. A given binary tree corresponds to a computer search procedure, where the given files or letters (represented by terminal nodes) are partitioned into two parts successively until a particular file or letter is finally identified. If the files or letters are listed alphabetically, such as a dictionary, then the binary tree must have, from left to right, the terminal nodes consecutively. Since different letters have different frequencies (weights) of occurring, an alphabetic tree of minimum weighted path length corresponds to a computer search tree with minimum-mean search time. A binary tree also represents a (variable-length) binary code. In an alphabetic binary code, the numerical binary order of the code words corresponds to the alphabetical orde...

An integral equation is derived for the generating function for binary tree values, the values reflecting sorting effort. The analysis does not assume uniformly distributed branching ratios, and therefore is applicable to a family of sorting algorithms discussed by Hoare, Singleton, and van Emden. The solution to the integral equation indicates that using more advanced algorithms in the family makes only minor reductions in the expected sorting efforts, but substantially reduces the variance in sorting effort. Statistical tests of the values of several thousand trees containing up to 10,000 points have given first, second, and third moments of the value distribution function in satisfactory agreement with the moments computed from the generating function. The empirical tests, as well as the analytical results, are in agreement with previously pubished results for the first moment in the cases of uniform and nonuniform distribution of branching ratio, and for the second moment in the case of uniform distribution of branching ratio.

An algorithm is given for constructing a binary tree of minimum weighted path length and with restricted maximum path length. (Huffman’s tree is a binary tree of minimum weighted path length with no restriction on maximum path length.) When an alphabetical ordering of the terminal nodes is introduced, the binary tree is called an alphabetic binary tree. We show that Huffman’s algorithm for optimal binary trees coincides with the T-C algorithm for optimal alphabetic binary trees when the terminal nodes have monotonically increasing weights from left to right.

We extend the binary search tree model of probability to simply generated families of trees. In the resulting statistics, well-balanced trees are more likely than linear trees. Using this balanced model, analyses are more complex than in the uniform case, but still feasible. We illustrate our point by working out some particular simple cases of study: the computation of occupancy (a measure of the degree of balancing in trees) and the average size of the intersection of two m-ary trees. The results are then compared with those obtained using the uniform model.

Given the n nodes of a binary tree in both inorder and preorder sequence, the tree can be uniquely identified. An efficient algorithm for reconstructing such trees from their sequences is presented, using O (n) time and O (h) intermediate storage, where h is the height of the tree being reconstructed.

The affine group of a homogeneous tree is the group of all its isometries fixing an end of its boundary. We consider a random walk with law μ on this group and the associated random processes on the tree and its boundary. In the drift-free case there exists on the boundary of the tree a unique μ-invariant Radon measure. In this paper we describe its behaviour at infinity.

We investigate code trees and search trees with cost functions that increase exponentially with the depth in the tree. While corresponding coding theorems have been considered in connection with Rényi’s entropy since 1965, the algorithmic aspects of these constructions have not been analyzed before. We propose a generalized Huffman algorithm for the construction of optimal codes in this model and treat related questions for search trees giving bounds on the costs of optimal trees. The algorithm for search tree construction is based on a new form of dynamic programming with the quadrangle inequality.We also consider random trees. Due to the exponential cost function, optimally balanced trees turn out to have significantly lower average costs than random trees, unlike in the standard cost model.

In this paper, we introduce a class of extended binary trees that resembles all possible tree-structures of binary tries. Assuming a uniform distribution of those trees we prove that for α being the number of internal nodes the average stack-size is given by 32πα. Since this result is quite similar to that for ordinary extended binary trees an attempt to find an explanation for that similarity using a quantitative level is made.

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.

We introduce the m -ary interval tree, a random structure that underlies interval division and simultaneous parking problems. Certain significant paths in the m -ary interval trees are considered. When appropriately normed, the length of these paths are shown to converge in distribution to a normal random variable. The work extends the study of incomplete binary interval trees in Itoh and Mahmoud (J. Appl. Probab. 40 (2003) 645). However, the extension is nontrivial, in the sense that the characterization in the m -ary case involves high-order differential equations, which is to be contrasted with the first-order differential equation that underlies the binary case, and in the sense that the path lengths exhibit oscillatory behavior for m ⩾ 4 , that does not exist in binary and ternary cases.

We consider random binary search trees when the input consists of a multiset, i.e. a set with multiple occurrences of equal elements, and prove that the randomized insertion and deletion algorithms given by Martínez and Roura (1998) [4] produce random search trees regardless of multiplicities; even if all the elements are equal during the tree updates, a search tree will maintain its randomness. Thus, equal elements do not degenerate a random search tree and they need not to be handled in any special way. We consider also stability of a search tree with respect to its inorder traversal and prove that the algorithms used produce stable trees. This implies an implicit indexing of equal elements giving another proof that multiplicities do not pose problems when maintaining random binary search trees.

We compute the second order correction for the cover time of the binary tree of depth $n$ by (continuous-time) random walk, and show that with probability approaching 1 as $n$ increases, $\sqrt{\tau_{\mathrm{cov}}}=\sqrt{|E|}[\sqrt{2\log 2}\cdot n - {\log n}/{\sqrt{2\log 2}} + O((\log\logn)^8]$, thus showing that the second order correction differs from the corresponding one for the maximum of the Gaussian free field on the tree., Comment: 14 pages, no figure

We give explicit asymptotic expressions for the number of “level number sequences” (l.n.s.) associated to binary trees. The level number sequences describe the number of nodes present at each level of a tree.

Denote by S n the set of all distinct rooted binary trees with n unlabeled vertices. Define σ n as a total height of a tree chosen at random in the set S(n), assuming that all the possible choices are equally probable. The total height of a tree is defined as the sum of the heights of its vertices. The height of a vertex in a rooted tree is the distance from the vertex to the root of the tree, that is, the number of edges in the path from the vertex to the root. This paper is concerned with the distribution and the moments of σ n and their asymptotic behavior as n → ∞).

We present a detailed study of left–right-imbalance measures for random binary search trees under the random permutation model, i.e., where binary search trees are generated by random permutations of {1,2,…,n}. For random binary search trees of size n we study (i) the difference between the left and the right depth of a randomly chosen node, (ii) the difference between the left and the right depth of a specified node j=j(n), and (iii) the difference between the left and the right pathlength, and show for all three imbalance measures limiting distribution results.

The distribution of binary trees with bicoloured endpoints under the taxonomic principle of parsimony is examined. Part one provides a constructive proof of an expression which describes the distribution of binary trees for a fixed colouring in terms of simple tree-related quantities. The result relies on Menger's theorem and an invariance property of binary trees. In part two a second invariance property gives the dual distribution, where the tree is fixed and the colourings vary. Applications to taxonomy, and the extension of results to r-colourings (r > 2) are outlined briefly.

While algorithms exist which produce optimal binary trees, there are no direct formulas for the cost of such trees. In this note, we give a formula for the cost of the optimal binary tree built on m nodes with weights 1, 2, 3,…, m . The simplicity of this proof suggests that one can try to compute the cost of optimal trees for other special classes of weights.

In this paper, we present a method of evaluating binary image dissimilarity based on tree representation and heuristic optimization. Starting from the image, a graph structure of a binary tree is constructed that splits the set of image foreground pixels into consecutive subsets attached to tree nodes. Next, instead of comparing two images themselves, one compares the trees and expresses image dissimilarity as tree dissimilarity, which can be characterized by a nonlinear function. The goal is to find its minimum, as it corresponds with the best match of compared trees. Searching for the minimum would be ineffective with analytical optimization methods. Hence, we have approached the issue with three meta-heuristic algorithms, namely genetic algorithm, particle swarm optimization (PSO) and simulated annealing. The presented results show that PSO achieved the best results. The proposed method is compared with other binary image comparison approaches. The performed tests that are described in the paper show that it outperforms its competitors and can be successfully applied to compare binary images.

We investigate binary search trees formed from sequences of nondistinct keys under two models. In the first model, an input sequence is composed from elements of a given finite multiset and all possible sequences are equally-likely. In the second model, an input sequence is composed from n elements of a (possibly infinite) set, where each key has a specified probability; the n keys are independently chosen from the given set. Under both models, we shall derive general closed-form expressions for the expected values of the characteristic parameters defined on the corresponding binary search trees. These parameters include the (left, right) depth of a given key, the level of a given external node and the left (right) side or the internal (external) path length of a search tree. Furthermore, we find some nonobvious relations between these expected values. In some respects, the second model tends to the first model for large n . All results are illustrated by concrete examples sometimes showing unexpected phenomena.

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., 19 pages, many images; published version

The problem is considered of determining the distribution of the number of nodes in any given component of a forest obtained by removing edges from a random tree.

In this paper distribution results are proved on the cost of insertion in digital search trees, (binary) tries and Patricia tries. A method from the calculus of finite differences is used to achieve asymptotic results.

An amortized analysis of the insertion and deletion algorithms ofk-dimensional balanced binary trees (kBB-trees) is performed. It is shown that the total rebalancing time for a mixed sequence ofminsertions and deletions in akBB-tree of sizenisO(k(m+n)). Based on 2BB-trees, a self-organizing tree, called aself-organizing balanced binary tree, is defined. It is shown that the average access time for an item stored in the tree is optimal to within a constant factor, while the worst-case access time is logarithmic. The amortized analysis ofkBB-trees leads to the result that the total update time for a mixed sequence ofmaccesses, insertions, and (restricted) deletions in a self-organizing balanced binary tree initially storingndata items isO(m+n)

Concerning the Horton-Strahler number (or register function) of binary trees, Yekutieli and Mandelbrot posed the problem of analyzing the bifurcation ratio of the root, which means how many maximal subtrees of register function one less than the whole tree are present in the tree. We show that if all binary trees of size n are considered to be equally likely, then the average value of this number of subtrees is asymptotic to 3.341266+δ(log4 n), where an analytic expression for the numerical constant is available and δ(x) is a (small) periodic function of period 1, which is also given explicitly. Additionally, we sketch the computation of the variance and also of higher bifurcation ratios.

We study the quantity distance between node j and node n in a random tree of size n chosen from a family of increasing trees. For those subclass of increasing tree families, which can be constructed via a tree evolution process, we give closed formulæ for the probability distribution, the expectation and the variance. Furthermore we derive a distributional decomposition of the random variable considered and we show a central limit theorem of this quantity, for arbitrary labels 1≤j

The main goal of this work is to fathom the suitability of the mesh with multiple broadcasting architecture (MMB) for some tree-related computations. We view our contribution at two levels: on the one hand, we exhibit time lower bounds for a number of tree-related problems on the MMB. On the other hand, we show that these lower bounds are tight by exhibiting time-optimal tree algorithms on the MMB. Specifically, we show that the task of encoding and/or decoding n-node binary and ordered trees cannot be solved faster than Ω(log n) time even if the MMB has an infinite number of processors. We then go on to show that this lower bound is tight. We also show that the task of reconstructing n-node binary trees and ordered trees from their traversais can be performed in O(1) time on the same architecture. Our algorithms rely on novel time-optimal algorithms on sequences of parentheses that we also develop.

Grammatical codes of trees provide a way to encode ordered trees into strings over a finite alphabet in such a way that the length of each code-word is precisely the number of leaves of the coded tree. Such codes are grammatical because they result by applying production rules of a grammar G to a tree t which becomes then a derivation tree t ′ in G and the yeild of this derivation tree t ′ becomes the code-word for t . Grammatical codes were investigated in [2,3], see also [1]. In this note we present two topics related to binary grammatical codes. The first topic (see Section 2) is grammatical codes of binary trees with a minimal code alphabet. It is shown that the only binary codes that are minimal in this sense are the so-called “strict” binary codes (as considered in [3]). The second topic (see Section 3) concerns the extension of binary grammatical codes to grammatical codes for trees of arbitrary degree. We make comparisons between classes of codes obtained in this way and the classes from [2, 3]. In Section 1 we recall (from [2, 3]) some notions and results concerning grammatical codes.

By using analytic tools it is shown that the variance E(Hn−EHn)2 of the height Hn of binary search trees of size n is bounded.

We show that binary search trees of a given size tend to have smaller height when the root division is into two subtrees of more balanced sizes. We deduce that the expectation of the absolute value of the difference in height of two binary search trees of the same number of nodes is less than 3.135 infinitely often. We also deduce strong upper bounds on the probability of large deviations from the median. Putting together these two conclusions and a simple and plausible conjecture on critical nodes leads to O(1) bounds on all moments of binary search tree heights.

Complete binary spanning trees of an n x n array of processors with an eight nearest neighbor interconnection pattern exist for a limited value of n. These spanning trees provide a fast route to accumulate information from all processors of the array, and allow certain problems to be solved as efficiently on an eight-neighbor array as on a tree-structured array. The condition under which complete binary spanning trees of a square array may exist is determined. This condition shows that complete binary spanning trees of an n x n eight-neighbor array exist only for n ≪ = 13. It is also observed that for n ≪ = 6, leaf nodes of these spanning trees lie on the periphery of the array.

A restriction on height-balanced binary trees is presented. It is seen that this restriction reduces the extra memory requirements by half (from two extra bits per node to one) and maintains fast search capabilities at a cost of increased time requirements for inserting new nodes.

Algorithms have been presented for computing a bijection between the set of binary trees on n nodes and an initial segment of the positive integers. A more complicated algorithm was also presented that computes a different bijection, claiming that their algorithm is more efficient and has advantages if a sequence of several consecutive trees is required. A modification of the first algorithm is presented that is simpler than the first and as efficient as the second. Also given is a new linear-time algorithm for transforming a tree into its successor in the natural ordering of binary trees.