dc.identifier.uri |
http://dx.doi.org/10.15488/2695 |
|
dc.identifier.uri |
http://www.repo.uni-hannover.de/handle/123456789/2721 |
|
dc.contributor.author |
Dennert, Florian
|
|
dc.contributor.author |
Grübel, Rudolf
|
|
dc.date.accessioned |
2018-01-29T14:13:18Z |
|
dc.date.available |
2018-01-29T14:13:18Z |
|
dc.date.issued |
2010 |
|
dc.identifier.citation |
Dennert, F.; Grübel, R.: On the subtree size profile of binary search trees. In: Combinatorics Probability and Computing 19 (2010), Nr. 4, S. 561-578. DOI: https://doi.org/10.1017/S0963548309990630 |
|
dc.description.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. Copyright © 2010 Cambridge University Press. |
eng |
dc.language.iso |
eng |
|
dc.publisher |
Cambridge : Cambridge University Press |
|
dc.relation.ispartofseries |
Combinatorics, Probability and Computing 19 (2010), Nr. 4 |
|
dc.rights |
Es gilt deutsches Urheberrecht. Das Dokument darf zum eigenen Gebrauch kostenfrei genutzt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden. Dieser Beitrag ist aufgrund einer (DFG-geförderten) Allianz- bzw. Nationallizenz frei zugänglich. |
|
dc.subject |
Asymptotic behaviour |
eng |
dc.subject |
Binary search tree algorithms |
eng |
dc.subject |
Binary search trees |
eng |
dc.subject |
Joint distributions |
eng |
dc.subject |
K-values |
eng |
dc.subject |
Process view |
eng |
dc.subject |
Qualitative differences |
eng |
dc.subject |
Random tree |
eng |
dc.subject |
Subtrees |
eng |
dc.subject |
Upper-end |
eng |
dc.subject |
Asymptotic analysis |
eng |
dc.subject |
Binary trees |
eng |
dc.subject |
Trees (mathematics) |
eng |
dc.subject.ddc |
510 | Mathematik
|
ger |
dc.title |
On the subtree size profile of binary search trees |
|
dc.type |
Article |
|
dc.type |
Text |
|
dc.relation.issn |
0963-5483 |
|
dc.relation.doi |
https://doi.org/10.1017/S0963548309990630 |
|
dc.bibliographicCitation.issue |
4 |
|
dc.bibliographicCitation.volume |
19 |
|
dc.bibliographicCitation.firstPage |
561 |
|
dc.bibliographicCitation.lastPage |
578 |
|
dc.description.version |
publishedVersion |
|
tib.accessRights |
frei zug�nglich |
|