Search

How much separate information about two random binary sequences is needed in order to tell with small probability of error in which positions the two sequences differ? If the sequences are the outputs of two correlated memoryless binary sources, then in some cases the rate of this information may be substantially less than the joint entropy of the two sources. This result is implied by the solution of the source coding problem with two separately encoded side information sources for a special class of source distributions.

A binary operation on the class of trees is defined that generates a set B of finite trees form a trivial tree (one node) and B contains for every finite tree G exactly one element isomorphic to G. The binary operation defines an algebraic structure on B, and as a consequence the finite tree types are characterized as an initial algebra in the same way as the natural numbers are characterized as an initial algebra by the Peano-Lawvere axiom [2]. Simple and primitive recursion are defined and some applications of the initial algebra characterization are given.

In this paper we have studied the performance of alternative representations of binary search-trees for indexing a relation kept in main-memory. It was shown that space/time performance of the common techniques, such as sorted heaps, and more complex data structures, such as avl-trees, can be improved considerably. In particular, when an upperbound is determined during program construction on the maximal size of the indices, an efficient mapping, called the virtual tree, from binary search tree to array exists. The resulting search structure ensures an upperbound on the number of comparisons for searching and maintenance will only start to deteriorate when the area set aside for holding the index is nearly full. In addition, we showed that limiting the maximal size of the index structure permits judicious use of code-expansion, i.e. logarithmic code expansion, to further improve the performance of the algorithms. For a search dominant environment our approach is better than the more space consumptive binary trees representations based on pointer chasing. In a volatile environment the space/time performance can be controlled precisely.

In this paper we prove a conjecture of Erdos and Palka on the maximum size of random trees. Furthermore, while, generally speaking, in the probabilistic analysis the results are proved only when the size of the graphs tends to infinity, in this case, with extremely small probability of error, the results also hold for graphs of small size.

Binary search trees have received a great deal of attention in recent years. As a result of this interest, several methods have been developed for balancing them; namely, random, height-balanced, bounded-balance, and weight-balanced trees. These methods which include weighted and non-weighted binary search trees are grouped into two classes: 1) dynamic balancing and 2) total restructuring. The rational and properties of the more significant methods are discussed and compared with other tree balancing algorithms. These comparisons provide insight about the conditions under which an algorithm is appropriate.

Given a file of N records each of which has k keys, the worst-case analysis for the region and partial region queries in multidimensional binary search trees and balanced quad trees are presented. It is shown that the search algorithms proposed in [1, 3] run in time O(k·N 1?1/k) for region queries in both tree structures. For partial region queries with s keys specified, the search algorithms run at most in time O(s·N 1?1/k ) in both structures.

BCT (Binary Classification Tree) is a system that learns from examples and represents learned concepts as a binary polythetic decision tree. Polythetic trees differ from monothetic decision trees in that a logical combination of multiple (versus a single) attribute values may label each tree arc. Statistical evaluations are used to recursively partition the concept space in two and expand the tree. As with standard decision trees, leaves denote classifications. Classes are predicted for unseen instances by traversing appropriate branches in the tree to the leaves. Empirical results demonstrated that BCT is generally more accurate or comparable to two earlier systems.

This chapter presents the bounded form of binary search tree further described in §5.1 where the interface to the unbounded binary search tree is covered. The implementation follows in §5.2.

It is now recognized that binary search trees are structures which can be used efficiently for the organization of files and directories. The ease of insertion and deletion of nodes makes trees very appealing for directories which are often modified. By comparison with a sequential table organization, some additional memory is required for the links between nodes. From a cost-effective viewpoint, this is generally more than compensated for by the savings in searching (for a linear table) and inserting (for an ordered table).

This paper studies embeddings of graphs in binary trees. The cost of such an embedding is the maximum distance in the binary tree between images of adjacent graph vertices. Several techniques for bounding the costs of such embeddings from above are derived; notable among these is an algorithm for embedding any outerplanar graph in a binary tree with a cost that is within a factor of 3 of optimal. A number of techniques for bounding the costs of such embeddings from below are developed; notable here are two techniques for inferring the presence of large separators in graphs. Finally, a number of characterizations are established of those families of graphs that are almost binary trees, in the sense that every graph in the family is embeddable in a binary tree within bounded cost.

