Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 561-578 |
| Seitenumfang | 18 |
| Fachzeitschrift | Combinatorics Probability and Computing |
| Jahrgang | 19 |
| Ausgabenummer | 4 |
| Frühes Online-Datum | 22 Jan. 2010 |
| Publikationsstatus | Veröffentlicht - 4 Juli 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 Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Mathematik (insg.)
- Statistik und Wahrscheinlichkeit
- Informatik (insg.)
- Theoretische Informatik und Mathematik
- Mathematik (insg.)
- Angewandte Mathematik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Combinatorics Probability and Computing, Jahrgang 19, Nr. 4, 04.07.2010, S. 561-578.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -