Search

This work is a case study of the formal verification and complexity analysis of some famous probabilistic algorithms and data structures in the proof assistant Isabelle/HOL. In particular, we consider the expected number of comparisons in randomised quicksort, the relationship between randomised quicksort and average-case deterministic quicksort, the expected shape of an unbalanced random Binary Search Tree, the randomised binary search trees described by Martínez and Roura, and the expected shape of a randomised treap. The last three have, to our knowledge, not been analysed using a theorem prover before and the last one is of particular interest because it involves continuous distributions.

We investigate the distribution of the number of vertices of a randomly chosen subtree of a tree. Specifically, it is proven that this distribution is close to a Gaussian distribution in an explicitly quantifiable way if the tree has sufficiently many leaves and no long branchless paths. We also show that the conditions are satisfied asymptotically almost surely for random trees. If the conditions are violated, however, we exhibit by means of explicit counterexamples that many other (non-Gaussian) distributions can occur in the limit. These examples also show that our conditions are essentially best possible.

We introduce the random exponential binary tree (EBT) and study its profile. As customary, the tree is extended by padding each leaf node (considered internal), with the appropriate number of external nodes, so that the outdegree of every internal node is made equal to 2. In a random EBT, at every step, each external node is promoted to an internal node with probability p, stays unchanged with probability 1 - p, and the resulting tree is extended. We study the internal and external profiles of a random EBT and get exact expectations for the numbers of internal and external nodes at each level. Asymptotic analysis shows that the average external profile is richest at level $\frac {2p}{p+1}n$ , and it experiences phase transitions at levels a n, where the a’s are the solutions to an algebraic equation. The rates of convergence themselves go through an infinite number of phase changes in the sublinear range, and then again at the nearly linear levels.

This paper deals with the efficiency of the search, with a method of organization and storage of the information that allows better results than the research trees or binary trees. No one ever dared to present better results than 0(log n) complexity, and when they wish to improve, they use balanced trees, but they continue to use principles that do not impact the pre-semantic information treatment. The Heru search method has as main characteristic the total or partial substitution of the use of the binary trees, enabling the elimination of the approximate results and informing the user the desired information instead of occurrences by sampling outside the desired information. The breakdown of the 0(log n) paradigm and the refinement of the searches are achieved with the use of a set of unpublished mathematical formulas and concepts called Infinite Series with Multiple Ratios.

Compression schemes for advanced data structures have become a central modern challenge. Information theory has traditionally dealt with conventional data such as text, images, or video. In contrast, most data available today is multitype and context-dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [8]. In this paper, we continue this program by considering trees with statistically correlated vertex names. Trees come in many forms, but here we deal with binary plane trees (where order of subtrees matters) and their non-plane version (where order of subtrees doesn’t matter). Furthermore, we assume that each name is generated by a known memoryless source (horizontal independence), but a symbol of a vertex name depends in a Markovian sense on the corresponding symbol of the parent vertex name (vertical Markovian dependency). Such a model is closely connected to models of phylogenetic trees. While in general the problem of multimodal compression and associated analysis can be extremely complicated, we find that in this natural setting, both the entropy analysis and optimal compression are analytically tractable. We evaluate the entropy for both types of trees. For the plane case, with or without vertex names, we find that a simple two-stage compression scheme is both efficient and optimal. We then present efficient and optimal compression algorithms for the more complicated non-plane case.

Let all vertices of a complete binary tree of finite height be independently and equiprobably labeled by the elements of some finite alphabet. We consider the numbers of pairs of identical tuples of labels on chains of subsequent vertices in the tree. Exact formulae for the expectations of these numbers are obtained. Convergence to the compound Poisson distribution is proved.

In this paper, we proposed the object classification method using genetic and dynamic random forest consisting of optimal combination of unit tree. The random forest can ensure good generalization performance in combination of large amount of trees by assigning the randomization to the training samples and feature selection, etc. allocated to the decision tree as an ensemble classification model which combines with the unit decision tree based on the bagging. However, the random forest is composed of unit trees randomly, so it can show the excellent classification performance only when the sufficient amounts of trees are combined. There is no quantitative measurement method for the number of trees, and there is no choice but to repeat random tree structure continuously. The proposed algorithm is composed of random forest with a combination of optimal tree while maintaining the generalization performance of random forest. To achieve this, the problem of improving the classification performance was assigned to the optimization problem which found the optimal tree combination. For this end, the genetic algorithm methodology was applied. As a result of experiment, we had found out that the proposed algorithm could improve about 3~5% of classification performance in specific cases like common database and self infrared database compare with the existing random forest. In addition, we had shown that the optimal tree combination was decided at 55~60% level from the maximum trees.