Trees have been important data structures since the mid-fifties when the first list processing applications and languages were developed. When Knuth systematized the accumulated knowledge about data structures in his 1968 book on Fundamental Algorithms, he devoted half the space to tree structures. During the seventies, data structures based on trees were extended to files on secondary storage and to multidimensional problems such as multi-key access. Trees also became the dominant data structure for many algorithms in the field of concrete complexity, because they are the only structures known that guarantee an O(log n) worst case bound on sequential and random access, insertion and deletion on linearly ordered sets. Recent events indicate, however, that in the coming decade the predominance of trees as all-round data structures may be challenged by address computation techniques. Various refinements and generalizations of the old programming trick called hashing have caused an unexpected extension of the domain of applicability of address computation techniques to dynamic files and multi-key access.

Publisher Summary This chapter presents a nonparametric discriminant analysis based on the construction of a binary decision tree. The standard classical methods in classification problems are discriminant analysis and logistic regression. In these cases, the prediction rules are given in the form of algebraic expressions that are difficult to understand and interpret. The discriminant analysis takes a different approach, and the resulting prediction rules are given in the form of binary decision trees close to the physician reasoning, easy to understand, use, explain, and interpret. A binary decision tree is constructed by repeated splits of subsets of patients into two descendant subsets. The idea is to select each split so that the data in each of the descendant subsets are purer than the data in the parent node. In the illustrative binary decision tree, each subset is a node. A binary decision tree is obtained by means of the qualitative measurements of the data set.

A two-step procedure for nonparametric multiclass classifier design is described. A multiclass recursive partioning algorithm is given which generated a single binary decision tree for classifying all classes. The algorithm minimizes the Bayes risk at each node. A tree termination algorithm is given which optimally terminates binary decision trees. The algorithm yields the unique tree with fewest nodes which minimizes the Bayes risk. Tree generation and termination are based on the training and test samples, respectively.

We use the idea of self-adjusting trees to create new, simple data structures for priority queues (which we call heaps) and search trees. Unlike other efficient implementations of these data structures, self-adjusting trees have no balance condition. Instead, whenever the tree is accessed, certain adjustments take place. (In the case of heaps, the adjustment is a sequence of exchanges of children, in the case of search trees the adjustment is a sequence of rotations.) Self-adjusting trees are efficient in an amortized sense: any particular operation may be slow but any sequence of operations must be fast. Self-adjusting trees have two advantages over the corresponding balanced trees in both applications. First, they are simpler to implement because there are fewer cases in the algorithms. Second, they are more storage-efficient because no balance information needs to be stored. Furthermore, a self-adjusting search tree has the remarkable property that its running time (for any sufficiently long sequence of search operations) is within a constant factor of the running time for the same set of searches on any fixed binary tree. It follows that a self-adjusting tree is (up to a constant factor) as fast as the optimal fixed tree for a particular probability distribution of search requests, even though the distribution is unknown.

Publisher Summary This chapter focuses on advanced data structures. The chapter presents a complex data structure, the binary tree. Binary trees are one of the most powerful and flexible data structures used in programs. The theory behind binary trees is discussed. Binary trees are actually related to the linked list family of data structures. In C, binary trees are naturally coded with structures and pointers. A binary tree is constructed from nodes that contain data and pointers to other trees. Binary trees are true recursive data structures. Therefore, it is only natural that most of the operations for processing binary trees are also recursive. Binary trees are ideal structures for storing data in some prearranged order. One of the most commonly used type of tree is called the sorted tree. In such a tree, data is always inserted in a sorted order. The technique of traveling through a tree is called tree traversal. There are three methods used to traverse trees: preorder, inorder, and postorder.

We consider heuristics which attempt to maintain a binary search tree in a near optimal form, assuming that elements are requested with fixed, but unknown, independent probabilities. A "move to root" heuristic is shown to yield an expected search time within a constant factor of that of an optimal static binary search tree. On the other hand, a closely related "simple exchange" technique is shown not to have this property. The rate of convergence of the "move to root" heuristic is discussed. We also consider the more general case in which elements not in the tree may have non-zero probability of being requested.

A rotation in a binary tree is a local restructuring that changes the tree into another tree. Rotations are useful in the design of tree-based data structures. The rotation distance between a pair of trees is the minimum number of rotations needed to convert one tree into the other. In this paper we establish a tight bound of In 6 on the maximum rotation distance between two A2-node trees for all large n, using volumetric arguments in hyperbolic 3-space. Our proof also gives a tight bound on the minimum number of tetrahedra needed to dissect a polyhedron in the worst case, and reveals connections 1 This is a revised and expanded version of a paper that appeared in the 18th Annual ACM Symposium on Theory of Computing, [9]. 2 Partial support provided by DARPA, ARPA order 4976, amendment 19, monitored by the Air Force Avionics Laboratory under contract F33615-87-C-1499, and by the National Science Foundation under grant CCR-8658139. 3 Partial support provided by the National Science Foundation under grant DCR-8605962. 4 Partial support provided by the National Science Foundation under grants DMR-8504984 and DCR8505517.

