Xingbo Wang, Jinfeng Luo, Ying Tian · 2021
The paper investigates the properties and the factoring method of a kind of odd integers whose divisors are like those of the Fermat numbers. By means of the valuated binary tree, an odd integer N is turned to be a node of a tree whose root is helpful and easy to find out the small divisor of N. The paper finds out an approach to realize such a tree-factoring idea. Theoretic analyses for the approach are proved with strict mathematical reasonings, a deterministic framework as well as a random-walk framework is proposed to perform the factorization and numerical experiments are made to factorize some Fermat numbers. Experiments show that the random-walk method is in general faster than what were known in the past, which reveals that factorization of an odd integer can be done by means of a random walk on a valuated binary tree.
Cited by 0
Éva Czabarka · ISU Red - Research and eData (Illinois State University) · 2016
Leaf-labeled binary trees (a.k.a.phylogenetic trees) and tanglegrams are of interest to biologists.For a rooted binary tree on n leaves, any subset of k leaves induces a rooted binary tree by taking all paths connecting these leaves, placing the new root on the vertex closest to the original root of the tree, and suppressing all non-root degree two vertices in the resulting tree.The inducibility of a k-leaf rooted binary tree in an n-leaf rooted binary tree is the proportion of k-subsets of leaves that induce a tree isomorphic to that tree; the inducibility of any rooted binary tree is the limit superior of its inducibility in any sequence of binary trees.We show a number of results on the inducibility of certain types of binary trees that we use to estimate the expected crossing number of tanglegrams.A tanglegram is a pair of rooted binary trees on the same number of leaves with a fixed matching on the leaves; its crossing number is the minimum number of crossings we can have when we draw this in the plane such that the two binary trees are drawn as plane trees and the crossings are only allowed on the edges corresponding to the given matchings.The tanglegram crossing number is used to estimate relevant biological quantities (e.g. in parasite-host trees).We show that the expected value of tangregram crossing number in a random tanglegram on n-leaf trees is (n 2 ), i.e. as large as possible.
Cited by 0Open access
Qiang Zhang, Mike Steel · ArXiv.org · 2025
Rooted phylogenetic networks allow biologists to represent evolutionary relationships between present-day species by revealing ancestral speciation and hybridization events. A convenient and well-studied class of such networks are `tree-child networks' and a `ranking' of such a network is a temporal ordering of the ancestral speciation and hybridization events. In this short note, we investigate the question of counting such rankings on any given binary (or semi-binary) tree-child network. We also consider a class of binary tree-child networks that have exactly one ranking, and investigate further the relationship between ranked-tree child networks and the class of `normal' networks. Finally, we provide an explicit asymptotic expression for the expected number of rankings of a tree-child network chosen uniformly at random.
Cited by 0Open access
Alexandra Vormberg (3698203), Felix Effenberger (792048), Julia Muellerleile (4220431) et al. · Figshare · 2017
<p><b>A</b>. Sample binary trees taken from all possible 9,694,845 unsorted and 10,905 sorted trees of degree 16. Coloured dots denote node SO (black– 1, green– 2, red– 3, blue– 4, cyan– 5). <b>B</b>. Depiction of all possible distributions of segment numbers with SO in binary trees of degree 16; distributions for different trees are coloured differently. Bold green and bold magenta lines show distributions for the so-called “herringbone” tree (green box in A) and for the complete binary tree (magenta box in A), respectively. <b>C</b>. All possible distributions of branch numbers with SO in binary trees of degree 16. Bold green and bold magenta lines show distribution for the “herringbone” tree and for the complete binary tree, respectively. Bold grey line shows distribution for a tree that follows the trend of 4<sup>1−<i>k</i></sup> for SO <i>k</i> from dashed lines in E and H. <b>D</b>. Averages (lines with markers) and standard deviations (shaded areas) of normalised segment number distributions with SO for all possible sorted and unsorted binary trees of degree 16 divided into trees of segment Strahler number (SN) 2, 3, and 4. Dashed line indicates the distribution obtained from a complete binary tree (see main text). <b>E</b>. Similar to D but with normalised branch number distributions. Dashed line here indicates the asymptotic power relation obtained for large random binary trees (see main text). <b>F</b>. Sketch illustrating the Galton-Watson (GW) type random branching process. Terminal nodes either stop growing or branch out with probabilities <i>P</i><sub><i>st</i></sub> = 0.5 (red) and <i>P</i><sub><i>br</i></sub> = 0.5 (blue), respectively. <b>G, H</b>. Similar to D and E but for GW random binary trees divided into groups of SN 2–6. <b>I</b>. Branch bifurcation ratio between subsequent orders for the same GW random binary trees as in G and H. Magenta line indicates lower bound (see main text) and grey line denotes asymptotic bifurcation ratio for large random binary trees (see main text). <b>J</b>. Average (lines with markers) and standard deviations (shaded areas) of normalised topological subtree sizes for all topological nodes as a function of SO in GW random binary trees divided into SN 3–6. Magenta dashed line indicates relation obtained for a complete binary tree (CBT) of node SN 6 (see main text). Grey dashed lines represent mirror images (4<sup><i>k</i>−<i>SN</i></sup>, for SO <i>k</i> and SN 3–6) of the power relation in E (see main text). Note that in segment distributions per SO such as in D and G, nearly half of the segments are terminal segments (i.e. SO 1) in all cases, a property of binary trees.</p>
Cited by 0Open access
Franz Rembart, Matthias Winkel · arXiv (Cornell University) · 2016
We embed Duquesne and Le Gall's stable tree into a binary compact continuum random tree (CRT) in a way that solves an open problem posed by Goldschmidt and Haas. This CRT can be obtained by applying a recursive construction method of compact CRTs as presented in earlier work to a specific distribution of a random string of beads, i.e. a random interval equipped with a random discrete measure. We also express this CRT as a tree built by replacing all branch points of a stable tree by rescaled i.i.d. copies of a Ford CRT. Some of these developments are carried out in a space of infinity-marked metric spaces generalising Miermont's notion of a k-marked metric space.
Cited by 0Open access
Evans, SN, Grübel, R, Wakolbinger, A · eScholarship (California Digital Library) · 2017
© Institute of Mathematical Statistics, 2017. Rémy'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.
Cited by 0Open access
Svante Janson · 2009
Abstract. We study the difference between the left and right total pathlengths in a random binary tree. The results include exact and asymptotic formulas for moments and an asymptotic distribution that can be expressed in terms of either the Brownian snake or ISE. The proofs are based on computing expectations for a subcritical binary Galton– Watson tree, and studying asymptotics as the Galton–Watson process approaches a critical one. 1.
Cited by 0
David R. Karger, Philip N. Klein, Robert E. Tarjan · 1995
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
Cited by 0
David R. Karger, Philip N. Klein, Robert E. Tarjan · Journal of the ACM · 1995
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
Cited by 402Open access
Suri Pushpa, Prasad Vinod · 2008
Binary search tree is a best-suited data structure for data storage and retrieval when entire tree could be accommodated in the primary memory. However, this is true only when the tree is height-balanced. Lesser the height faster the search will be. Despite of the wide popularity of Binary search trees there has been a major concern to maintain the tree in proper shape. In worst case, a binary search tree may reduce to a linear link list, thereby reducing search to be sequential. Unfortunately, structure of the tree depends on nature of input. If input keys are not in random order the tree will become higher and higher on one side. In addition to that, the tree may become unbalanced after a series of operations like insertions and deletions. To maintain the tree in optimal shape many algorithms have been presented over the years. Most of the algorithms are static in nature as they take a whole binary search tree as input to create a balanced version of the tree. In this paper, few techniques have been discussed and analyzed in terms of time and space requirement. Key words:
Cited by 0
J. F. Bell, Gopal Gupta · Software Practice and Experience · 1993
Abstract Much has been said in praise of self‐adjusting data structures, particularly self‐adjusting binary search trees. Self‐adjusting trees are most suited to skewed key‐access distributions as the techniques attempt to place the most commonly accessed keys near the root of the tree. Theoretical bounds on worst‐case and amortized performance (i.e. performance over a sequence of operations) have been derived which compare well with those for optimal binary search trees. In this paper, we compare the performance of three different techniques for self‐adjusting trees with that of AVL and random binary search trees. Comparisons are made for various tree sizes, levels of key‐access‐frequency skewness and ratios of insertions and deletions to searches. The results show that, because of the high cost of maintaining self‐adjusting trees, in almost all cases the AVL tree outperforms all the self‐adjusting trees and in many cases even a random binary search tree has better performance, in terms of CPU time, than any of the self‐adjusting trees. Self‐adjusting trees seem to perform best in a highly dynamic environment, contrary to intuition.
Cited by 32
Luc Devroye · 2005
Abstract. Under certain conditions, sums of functions of subtrees of a random binary search tree are asymptotically normal. We show how Stein’s method can be applied to study these random trees, and survey methods for obtaining limit laws for such functions of subtrees.
Cited by 0
Buck, Jamis · 2015
Part I. The basics : Your first random mazes : Preparing the grid ; The binary tree algorithm ; The sidewinder algorithm -- Automating and displaying your mazes : Introducing our basic grid ; Displaying a maze on a terminal ; Implementing the binary tree algorithm ; Rendering a maze as an image -- Finding solutions : Dijkstra's algorithm ; Implementing Dijkstra's ; Finding the shortest path ; Making challenging mazes ; Coloring your mazes -- Avoiding bias with random walks : Understanding biases ; The Aldous-Broder algorithm ; Implementing Aldous-Broder ; Wilson's algorithm ; Implementing Wilson's algorithm -- Adding constraints to random walks : The hunt-and-kill algorithm ; Implementing hunt-and-kill ; Counting dead ends ; The recursive backtracker algorithm ; Implementing the recursive backtracker -- Part II. New steps : Fitting mazes to shapes : Introducing masking ; Implementing a mask ; ASCII masks ; Image masks --
Cited by 2
Susann Vorberg (5931470), Stefan Seemayer (5931473), Johannes Söding (9982) · Figshare · 2018
<p>CCMgen can generate multiple sequence alignments (MSAs) based on a Markov random field (MRF) model and a phylogenetic tree supplied either as Newick file or as one of the two shown, idealized topologies: <b>A</b> binary tree and <b>B</b> star-shaped tree.</p>
Cited by 0Open access
Fei Gao, Dongfeng Zhao · 2002
The tree-based algorithm is an important contention resolution mechanism that was applied to the random multi-access channel. This paper reported an improved Q-ary tree algorithms (ITA/sub Q/) scheme. The theoretical analyses and computer simulation indicate that the performance of ITAQ is better than the basic binary and ternary tree algorithm at throughput and access delay.
Cited by 1
Meng He, Richard Peng, Yinzhan Xu · Society for Industrial and Applied Mathematics eBooks · 2018
We study a new way of measuring the expected performance of various binary search tree algorithms that is between the worst and the average case. Our starting point is the correspondence between binary search trees and insertion sequences, and we will measure the difficulty of such sequences based on inversion counts. This measure naturally interpolates between random and sequential insertion orders. We show that if the tree is randomly picked from all trees built upon insertion length n permutations with t inversions, the height of the tree can be bounded by .
Cited by 0Open access
Janson, Svante · arXiv (Cornell University) · 2020
We explore the tree limits recently defined by Elek and Tardos. In particular, we find tree limits for many classes of random trees. We give general theorems for three classes of conditional Galton-Watson trees and simply generated trees, for split trees and generalized split trees (as defined here), and for trees defined by a continuous-time branching process. These general results include, for example, random labelled trees, ordered trees, random recursive trees, preferential attachment trees, and binary search trees.
Cited by 0Open access
Kai Xiong · 2014
Binary classification plays an important role in many decision-making processes. Random forests can build a strong ensemble classifier by combining weaker classification trees that are de-correlated. The strength and correlation among individual classification trees are the key factors that contribute to the ensemble performance of random forests. We propose roughened random forests, a new set of tools which show further improvement over random forests in binary classification. Roughened random forests modify the original dataset for each classification tree and further reduce the correlation among individual classification trees. This data modification process is composed of artificially imposing missing data that are missing completely at random and subsequent missing data imputation.
Cited by 0Open access
Olivier Bodini, Antoine Genitrini, Khaydar Nurligareev · SPIRE - Sciences Po Institutional REpository · 2026
This paper introduces a new combinatorial framework for modeling the growth of binary trees through a discrete evolution process that incorporates a growing rule and an extinction rule. Building upon the theory of increasingly labeled structures and the analysis of polynomial iterates, we extend previous models of increasing trees with label repetitions by allowing growth branches to terminate. This mechanism enables a direct connection between dynamic evolutionary processes and classical unlabeled binary trees. We provide a combinatorial outlook for this model, linking our new approach to essential but traditionally complex parameters such as tree height, the maximum number of leaves at the deepest level (for a given tree size), and the overall tree profile. Our approach reveals structural links with Mandelbrot polynomials and coding theory. Furthermore, we leverage these structural insights to develop an efficient, iterative uniform random sampler for binary trees with a prescribed profile, achieving optimal complexity in both time and space and in random bit consumption.
Cited by 0Open access
O. I. Sheluhin, Mikhail Kazhemskiy · Automatic Control and Computer Sciences · 2020
In this paper, it is proposed to improve the efficiency of binary classification of network traffic anomalous behavior by introducing an additional informative feature – fractal dimension. The overall effectiveness of the proposed method is estimated by evaluating the quality of binary classification using the algorithms Decision Tree Classifier, Random Forest and Ada Boost on the example of using the NSL-KDD database. It is shown that adding the fractal dimension in the binary classification of attacks, gives improvement of the precision metric in average by 6%, and for AUC-ROC about 10% for all considered classification algorithms. Furthermore, introduction of fractal dimension as an additional feature has allowed to significantly reduce the time of training and testing of binary classification. So, for the Random Forest algorithm, the decrease in processing time was more than 3 times, and for the Decision Tree Classifier more than 2 times.
Cited by 11