A note on limits of sequences of binary trees

Research output: Contribution to journal › Article › Research › peer review

Authors

  • Rudolf Grübel

Research Organisations

View graph of relations

Details

Original languageEnglish
Number of pages15
JournalDiscrete Mathematics and Theoretical Computer Science
Volume25
Issue number1
Publication statusPublished - 30 May 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.

Keywords

    Asymptotics, binary search trees, binary trees, digital search trees, Gaussian process, subtree size convergence

ASJC Scopus subject areas

Cite this

A note on limits of sequences of binary trees. / Grübel, Rudolf.
In: Discrete Mathematics and Theoretical Computer Science, Vol. 25, No. 1, 30.05.2023.

Research output: Contribution to journal › Article › Research › peer review

Grübel, R 2023, 'A note on limits of sequences of binary trees', Discrete Mathematics and Theoretical Computer Science, vol. 25, no. 1. https://doi.org/10.48550/arXiv.2302.07850, https://doi.org/10.46298/DMTCS.10968
Grübel, R. (2023). A note on limits of sequences of binary trees. Discrete Mathematics and Theoretical Computer Science, 25(1). https://doi.org/10.48550/arXiv.2302.07850, https://doi.org/10.46298/DMTCS.10968
Grübel R. A note on limits of sequences of binary trees. Discrete Mathematics and Theoretical Computer Science. 2023 May 30;25(1). doi: 10.48550/arXiv.2302.07850, 10.46298/DMTCS.10968
Grübel, Rudolf. / A note on limits of sequences of binary trees. In: Discrete Mathematics and Theoretical Computer Science. 2023 ; Vol. 25, No. 1.
Download
@article{348969e11dc74f76810677bd6c04d1f7,
title = "A note on limits of sequences of binary trees",
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.",
keywords = "Asymptotics, binary search trees, binary trees, digital search trees, Gaussian process, subtree size convergence",
author = "Rudolf Gr{\"u}bel",
note = "Publisher Copyright: {\textcopyright} 2023 by the author(s)",
year = "2023",
month = may,
day = "30",
doi = "10.48550/arXiv.2302.07850",
language = "English",
volume = "25",
number = "1",

}

Download

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 -