Upper Bounds on the Average Height of Random Binary Trees
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917677449084928 |
|---|---|
| author | Benkner, Louisa Seelbach |
| author_facet | Benkner, Louisa Seelbach |
| contents | We study the average height of random trees generated by leaf-centric binary tree sources as introduced by Zhang, Yang and Kieffer. A leaf-centric binary tree source induces for every $n \geq 2$ a probability distribution on the set of binary trees with $n$ leaves. Our results generalize a result by Devroye, according to which the average height of a random binary search tree of size $n$ is in $\mathcal{O}(\log n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17952 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Upper Bounds on the Average Height of Random Binary Trees Benkner, Louisa Seelbach Combinatorics Discrete Mathematics We study the average height of random trees generated by leaf-centric binary tree sources as introduced by Zhang, Yang and Kieffer. A leaf-centric binary tree source induces for every $n \geq 2$ a probability distribution on the set of binary trees with $n$ leaves. Our results generalize a result by Devroye, according to which the average height of a random binary search tree of size $n$ is in $\mathcal{O}(\log n)$. |
| title | Upper Bounds on the Average Height of Random Binary Trees |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2405.17952 |