We introduce two models for random trees with multiple states motivated by studies of trait dependence in the evolution of species. Our discrete time model, the multiple state ERM tree, is a generalization of Markov propagation models on a random tree generated by a binary search or 'equal rates Markov' mechanism. Our continuous time model, the multiple state Yule tree, is a generalization of the tree generated by a pure birth or Yule process to the tree generated by multi-type branching processes. We study state dependent topological properties of these two random tree models. We derive asymptotic results that allow one to infer model parameters from data on states at the leaves and at branch-points that are one step away from the leaves.

In order to conduct a statistical analysis on a given set of phylogenetic gene trees, we often use a distance measure between two trees. In a statistical distance-based method to analyze discordance between gene trees, it is a key to decide "biological meaningful" and "statistically well-distributed" distance between trees. Thus, in this paper, we study the distributions of the three tree distance metrics: the edge difference, the path difference, and the precise $K$ interval cospeciation distance, between two trees: first, we focus on distributions of the three tree distances between two random unrooted trees with $n$ leaves ($n \geq 4$); and then we focus on the distributions the three tree distances between a fixed rooted species tree with $n$ leaves and a random gene tree with $n$ leaves generated under the coalescent process with given the species tree. We show some theoretical results as well as simulation study on these distributions., 18 pages, 11 figures

We propose an approach to embed the complete binary tree into the n-dimensional Mbius cube Mn.We prove that the complete binary tree with 2n1 vertices can be embedded with dilation 1, congestion 1, load 1 into Mn and expansion tending to 1.The research result in this paper demonstrates that embeddability of the complete binary tree in the n-dimensional Mbius cube is superior to that in the n-dimensional hypercube. The complete binary tree as an important network structure has long been investigated for parallel and distributed computing, which has many nice properties and used to be embedded into other interconnection architectures. The Mbius cube Mn is an important variant of the hypercube Qn. It has many better properties than Qn with the same number of edges and vertices. In this paper, we prove that the complete binary tree with 2n1 vertices can be embedded with dilation 1, congestion 1, load 1 into Mn and expansion tending to 1.

This paper proposes the use of binary trees for representing and managing the potentials involved in Influence Diagrams. This kind of tree allows representing context-specific independencies that are finer-grained compared to those encoded using other representations. This enhanced capability can be used to improve the efficiency of the inference algorithms used for Influence Diagrams. Moreover, binary trees allow computing approximate solutions when exact inference is not feasible. In this work we describe how binary trees can be used to perform this approximate evaluation and we compare them with other structures present in the literature.

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.

Binary tree is a very important data structure in computer science. Some major properties are discussed. Both recursive and non-recursive traversal methods of binary tree are discussed in detail. Some improvements in programming are proposed.

This work is a case study of the formal verification and complexity analysis of some famous probabilistic algorithms and data structures in the proof assistant Isabelle/HOL. In particular, we consider the expected number of comparisons in randomised quicksort, the relationship between randomised quicksort and average-case deterministic quicksort, the expected shape of an unbalanced random Binary Search Tree, and the expected shape of a Treap. The last two have, to our knowledge, not been analysed using a theorem prover before and the last one is of particular interest because it involves continuous distributions.

Binary relations play an important role in rough set theory. This paper investigates the similarity of binary relations based on L-fuzzy topologies, where L is a boolean algebra. First, rough approximations based on a boolean algebra are proposed through successor neighborhoods on binary relations. Next, L-fuzzy topologies induced by binary relations are investigated. Finally, similarity of binary relations is introduced by using the L-fuzzy topologies and the fact that every binary relation is solely similar to some preorder relation is proved. It is worth mentioning that similarity of binary relations are both originated in the L-fuzzy topology and independent of the L-fuzzy topology.

