Fringe trees of Patricia tries, compressed binary search trees, and three other random full 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_ | 1866912867127656448 |
|---|---|
| author | Janson, Svante |
| author_facet | Janson, Svante |
| contents | We study the distribution of fringe trees in Patricia tries (extending earlier results by Ischebeck (2025)) and compressed binary search trees; both cases are random binary trees that have been compressed by deleting nodes of outdegree 1 so that they are random full binary trees. The main results are central limit theorems for the number of fringe trees of a given type, which imply quenched and annealed limit results for the fringe tree distribution; for Patricia tries, this is complicated by periodic oscillations in the usual manner. We also consider extended fringe trees. The results are derived from earlier results for uncompressed tries and binary search trees. In the case of compressed binary search trees, it seems difficult to give a closed formula for the asymptotic fringe tree distribution, but we provide a recursion and give examples.
For comparison, we give also results, simpler and partly known, for three other models of random full binary trees: the extended binary search tree, the critical beta-spltting random tree, and the uniform random full binary tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_01239 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fringe trees of Patricia tries, compressed binary search trees, and three other random full binary trees Janson, Svante Probability Combinatorics 60C05, 05C05, 60F05 We study the distribution of fringe trees in Patricia tries (extending earlier results by Ischebeck (2025)) and compressed binary search trees; both cases are random binary trees that have been compressed by deleting nodes of outdegree 1 so that they are random full binary trees. The main results are central limit theorems for the number of fringe trees of a given type, which imply quenched and annealed limit results for the fringe tree distribution; for Patricia tries, this is complicated by periodic oscillations in the usual manner. We also consider extended fringe trees. The results are derived from earlier results for uncompressed tries and binary search trees. In the case of compressed binary search trees, it seems difficult to give a closed formula for the asymptotic fringe tree distribution, but we provide a recursion and give examples. For comparison, we give also results, simpler and partly known, for three other models of random full binary trees: the extended binary search tree, the critical beta-spltting random tree, and the uniform random full binary tree. |
| title | Fringe trees of Patricia tries, compressed binary search trees, and three other random full binary trees |
| topic | Probability Combinatorics 60C05, 05C05, 60F05 |
| url | https://arxiv.org/abs/2405.01239 |