
arXiv: 2302.07850
We discuss a notion of convergence for binary trees that is based on subtree sizes. In analogy to recent developments in the theory of graphs, posets and permutations we investigate some general aspects of the topology, such as a characterization of the set of possible limits and its structure as a metric space. For random trees the subtree size topology arises in the context of algorithms for searching and sorting when applied to random input, resulting in a sequence of nested trees. For these we obtain a structural result based on a local version of exchangeability. This in turn leads to a central limit theorem, with possibly mixed asymptotic normality.
mathematics - combinatorics, digital search trees, Trees, 510, subtree size convergence, QA1-939, FOS: Mathematics, binary trees, Mathematics - Combinatorics, Gaussian process, mathematics - probability, Combinatorial probability, Probability (math.PR), Markov chains (discrete-time Markov processes on discrete state spaces), 05c05, 60c05, 68w40, 004, asymptotics, binary search trees, 05C05, 60C05, 68W40, Combinatorics (math.CO), Asymptotics, Mathematics, Mathematics - Probability
mathematics - combinatorics, digital search trees, Trees, 510, subtree size convergence, QA1-939, FOS: Mathematics, binary trees, Mathematics - Combinatorics, Gaussian process, mathematics - probability, Combinatorial probability, Probability (math.PR), Markov chains (discrete-time Markov processes on discrete state spaces), 05c05, 60c05, 68w40, 004, asymptotics, binary search trees, 05C05, 60C05, 68W40, Combinatorics (math.CO), Asymptotics, Mathematics, Mathematics - Probability
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
