Details
| Originalsprache | Englisch |
|---|---|
| Seitenumfang | 15 |
| Fachzeitschrift | Discrete Mathematics and Theoretical Computer Science |
| Jahrgang | 25 |
| Ausgabenummer | 1 |
| Publikationsstatus | Veröffentlicht - 30 Mai 2023 |
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.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
- Mathematik (insg.)
- Diskrete Mathematik und Kombinatorik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Discrete Mathematics and Theoretical Computer Science, Jahrgang 25, Nr. 1, 30.05.2023.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review
}
TY - JOUR
T1 - A note on limits of sequences of binary trees
AU - Grübel, Rudolf
N1 - Publisher Copyright: © 2023 by the author(s)
PY - 2023/5/30
Y1 - 2023/5/30
N2 - 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.
AB - 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.
KW - Asymptotics
KW - binary search trees
KW - binary trees
KW - digital search trees
KW - Gaussian process
KW - subtree size convergence
UR - http://www.scopus.com/inward/record.url?scp=85165914286&partnerID=8YFLogxK
U2 - 10.48550/arXiv.2302.07850
DO - 10.48550/arXiv.2302.07850
M3 - Article
AN - SCOPUS:85165914286
VL - 25
JO - Discrete Mathematics and Theoretical Computer Science
JF - Discrete Mathematics and Theoretical Computer Science
SN - 1462-7264
IS - 1
ER -