Search

This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm that is closely related to the over thirty-year-old idea of splay trees and evaluate its adaption performance in the distributed scenario if different communication patterns are provided. To do so, the process of self-adjustment is modeled similarly to a basic network creation game in which the nodes want to communicate with only a certain subset of all nodes. We show that, in general, the game (i.e., the process of local adjustments) does not converge, and that convergence is related to certain structures of the communication interests, which we call conflicts. We classify conflicts and show that for two communication scenarios in which convergence is guaranteed, the self-adjusting tree performs well. Furthermore, we investigate the different classes of conflicts separately and show that, for a certain class of conflicts, the performance of the tree network is asymptotically as good as the performance for converging instances. However, for the other conflict classes, a distributed self-adjusting binary search tree adapts poorly.

A novel method is proposed to design an optimal binary tree using genetic algorithm.Our method is the first one for the global optimization of a binary tree.The results demonstrated that the classification accuracy of our method was improved. Support vector machine (SVM) with a binary tree architecture is popular since it requires the minimum number of binary SVM to be trained and tested. Many efforts have been made to design the optimal binary tree architecture. However, these methods usually construct a binary tree by a greedy search. They sequentially decompose classes into two groups so that they consider only local optimum at each node. Although genetic algorithm (GA) has been recently introduced in multiclass SVM for the local partitioning of the binary tree structure, the global optimization of a binary tree structure has not been tried yet. In this paper, we propose a global optimization method of a binary tree structure using GA to improve the classification accuracy of multiclass problem for SVM. Unlike previous researches on multiclass SVM using binary tree structures, our approach globally finds the optimal binary tree structure. For the efficient utilization of GA, we propose an enhanced crossover strategy to include the determination method of crossover points and the generation method of offsprings to preserve the maximum information of a parent tree structure. Experimental results showed that the proposed method provided higher accuracy than any other competing methods in 11 out of 18 datasets used as benchmark, within an appropriate time. The performance of our method for small size problems is comparable with other competing methods while more sensible improvements of the classification accuracy are obtained for the medium and large size problems.

CB tree represents the binary trie by a compact binary sequence. However, retrieval time grows fast since the more keys stored in the trie, longer the binary sequences are. In addition it is inefficient for frequent key insertion/deletion. HCB tree is a hierarchical CB tree consisting of small binary tries. However it can not avoid shift operations and have to scan an additional table to refer child or parent trie. In order to improve retrieval performance and avoid shift operations when keys are inserted or deleted, we in this paper represent each separated trie by a full binary trie and then assign the unique identifier to it. Finally the theoretical evaluations show that both the proposed approach and HCB tree provides better than CB tree for key retrieval. The proposed approach shows the highest performance in case of key insertion/deletion and moreover requires only 71%~89% of storage as compared with CB tree.

Let G = ( V , E ) be a connected graph. The locating-chromatic number of G , denoted by χ L ( G ), is the cardinality of a minimum locating coloring of the vertex set V ( G ) such that all vertices have distinct coordinates. The results on locating-chromatic number of graphs are still limited. In particular, the locating-chromatic number of trees is not completely solved. Therefore, in this paper, we study the locating-chromatic number of any binary tree.

Traversing binary tree is an important algorithm in data structure. This paper analyses and discusses the recursive algorithm implementation of preorder-traversing binary tree through instance. It would contribute beginners to understand more deeply the process of preorder-traversing and enhance their programming.

Network tomography is a promising inference technique for network topology from end-to-end measurements. In this letter, we propose a novel binary tree pruning algorithm based on t-test to infer the network topology. A binary tree topology is first inferred using the existing Agglomerative Likelihood Tree (ALT) method, and then two samples t-test is applied to prune the binary tree, thus a general tree corresponding to the real topology is obtained. A lower bound on the correctly identified probability of the proposed method is derived. Simulation results show that the pruning method based on t-test outperforms the method which prunes the binary tree using a fixed threshold.

We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.

We show that for every $k$, the probability that a randomly selected vertex of a random binary search tree on $n$ nodes is at distance $k-1$ from the closest leaf converges to a rational constant $c_k$ as $n$ goes to infinity., 12 pages 1 figure