Although the distance between binary codes can be computed fast in Hamming space, linear search is not practical for large scale datasets. Therefore attention has been paid to the efficiency of performing approximate nearest neighbor search, in which hierarchical clustering trees (HCT) are widely used. However, HCT select cluster centers randomly and build indexes with the entire binary code, this degrades search performance. In this paper, we first propose a new clustering algorithm, which chooses cluster centers on the basis of relative distances and uses a more homogeneous partition of the dataset than HCT has to build the hierarchical clustering trees. Then, we present an algorithm to compress binary codes by extracting distinctive bits according to the standard deviation of each bit. Consequently, a new index is proposed using compressed binary codes based on hierarchical decomposition of binary spaces. Experiments conducted on reference datasets and a dataset of one billion binary codes demonstrate the effectiveness and efficiency of our method.

We analyze the estimation of the angle, scalar product, and the Euclidean distance of real-valued vectors using binary vectors with controlled sparsity. Transformation is carried out by projection using a binary random matrix with elements {0,1} and the output threshold transformation. We also provide a comparative analysis of the error obtained while estimating the similarity measures of input vectors by some similarity measures of output binary vectors based on their scalar product.

A new version of the RE-EM regression tree method for longitudinal and clustered data is presented. The RE-EM tree is a methodology that combines the structure of mixed effects models for longitudinal and clustered data with the flexibility of tree-based estimation methods. The RE-EM tree is less sensitive to parametric assumptions and provides improved predictive power compared to linear models with random effects and regression trees without random effects. The previously-suggested methodology used the CART tree algorithm for tree building, and therefore that RE-EM regression tree method inherits the tendency of CART to split on variables with more possible split points at the expense of those with fewer split points. A revised version of the RE-EM regression tree corrects for this bias by using the conditional inference tree as the underlying tree algorithm instead of CART. Simulation studies show that the new version is indeed unbiased, and has several improvements over the original RE-EM regression tree in terms of prediction accuracy and the ability to recover the correct tree structure.

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We continue the exploration. Our contributions are three: We systematically study the use of ranks and rank differences to define height-based balance in binary trees. Different invariants on rank differences yield AVL trees, red-black trees, and other kinds of balanced trees. By relaxing AVL trees, we obtain a new kind of balanced binary tree, the weak AVL tree (wavl tree) , whose properties we develop. Bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and at most two rotations, improving the three or more rotations per deletion needed in all other kinds of balanced trees of which we are aware. The height bound of a wavl tree degrades gracefully from that of an AVL tree as the number of deletions increases and is never worse than that of a red-black tree. Wavl trees also support top-down, fixed look-ahead rebalancing in O(1) amortized time. Finally, we use exponential potential functions to prove that in wavl trees rebalancing steps occur exponentially infrequently in rank. Thus, most of the rebalancing is at the bottom of the tree, which is crucial in concurrent applications and in those in which rotations take time that depends on the subtree size.

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.

By the example of perfect binary codes, we prove the existence of binary homogeneous nontransitive codes. Thereby, taking into account previously obtained results, we establish a hierarchical picture of extents of linearity for binary codes; namely, there is a strict inclusion of the class of binary linear codes in the class of binary propelinear codes, which are strictly included in the class of binary transitive codes, which, in turn, are strictly included in the class of binary homogeneous codes. We derive a transitivity criterion for perfect binary codes of rank greater by one than the rank of the Hamming code of the same length.

The information sources using logistic maps have been studied in this article. We use a particular symmetric binary function to generate the binary sequences due to the generating partition of the logistic maps, which can reflect the dynamics of chaotic real-valued sequences. Using this binary function, we will establish a binary description of the logistic maps, and prove that this description is equivalent with the logistic maps. The probability of all the possible binary sequences generated by this symmetric binary function has been calculated according to this description. Furthermore, the cryptographic complexity of these binary sequences is evaluated theoretically and experimentally, including the correlation functions, the linear complexity, the nonlinear complexity, the Lempel–Ziv complexity and the approximate entropy. Such results show that the logistic binary sequences have good properties of cryptography. © 2015 Wiley Periodicals, Inc. Complexity, 2015

We investigate protected nodes in random recursive trees. The exact mean of the number of such nodes is obtained by recurrence, and a linear asymptotic equivalent follows. A nonlinear recurrence for the variance shows that the variance grows linearly, too. It follows that the number of protected nodes in a random recursive tree, upon proper scaling, converges in probability to a constant.

We propose a transformation of real input vectors to output binary vectors by projection using a binary random matrix with elements {0,1} and thresholding. We investigate the rate of convergence of the distribution of vector components before binarization to the Gaussian distribution as well as its relationship to the estimation error of the angle between the input vectors by the binarized output vectors. It is shown that for the choice of projection parameters that provide nearly-Gaussian distribution, the experimental and analytical errors are close.

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.