We derive upper and lower bounds for the weighted path length Popt of optimum binary search trees. In particular, 1/log3 H≤Popt≤2+H where H is the entropy of the frequency distribution. We also present an approximation algorithm which constructs nearly optimal trees.

This paper considers the distribution of the genealogical tree of a sample of genes in the infinitely-many-site model where the relative age ordering of the mutations (nodes in the tree) is known. A computer implementation of a recursion for the probability of such trees is discussed when the nodes are age-labeled, or not.

More than twenty years ago Nievergelt and Wong obtained a number of new bounds on the path length of binary trees in both the weighted and unweighted cases.

We present an efficient algorithm for decomposing an n-ary relation into a tree of binary relations, and provide an efficient test for checking whether or not the tree formed represents the relation. If there exists a tree-decomposition, the algorithm is guaranteed to find one, otherwise, the tree generated will fail the test, then indicating that no tree decomposition exist. The unique features of the algorithm presented in this paper, is that it does not apriori assume any dependencies in the initial relation, rather it derives such dependencies from the bare relation instance.

We discuss two simple strategies for constructing binary search trees: "Place the most frequently occurring name at the root of the tree, then proceed similary on the subtrees "and" choose the root so as to equalize the total weight of the left and right subtrees as much as possible, then proceed similarly on the subtres." While the former rule may yield extremely inefficient search trees, the latter rule always produces nearly optimal trees.

Let T(n) denote the set of all bitstrings with n 1's and n 0's such that in every prefix the number of 0's does not exceed the number of 1's. This is a well known representation of binary trees. We consider algorithms that generate the elements of T(n) in such way that successive bitstrings differ by the transposition of two bits. The presented algorithms have a constant average time per generated tree.

k-balanced binary trees are a form of binary tree balanced by the internal path reduction algorithm described by Gonnet in his original article [1]. As discussed previously in Chapter 3, this balancing scheme reorganizes one or more subtrees whenever the internal path length can be reduced. The idea is that future search operations will examine fewer subtrees during a search since the subtrees are closer to the root of the tree after being rebalanced. In Gonnet’s original exposition of the algorithm, rebalancing occurred whenever the internal path length could be reduced by one, and leading to the term 1 -balanced tree. As noted by Gonnet, a factor of two, three, or greater could also be used with essentially the same algorithm, which would rebalance a subtree when its internal path length could be reduced by the given factor. He gave the name k-balanced trees to the class of binary search trees balanced in this manner. In this chapter, we present an implementation for k- balanced trees where k is termed the balancing control factor regulating the frequency of rebalancing operations.

It is shown how a highly compact representation of binary trees can be used as the basis of two access methods for dynamic files, called BDS-trees and S-trees, respectively. Both these methods preserve key-order and offer easy and efficient sequential access. They are different in the way the compact binary trees are used for searching. With a BDS-tree the search is a digital search using binary digits. Although the S-tree search is performed on a bit-by-bit basis as well, it will appear to be slightly different. Actually, with S-trees the compact binary trees are used to represent separators at low storage costs. As a result, the fan-out, and thus performance, of a B-tree can beimproved by using within each index page an S-tree for representing separators efficiently. Copyright © 1987 by the Institute of Electrical and Electronics Engineers, Inc.

Publisher Summary This chapter discusses a nonuniform random recursive tree. A tree is a connected graph which has no cycles. Tree R with n vertices labelled 1, 2, …, n is a recursive tree if for each k such that 2≤ k ≤n the labels of vertices in the unique path from the first vertex to the k th vertex of a tree form an increasing subsequence of {1,2, . . ., n}. A random recursive tree with n vertices (n-RRT) is a tree picked at random from the family of all recursive trees with n vertices. The chapter deals with a random recursive tree such that the probability of joining a new vertex to the vertex i depends only on the degree of vertex i . In addition, the chapter considers two special cases of the random recursive tree.

In this paper the parallel conflict-free access to complete extended binary subtrees of complete binary trees is investigated. Thereby linear and also nonlinear memory module assignment functions S are considered. Furthermore, the problem of optimal parallel access to extended binary trees is solved.

The combination of APL2 constructs and direct definition notation makes the description and implementation of complex generic types easy and natural. This paper illustrates this with an APL2 paradigm for modelling binary trees. It considers the problems of constructing trees, inserting new items, searching for items, counting leaves, counting comparisons, and testing for equivalence.