Binary codes play an important role in many computer vision applications. They require less storage space while allowing efficient computations. However, a linear search to find the best matches among binary data creates a bottleneck for large-scale datasets. Among the approximation methods used to solve this problem, the hierarchical clustering tree (HCT) method is a state-of the-art method. However, the HCT performs a hard assignment of each data point to only one cluster, which leads to a quantisation error and degrades the search performance. As a solution to this problem, an algorithm to create hierarchical soft clustering tree (HSCT) by assigning a data point to multiple nearby clusters in the Hamming space is proposed. Through experiments, the HSCT is shown to outperform other existing methods.

A improved binary tree SVM multi-class classification algorithm is proposed. Firstly, constructing the minimum hyper ellipsoid for each class sample in the feather space, and then generating optimal binary tree according to the hyper ellipsoid volume, training sub-classifier for every non-leaf node in the binary tree at the same time. For the sample to be classified, the sub-classifiers are used from the root node until one leaf node, and the corresponding class of the leaf node is the class of the sample. The experiments are done on the Statlog database, and the experimental results show that the algorithm improves classification precision and classification speed, especially in the situation that the number of class are more and their distribution area are equal approximately, the algorithm can greatly improve the classification precision and classification speed.

In this paper, we revisit a method to produce binary sequences using the most significant bit map from Z4 to the binary field. This method is useful for the construction of binary sequences with low correlation and large family size. There may be more cases where starting with Z4 could help researchers design new low correlation sequences for code-division multiple access application.

The paper presents the first concurrency-optimal implementation of a binary search tree (BST). The implementation, based on a standard sequential implementation of a partially-external tree, ensures that every schedule, i.e., interleaving of steps of the sequential code, is accepted unless linearizability is violated. To ensure this property, we use a novel read-write locking protocol that protects tree edges in addition to its nodes.

Positive selection is one of artificial immune approaches, which finds application in network security. It relies on building detectors for protecting self cells, i.e. positive class objects. Random selection used to find candidates for detectors gives good results if the data is represented in a non-multidimensional space. For a higher dimension many attempts may be needed to find a detector. In an extreme case, the approach may fail due to not building any detector. This paper proposes an improved version of the positive selection approach. Detectors are constructed based on self cells in a deterministic way and they are stored in a binary tree structure. Thanks to this, each cell is protected by at least one detector regardless of the data dimension and size. Results of experiments conducted on network intrusion data (KDD Cup 1999 Data) and other datasets show that the proposed approach produces detectors of similar or better quality in a considerably shorter time compared with the probabilistic version. Furthermore, the number of detectors needed to cover the whole self space can be clearly smaller.

P-sets consists of an internal P-set XF and an outer P-set XF and has dynamic characteristics, which result from the internal dynamic characteristics on XF and the outer dynamic characteristics on XF. In order to extend the application of the P-sets, the paper proposes an F-recursive binary tree through applying the dynamic characteristics for the P-set XF. Meanwhile, the paper provides the structures and characteristics for the F-recursive binary tree, including some properties and theorems about the F-recursive binary tree. The paper also gives the method of constructing F-recursive binary tree. The F-recursive binary tree has inward contraction characteristics and recursive characteristics. It can be used many research fields, such as information science and technology, artificial intelligence, knowledge discovery, as well as control theory and control engineering.

Binary Search Tree (BST) is an important data structure for managing ordered data. Many algorithms---blocking as well as non-blocking---have been proposed for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations based on both external and internal representations of a search tree. An important step in executing an operation on a tree is to traverse the tree from top-to-down in order to locate the operation's window. A process may need to perform this traversal several times to handle any failures occurring due to other processes performing conflicting actions on the tree. Most concurrent algorithms that have proposed so far use a naïve approach and simply restart the traversal from the root of the tree. In this work, we present a new approach to recover from such failures more efficiently in a concurrent binary search tree based on internal representation using local recovery by restarting the traversal from the "middle" of the tree in order to locate an operation's window. Our approach is sufficiently general in the sense that it can be applied to a variety of concurrent binary search trees based on both blocking and non-blocking approaches. Using experimental evaluation, we demonstrate that our local recovery approach can yield significant speed-ups of up to 69% for many concurrent algorithms.

We study the problem of embedding an unweighted complete binary tree into a line with low distortion. Very recently, Mathieu and Papamanthou (2008) [9] showed that the inorder traversal of the complete binary tree of height h gives a line embedding of distortion O(2^h), and conjectured that the current lower bound of @W(2^hh) increases to @W(2^h), i.e., the upper bound of O(2^h) is best possible. In this paper, we disprove their conjecture by providing a line embedding of the complete binary tree of height h with optimal distortion @Q(2^hh).

