Details
| Original language | English |
|---|---|
| Pages (from-to) | 561-578 |
| Number of pages | 18 |
| Journal | Combinatorics Probability and Computing |
| Volume | 19 |
| Issue number | 4 |
| Early online date | 22 Jan 2010 |
| Publication status | Published - 4 Jul 2010 |
Abstract
For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ ℕ to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye, by Feng, Mahmoud and Panholzer, and by Fuchs, we obtain results for the range of small k-values and the range of k-values proportional to the size n of T. In both cases emphasis is on the process view, i.e., the joint distributions for several k-values. We also show that the dynamics of the tree sequence lead to a qualitative difference between the asymptotic behaviour of the lower and the upper end of the profile.
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Mathematics(all)
- Statistics and Probability
- Computer Science(all)
- Computational Theory and Mathematics
- Mathematics(all)
- Applied Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Combinatorics Probability and Computing, Vol. 19, No. 4, 04.07.2010, p. 561-578.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - On the subtree size profile of binary search trees
AU - Dennert, Florian
AU - Grübel, Rudolf
PY - 2010/7/4
Y1 - 2010/7/4
N2 - For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ ℕ to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye, by Feng, Mahmoud and Panholzer, and by Fuchs, we obtain results for the range of small k-values and the range of k-values proportional to the size n of T. In both cases emphasis is on the process view, i.e., the joint distributions for several k-values. We also show that the dynamics of the tree sequence lead to a qualitative difference between the asymptotic behaviour of the lower and the upper end of the profile.
AB - For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ ℕ to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye, by Feng, Mahmoud and Panholzer, and by Fuchs, we obtain results for the range of small k-values and the range of k-values proportional to the size n of T. In both cases emphasis is on the process view, i.e., the joint distributions for several k-values. We also show that the dynamics of the tree sequence lead to a qualitative difference between the asymptotic behaviour of the lower and the upper end of the profile.
UR - http://www.scopus.com/inward/record.url?scp=77955773100&partnerID=8YFLogxK
U2 - 10.1017/S0963548309990630
DO - 10.1017/S0963548309990630
M3 - Article
AN - SCOPUS:77955773100
VL - 19
SP - 561
EP - 578
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
SN - 0963-5483
IS - 4
ER -