On the subtree size profile of binary search trees

Downloadstatistik des Dokuments (Auswertung nach 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

Version im Repositorium

Zum Zitieren der Version im Repositorium verwenden Sie bitte diesen DOI: https://doi.org/10.15488/2695

Zeitraum, für den die Download-Zahlen angezeigt werden:

Jahr: 
Monat: 

Summe der Downloads: 77




Kleine Vorschau
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

Verteilung der Downloads über den gewählten Zeitraum:

Herkunft der Downloads nach Ländern:

Pos. Land Downloads
Anzahl Proz.
1 image of flag of Germany Germany 30 38,96%
2 image of flag of United States United States 20 25,97%
3 image of flag of China China 9 11,69%
4 image of flag of Canada Canada 3 3,90%
5 image of flag of Spain Spain 2 2,60%
6 image of flag of Romania Romania 1 1,30%
7 image of flag of Portugal Portugal 1 1,30%
8 image of flag of New Zealand New Zealand 1 1,30%
9 image of flag of Ireland Ireland 1 1,30%
10 image of flag of Austria Austria 1 1,30%
    andere 8 10,39%

Weitere Download-Zahlen und Ranglisten:


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.