Binary sort tree is a special binary tree, can be used for sorting and searching area, realize the visualization has important significance. In this paper ,it is realized the visualization of binary sort tree by using object-oriented method and the features of complete binary tree, solve some problems when the method achieved.

tree traversal refers to the process of visiting each node in a specified order. Given the inorder traversal of a binary tree, along with one of its preorder or postorder traversals, the original binary tree can be uniquely identified. Many recursive and non recursive method of construction of the tree from inorder and any of the postorder or preorder traversal have been proposed. In this paper one of the proposed algorithms has been examined. This algorithm computes the wrong tree for some input sequences. We show a particular situation in which the algorithm fails and a solution for this situation is proposed. The proposed a modified non-recursive algorithm for reconstructing a binary tree which generates the correct tree otherwise an error has been reported.

Many problems in science and engineering can be simplified into the form of a perfect binary tree. This paper discusses our study entitled Perfect Binary Tree Sequence (PBTS) which transforms a perfect binary tree into the single-row network. The transformation is necessary in applications such as in the assignment of telephone channels to caller–receiver pairs roaming in cells in a cellular network on real-time basis. In this application, each caller and receiver in a call forms a node, while their pair connection forms the edge. A specific case of the graph in the form of a binary tree is then transformed into its corresponding single-row network for assigning the channels to the caller–receiver pairs. PBTS starts with the formation of the spine from a perfect binary tree through the insertion mechanism, and this leads to the expansion of the spine into one or more zones in the single-row network. This is followed by the formation of terminals and intervals for optimal transformation into the nets of the single-row network using our earlier method called ESSR. The numerical experiment results support our hypothesis that PBTS transforms the tree into its single-row network efficiently.

This paper evaluates reliability of binary directed tree-structured systems based on terminal failure limit-value. For the difficult problem with complex structures and directed transitive relation, the paper describes nodes in the tree system using set algebra, and uses set operations to compute a combinational mode of failed nodes, and then describes it with family of sets. On that basis, an effective algorithm is shown, and a numerical example is given to illustrate the algorithm obtained in the paper.

A data structure, called the primogenitary linked quad tree (PLQT), is used to store and retrieve solutions in heuristic solution procedures for binary optimization problems. Two ways are proposed to use integer vectors to represent solutions represented by binary vectors. One way is to encode binary vectors into integer vectors in a much lower dimension and the other is to use the sorted indices of binary variables with values equal to 0 or equal to 1. The integer vectors are used as composite keys to store and retrieve solutions in the PLQT. An algorithm processing trial solutions for insertion into or retrieval from the PLQT is developed. Examples are provided to demonstrate the way the algorithm works. Another algorithm traversing the PLQT is also developed. Computational results show that the PLQT approach takes only a very tiny portion of the CPU time taken by a linear list approach for the same purpose for any reasonable application. The CPU time taken by the PLQT managing trial solutions is negligible as compared to that taken by a heuristic procedure for any reasonably hard to solve binary optimization problem, as shown in a tabu search heuristic procedure for the capacitated facility location problem. Compared to the hashing approach, the PLQT approach takes the same or less amount of CPU time but much less memory space while completely eliminating collision.

We show that for no chain C there is a monadic-second order interpretation of the full binary tree in C.

In this paper we propose an online shape learning algorithm based on the self-balancing binary search tree data structure for the storage and retrieval of shape templates. This structure can also be used for classification purposes. We introduce a similarity measure with which we can make decisions on how to traverse the tree and even backtrack through the search path to find more candidate matches. Then we describe every basic operation a binary search tree can perform adapted to such a tree of shapes. Note that as a property of binary search trees, all operations can be performed in O(logn) time and are very efficient. Finally, we present experimental data evaluating the performance of the proposed algorithm and demonstrating the suitability of this data structure for the purpose it was designed to serve.

We study the number of random records in a binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.

Deletions in binary search trees are difficult to analyse as they are not randomness preserving. We will present a new kind of tree which differs slightly from the standard binary search tree. It will be referred to as an ordered binary search tree as it stores a history element in its nodes, which provides information about the order in which the nodes were inserted. Using this extra information it is possible to design a new randomness preserving and order preserving deletion algorithm.

