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
Zusammenfassung: | |
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. | |
Lizenzbestimmungen: | 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. |
Publikationstyp: | Article |
Publikationsstatus: | publishedVersion |
Erstveröffentlichung: | 2010 |
Die Publikation erscheint in Sammlung(en): | Fakultät für Mathematik und Physik |
Pos. | Land | Downloads | ||
---|---|---|---|---|
Anzahl | Proz. | |||
1 | Germany | 30 | 38,96% | |
2 | United States | 20 | 25,97% | |
3 | China | 9 | 11,69% | |
4 | Canada | 3 | 3,90% | |
5 | Spain | 2 | 2,60% | |
6 | Romania | 1 | 1,30% | |
7 | Portugal | 1 | 1,30% | |
8 | New Zealand | 1 | 1,30% | |
9 | Ireland | 1 | 1,30% | |
10 | Austria | 1 | 1,30% | |
andere | 8 | 10,39% |
Hinweis
Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.