Average Case Analysis of Leaf-Centric Binary Tree Sources
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2018
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913810636341248 |
|---|---|
| author | Benkner, Louisa Seelbach Lohrey, Markus Wagner, Stephan |
| author_facet | Benkner, Louisa Seelbach Lohrey, Markus Wagner, Stephan |
| contents | We study the average number of distinct fringe subtrees in 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. We generalize a result by Flajolet, Gourdon, Martinez and Devroye, according to which the average number of distinct fringe subtrees in a random binary search tree of size $n$ is in $Θ(n/\log n)$, as well as a result by Flajolet, Sipala and Steayert, according to which the number of distinct fringe subtrees in a uniformly random binary tree of size $n$ is in $Θ(n/\sqrt{\log n})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1804_10396 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Average Case Analysis of Leaf-Centric Binary Tree Sources Benkner, Louisa Seelbach Lohrey, Markus Wagner, Stephan Discrete Mathematics Information Theory Combinatorics 68P30 We study the average number of distinct fringe subtrees in 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. We generalize a result by Flajolet, Gourdon, Martinez and Devroye, according to which the average number of distinct fringe subtrees in a random binary search tree of size $n$ is in $Θ(n/\log n)$, as well as a result by Flajolet, Sipala and Steayert, according to which the number of distinct fringe subtrees in a uniformly random binary tree of size $n$ is in $Θ(n/\sqrt{\log n})$. |
| title | Average Case Analysis of Leaf-Centric Binary Tree Sources |
| topic | Discrete Mathematics Information Theory Combinatorics 68P30 |
| url | https://arxiv.org/abs/1804.10396 |