A set of maximal non-intersecting diagonals can decompose a polygon into triangles, and the edges and diagonals can be converted into the external and internal nodes of a strictly binary tree. This paper gives algorithms to generate all types of triangulations and triangulations at random. Based on that, this paper gives an algorithm to generate strictly binary trees at random. The experimental results show that the numbers of various shapes of strictly binary trees generated are nearly equal. The algorithm to generate strictly binary trees at random can be transformed to the algorithm to randomly generate binary trees.

In this paper we introduce the Pitman Yor Diffusion Tree (PYDT), a Bayesian non-parametric prior over tree structures which generalises the Dirichlet Diffusion Tree [30] and removes the restriction to binary branching structure. The generative process is described and shown to result in an exchangeable distribution over data points. We prove some theoretical properties of the model including showing its construction as the continuum limit of a nested Chinese restaurant process model. We then present two alternative MCMC samplers which allow us to model uncertainty over tree structures, and a computationally efficient greedy Bayesian EM search algorithm. Both algorithms use message passing on the tree structure. The utility of the model and algorithms is demonstrated on synthetic and real world data, both continuous and binary.

Given an undirected planar graph G with n vertices and a set S of n points inside a simple polygon P, a point-set embedding of G on S is a planar drawing of G such that each vertex is mapped to a distinct point of S and the edges are polygonal chains surrounded by P. A special case of the embedding problem is that in which G is a balanced binary tree. In this paper, we present a new algorithm for embedding an n-vertex balanced binary tree BBT on a set S of n points inside a simple m-gon P in O(m4/3+ϵ + nlog2 n + m log n) time with at most O(m) bends per edge.

The Wiener index has been studied for simply generated random trees, nonplane unlabeled random trees, and a huge subclass of random grid trees containing random binary search trees, random median-of-(2k+1) search trees, random $m$-ary search trees, random quadtrees, random simplex trees, etc. An important class of random grid trees for which the Wiener index was not studied so far is random digital trees. In this work, we close this gap. More precisely, we derive asymptotic expansions of moments of the Wiener index and show that a central limit law for the Wiener index holds. These results are obtained for digital search trees and bucket versions as well as tries and PATRICIA tries. Our findings answer in the affirmative two questions posed by Neininger.

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.

This paper presents a new, linear algorithm for performing the roll operation on binary trees. Based on the inorder tree traversal, this algorithm has a very simple structure and achieves linear time and space complexity. A detailed analysis of this algorithm is presented, showing how its design contributes to a more streamlined operation and an improved time complexity over the original — and only other known to the authors — binary tree roll algorithm. A practical implementation of both algorithms is benchmarked by counting the minimum and maximum numbers of basic operations, as well as measuring the minimum and maximum amounts of memory space required by the algorithms to run to completion, across all binary tree topologies with progressively increasing numbers of nodes. Results obtained from this empirical analysis quantify the best-and worst-case complexities of both algorithms and show how the improved algorithm outperforms the original one asymptotically, particularly in regards to their time complexity.

We continue developing the information theory of advanced data structures. In our previous work, we introduced structural entropy of unlabeled graphs and designed lossless compression algorithms for binary trees (with structure-correlated vertex names). In this paper, we consider d-ary trees (d ≥ 2) and trees with unrestricted degree for which we compute the entropy (the first step to design optimal compression algorithms). It turns out that extending from binary trees to general trees is mathematically quite challenging and leads to new recurrences that find ample applications in the information theory of structures.

We present two related results on the prefix tree of all binary cube-free words. First, we show that non-branching paths in this tree are short: such a path from a node of nth level has length \(O(\log n)\). Second, we prove that the lower density of the set of branching points along any infinite path is at least 23/78. Our results are based on a technical theorem describing the mutual location of “almost cubes” in a cube-free word.

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.

