A note on limits of sequences of binary trees

DOI10.46298/DMTCS.10968arXiv2302.07850MaRDI QIDQ6131798FDOQ6131798

Authors: Rudolf Grübel 

Publication date: 18 April 2024

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2302.07850

Recommendations

• Search trees: metric aspects and strong limit theorems
• Limit theorems for sequences of random trees
• Tree limits and limits of random trees
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• On the subtrees of random binary search trees

zbMATH Keywords

asymptoticsGaussian processbinary treesbinary search treesdigital search treessubtree size convergence

Mathematics Subject Classification ID

Trees (05C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Cited In (3)

• Limits of Mallows trees
• Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
• Binary search trees of permuton samples

This page was built for publication: A note on limits of sequences of binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131798)