In searching algorithms, trees of the same size are not equally likely to occur. Given a particular probability distribution over trees with the same number of nodes, the paper presents a general approach to the computation of the expected value of a general additive weight defined on these trees; special cases of this weight are various types of path lengths and free search cost measures. Generally, the presented method yields a system of formal equations satisfied by the generating function of the average weights whose actual interpretation represents a system of algebraic and functional-differential equations. The method is explicitly demonstrated for the class of random t -ary trees, binary search trees, t -ary digital search trees and Patricia trees.

If a binary search tree is created by inserting N keys in random order using the usual insertion algorithm, then it is well known that the average search path is about 1.4lgN. However, if deletions, using the frequently recommended Hibbard's algorithm, are interspersed with the insertions, then virtually nothing has been proven except for Knuth and Jonassen's very difficult, but complete, analysis of the case N = 3. In this paper it is shown that after a sufficient number of updates the average search path is t(N1/2). An improved algorithm given by Knuth is shown to have the same asymptotic behavior.

This paper introduces the arc tree, a hierarchical data structure to represent arbitrary curved shapes. The arc tree is a balanced binary tree that represents a curve of length l such that any subtree whose root is on the k-th tree level is representing a subcurve of length l/2 k . Each tree level is associated with an approximation of the curve; lower levels correspond to approximations of higher resolution. Based on this hierarchy of detail, queries such as point search or intersection detection and computation can be solved in a hierarchical manner. We compare the arc tree to several related schemes and present the results of a practical performance analysis for various kinds of set and search operators. We also discuss several options to embed arc trees as complex objects in an extensible database management system and argue that the embedding as an abstract data type is most promising.

We show that the cost of an optimal binary search tree can vary substantially, depending only on the left-to-right order imposed on the probabilities. We also prove that the costs of some common classes of near-optimal trees cannot be bounded above by the cost of an optimal tree plus a constant.

Consider a set of records, where each record is identified by a unique key. The records are accessed based on a set of access probabilities and are to be arranged lexicographically using a binary search tree. If is known a priori, it is well known [7] that an optimal binary search tree may be constructed using and . We consider the case when is not known a priori. A new restructuring heuristic is introduced that requires three extra integer memory locations per record, and this restructuring of the tree is performed only if it decreases the weighted path length of the overall resultant tree. We also present a space optimized version of the latter restructuring mechanism which requires only one extra integer field per record. We show that the cost of the tree is reduced by each restructuring operation, and present experimental results to demonstrate the superiority of our algorithm over all other reported efficient static and dynamic schemes.

The clusters of binary patterns can be considered as Boolean functions of the (binary) features. Such a relationship between the linearly separable (LS) Boolean functions and LS clusters of binary patterns is examined. An algorithm is presented to answer the questions of the type: “Is the cluster formed by the subsets of the (binary) data set having certain features AND/NOT having certain other features, LS from the remaining set?” The algorithm uses the sequences of Numbered Binary Form (NBF) notation and some elementary (NPN) transformations of the binary data.

A new tree-searched VQ scheme called delayed-decision binary tree-searched VQ is proposed in this paper. To alleviate the sub-optimal solution problem of binary tree-searched algorithms, it uses multipath search to find the best matching codevector in a binary-tree codebook. At each tree node, it examines the path error of the 2*M branches extended from M saved nodes, and Only the best M of these branches are saved for the next step. This procedure continues until the end of the tree is reached, and then the codevector of the best matched node among the final M saved nodes is used. In simulations, the delayed-decision algorithm is incorporated in a mean/residue binary tree-searched VQ. It is shown that, on the average, a 20% reduction of mean-square error is obtained when M=8. Therefore, the performance is much improved by better searching the same codebook at the expense of computational costs. Most of all, the image quality is improved without increasing the bit rate.

A method formulated by Yao and used by Brown has yielded bounds on the fraction of nodes with specified properties in trees bult by a sequence of random internal nodes in a random tree built by binary search and insertion, and show that in such a tree about bounds better than those now known. We then apply these methods to weight-balanced trees and to a type of “weakly balanced” trees. We determine the distribution of the weight-balance factors of the internal nodes in a random tree built by binary search and insertion and show that in such a tree about 72% of all internal nodes have weight balance factors lying between 1−2√/2 and 2√/2.

This chapter presents the unbounded form of binary search tree further described in §4.2. In §4.1 is the standard operations and exceptions module used by all tree modules in this volume. The interface to the unbounded binary search tree is covered in §4.2 while its implementation follows in §4.3. The chapter concludes with a utility module in §4.4 and §4.5.