Author(s): Evans, SN; Grubel, R; Wakolbinger, A | Abstract: Remy's algorithm is a Markov chain that iteratively generates a sequence of random trees in such a way that the nth tree is uniformly distributed over the set of rooted, planar, binary trees with 2n + 1 vertices. We obtain a concrete characterization of the Doob-Martin boundary of this transient Markov chain and thereby delineate all the ways in which, loosely speaking, this process can be conditioned to "go to infinity" at large times. A (deterministic) sequence of finite rooted, planar, binary trees converges to a point in the boundary if for each m the random rooted, planar, binary tree spanned by m + 1 leaves chosen uniformly at random from the nth tree in the sequence converges in distribution as n tends to infinity-a notion of convergence that is analogous to one that appears in the recently developed theory of graph limits. We show that a point in the Doob-Martin boundary may be identified with the following ensemble of objects: a complete separable ℝ-tree that is rooted and binary in a suitable sense, a diffuse probability measure on the R-tree that allows us to make sense of sampling points from it, and a kernel on the R-tree that describes the probability that the first of a given pair of points is below and to the left of their most recent common ancestor while the second is below and to the right. Two such ensembles represent the same point in the boundary if for each m the random, rooted, planar, binary trees spanned by m + 1 independent points chosen according to the respective probability measures have the same distribution. Also, the Doob-Martin boundary corresponds bijectively to the set of extreme point of the closed convex set of nonnegative harmonic functions that take the value 1 at the binary tree with 3 vertices; in other words, the minimal and full Doob-Martin boundaries coincide. These results are in the spirit of the identification of graphons as limit objects in the theory of graph limits.

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.

In phylogenetics, a common strategy used to construct an evolutionary tree for a set of species $$X$$ is to search in the space of all such trees for one that optimizes some given score function (such as the minimum evolution, parsimony or likelihood score). As this can be computationally intensive, it was recently proposed to restrict such searches to the set of all those trees that are compatible with some circular ordering of the set $$X$$ . To inform the design of efficient algorithms to perform such searches, it is therefore of interest to find bounds for the number of trees compatible with a fixed ordering in the neighborhood of a tree that is determined by certain tree operations commonly used to search for trees: the nearest neighbor interchange (nni), the subtree prune and regraft (spr) and the tree bisection and reconnection (tbr) operations. We show that the size of such a neighborhood of a binary tree associated with the nni operation is independent of the tree’s topology, but that this is not the case for the spr and tbr operations. We also give tight upper and lower bounds for the size of the neighborhood of a binary tree for the spr and tbr operations and characterize those trees for which these bounds are attained.

Pallo and Wu et al. respectively introduced the left-weight sequences (LW-sequences) and right-weight sequences (RW-sequences) for representing binary trees. In this paper, we introduce two new types of binary tree sequences called the left-child sequences (LC-sequences) and right-child sequences (RC-sequences). Next, we propose a loopless algorithm associated with rotations of binary trees for generating LW-, RW-, LC-, and RC-sequences simultaneously. Moreover, we show that LW- and RW-sequences are generated in Gray-code order, and LC- and RC-sequences are generated so that each sequence can be obtained from its predecessor by changing at most two digits. Our algorithm is shown to be more efficient in both space and time than the existing known algorithms.

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.

In this article, a novel technique IRUSRT (inverse random under sampling and random tree) by combining inverse random under sampling and random tree is proposed to implement imbalanced learning. The main idea is to severely under sample the majority class thus creating multiple distinct training sets. With each training set, a random tree is trained to separate the minority class from the majority class. By combining these random trees through fusion, a composite classifier is constructed. The experimental analysis on 23 real-world datasets assessed over area under the ROC curve (AUC), F-measure, and G-mean indicates that IRUSRT performs significantly better when compared with many existing class imbalance learning methods.

Suppose a finite population of several vertices, each connected to single or multiple edges. This constitutes a structure of graphical population of vertices and edges. As a special case, the graphical population like a binary tree having only two child vertices associated to parent vertex is taken into consideration. The entire binary tree is divided into two sub-graphs such as a group of left-nodes and a group of right-nodes. This paper takes into account a mixture of graph structured and population sampling theory together and presents a methodology for mean-edge-length estimation of left sub-graph using right edge sub-graph as an auxiliary source of information. A node-sampling procedure is developed for this purpose and a class of estimators is proposed containing several good estimators. Mathematical conditions for minimum bias and optimum mean squared error of the class are derived and theoretical results are numerically supported with a test of 99% confidence intervals. It is shown that suggested ...

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 enumeration of binary trees containing noncontiguous binary tree patterns. First, we show that any two ℓ-leaf binary trees are contained in the set of all n-leaf trees the same number of times. We give a functional equation for the multivariate generating function for number of n-leaf trees containing a specified number of copies of any path tree, and we analyze tree patterns with at most 4 leaves. The paper concludes with implications for pattern containment in permutations.

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