This paper presents a new method for evaluating boolean set operations between Binary Space Partition (BSP) trees. Our algorithm has many desirable features, including both numerical robustness and O(n) output sensitive time complexity, while simultaneously admitting a straightforward implementation. To achieve these properties, we present two key algorithmic improvements. The first is a method for eliminating null regions within a BSP tree using linear programming. This replaces previous techniques based on polygon cutting and tree splitting. The second is an improved method for compressing BSP trees based on a similar approach within binary decision diagrams. The performance of the new method is analyzed both theoretically and experimentally. Given the importance of boolean set operations, our algorithms can be directly applied to many problems in graphics, CAD and computational geometry.

We consider three random variables X n , Y n and Z n , which represent the numbers of the nodes with 0, 1, and 2 children, in the binary search trees of size n. The expectation and variance of the three above random variables are got, and it is also shown that X n , Y n and Z n are all asymptotically normal as n → ∞ by applying the contraction method.

We present a proof–based automatic synthesis experiment in the context of sorting binary trees, namely the synthesis of the function which inserts an element in a sorted binary tree at the appropriate place. The algorithm is automatically extracted from the automatically produced proof of the conjecture which expresses the existence of the desired output for each appropriate input of the function.This is a case study with the purpose of finding and illustrating general and domain specific inference rules and strategies for efficiently producing proofs from which the desired algorithms can be extracted.The construction of the necessary theory, of the provers, and the experiment itself are performed in the Theorema system.

We study the Kolmogorov complexity of a Binary Insertion Tree, and present a succinct encoding scheme for Binary Insertion Trees produced from incompressible permutations. Based on the encoding scheme, we obtain a simple incompressibility argument that yields an asymptotic analysis of the average height of a Binary Insertion Tree. This argument further implies that the QuickSort algorithm sorts a permutation of n elements in @Q(nlgn) comparisons on average.

One of the main problems in peer-to-peer systems is how to balance the lookup latency, the number of transmitted messages and the network expansibility. In this paper, we present a P2P model based on a rigorous binary tree code algorithm. Our model is robust and efficient with constant lookup latency and constant message transmission. More importantly, the model has good expansibility and is suitable for super-scale networks.

Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average-case complexity.We investigate what happens in between by analysing the smoothed height of binary search trees: Randomly perturb a given (adversarial) sequence and then take the expected height of the binary search tree generated by the resulting sequence. As perturbation models, we consider partial permutations, partial alterations, and partial deletions.On the one hand, we prove tight lower and upper bounds of roughly Θ((1−p)⋅n/p) for the expected height of binary search trees under partial permutations and partial alterations, where n is the number of elements and p is the smoothing parameter. This means that worst-case instances are rare and disappear under slight perturbations. On the other hand, we examine how much a perturbation can increase the height of a binary search tree, i.e. how much worse well balanced instances can become.

We analyze two bottom-up reduction algorithms over binary trees that represent replaceable data within a certain system, assuming the binary search tree (BST) probabilistic model. These reductions are based on idempotent and nilpotent operators, respectively. In both cases, the average size of the reduced tree, as well as the cost to obtain it, is asymptotically linear with respect to the size of the original tree. Additionally, the limiting distributions of the size of the trees obtained by means of these reductions satisfy a central limit law of Gaussian type.

In this paper we propose using experiments with Balanced-Sample Binary Trees (BSBTrees) as assignments and lecture material in intermediate data structures courses (CS2/3). BSBTrees are composite data structures that have a temporarily constructed form that precedes their normal construction. We present them in the context of binary search trees. To do this we first investigate the retrieval properties of randomly generated binary search trees and show how temporary construction can improve both worst case and average case behavior. We provide a brief analysis of BSBTree performance and description of the classes that can be used for BSBTree implementation. Last we discuss the use of BSBTrees in CS2 and CS3 courses and a survey of student opinions about BSBTrees.

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.

Balanced binary search tree structures such as AVL, red-black, and splay trees store exactly one element per node. We propose supernode versions of these structures in which each node may have a large number of elements. Some properties of supernode binary search tree structures are established. Experiments oonducted by us show that the supernode structures proposed by us use less space than do the corresponding one-element-per-node versions and also take less time for the standard dictionary operations: search, insert and delete.

