On the subtree size profile of binary search trees

Download statistics - Document (COUNTER):

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

Repository version

To cite the version in the repository, please use this identifier: https://doi.org/10.15488/2695

Selected time period:

year: 
month: 

Sum total of downloads: 43




Thumbnail
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.
License of this version: 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.
Document Type: article
Publishing status: publishedVersion
Issue Date: 2010
Appears in Collections:Fakultät für Mathematik und Physik

distribution of downloads over the selected time period:

downloads by country:

pos. country downloads
total perc.
1 image of flag of Germany Germany 26 60.47%
2 image of flag of United States United States 4 9.30%
3 image of flag of China China 3 6.98%
4 image of flag of Canada Canada 3 6.98%
5 image of flag of Spain Spain 2 4.65%
6 image of flag of Ukraine Ukraine 1 2.33%
7 image of flag of Romania Romania 1 2.33%
8 image of flag of Portugal Portugal 1 2.33%
9 image of flag of Hungary Hungary 1 2.33%
10 image of flag of United Kingdom United Kingdom 1 2.33%

Further download figures and rankings:


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.

Search the repository


Browse