Based on fisher ratio class separability measure, we propose two types of posterior probability support vector machines (PPSVMs) using binary tree structure. The first one is a some-against-rest binary tree of PPSVM classifiers (SBT), for which some classes as a cluster are divided from the rest classes at each non-leaf node. To determine the two clusters, we use the Fisher ratio separability measure. Accordingly, the second proposed method termed one-against-rest binary tree of PPSVMs (OBT), we separate only one class with the largest separability measure from the rest classes at each non-leaf node. Then, the procedures of both SBT and OBT are provided. Finally, we consider the problem of human action recognition based on depth maps adopting both proposed approaches. Simulation results indicate both methods gain higher classifying accuracy than those of canonical multi-class SVMs and PPSVMs. Besides, the decision complexity of the proposed SBT and OBT are reduced because they use the posterior probability and the Fisher ratio separability measure.

We present an O(n4)-time algorithm for the following problem: Given a set of items with known access frequencies, find the optimal binary search tree under the realistic assumption that each comparison can only result in a two-way decision: either an equality comparison or a less-than comparisons. This improves the best known result of O(n5) time, which is based on split tree algorithms. Our algorithm relies on establishing thresholds on the frequency of an item that can occur as an equality comparison at the root of an optimal tree.

We present a performance comparison of tree data structures for N-body simulation. The tree data structures examined are the balanced binary tree and the Barnes?Hut (BH) tree. Previous work has compared the performance of BH trees with that of nearest-neighbor trees and the fast multipole method, but the relative merits of BH and binary trees have not been compared systematically. In carrying out this work, a very general computational tool which permits controlled comparison of different tree algorithms was developed. The test problems of interest involve both long-range physics (e.g., gravity) and short-range physics (e.g., smoothed particle hydrodynamics). Our findings show that the Barnes?Hut tree outperforms the binary tree in both cases. However, we present a modified binary tree which is competitive with the Barnes?Hut tree for long-range physics and superior for short-range physics. Thus, if the local search time is a significant portion of the computational effort, a binary tree could offer performance advantages. This result is of particular interest since short-range searches are common in many areas of computational physics, as well as areas outside the scope of N-body simulation such as computational geometry. The possible reasons for this are outlined and suggestions for future algorithm evaluations are given.

We present observations and problems connected with a weighted binary tree representation of integer partitions.

We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. In addition to read and write instructions, our algorithm uses (single-word) compare-and-swap (CAS) and bit-test-and-set (SETB) atomic instructions, both of which are commonly supported by many modern processors including Intel~64 and AMD64.In contrast to existing lock-free algorithms for a binary search tree, our algorithm is based on marking edges rather than nodes. As a result, when compared to other lock-free algorithms, modify (insert and delete) operations in our algorithm work on a smaller portion of the tree, thereby reducing conflicts, and execute fewer atomic instructions (one for insert and three for delete). Our experiments indicate that our lock-free algorithm significantly outperforms all other algorithms for a concurrent binary search tree in many cases, especially when contention is high, by as much as 100%.

Splay and randomized search trees (RSTs) are self-balancing binary tree structures with little or no space overhead compared to a standard binary search tree (BST). Both trees are intended for use in applications where node accesses are skewed, for example in gathering the distinct words in a large text collection for index construction. We investigate the efficiency of these trees for such vocabulary accumulation. Surprisingly, unmodified splaying and RSTs are on average around 25% slower than using a standard binary tree. We investigate heuristics to limit splay tree reorganization costs and show their effectiveness in practice. In particular, a periodic rotation scheme improves the speed of splaying by 27%, while other proposed heuristics are less effective. We also report the performance of efficient bit-wise hashing and red–blacktrees for comparison. Copyright © 2001 John Wiley & Sons, Ltd.

The problem of constructing a binary search tree for a set of binary words has wide applications in computer science, biology, mineralogy, etc. Shannon considered a similar statement in his optimal coding theorem. It is NP-complete to construct a tree of minimum cost; therefore, the problem arises of finding simple algorithms for constructing nearly optimal trees. We show that there is a simple algorithm for constructing search trees sufficiently close to the optimal tree on average. By means of this algorithm we prove that for the optimal tree the average number of bits to be checked is near to its natural lower bound, i.e., the binary logarithm of the number of given words: their difference is less than 1.04.

This article proposes a novel genetic algorithm (GA) which switches the expression of the solution from a redundant binary number to a usual binary number. Furthermore, a GA which switches the expression from the Gray code to the usual binary number is proposed and compared. Comparisons of the performances among five GAs (binary number, redundant binary number, Gray code, switching from redundant binary number to binary number, switching from Gray code to binary number) are illustrated. The performances are evaluated by solving some equations. It is confirmed that the proposed GA effectively decreases the error rate.