uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A functional limit theorem for the profile of search trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2008 (English)In: The Annals of Applied Probability, ISSN 1050-5164, Vol. 18, no 1, 288-233 p.Article in journal (Refereed) Published
Abstract [en]

We study the profile X-n,X-k of random search trees including binary search trees and m-ary search trees. Our main result is a functional limit theorem of the normalized profile X-n,X-k/EXn,k for k = [alpha logn] in a certain range of alpha. A central feature of the proof is the use of the contraction method to prove convergence in distribution of certain random analytic functions in a complex domain. This is based on a general theorem concerning the contraction method for random variables in an infinite-dimensional Hilbert space. As part of the proof, we show that the Zolotarev metric is complete for a Hilbert space.

Place, publisher, year, edition, pages
2008. Vol. 18, no 1, 288-233 p.
Keyword [en]
functional limit theorem, search trees, profile of trees, random trees, analysis of algorithms
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-106265DOI: 10.1214/07-AAP457ISI: 000252750300012OAI: oai:DiVA.org:uu-106265DiVA: diva2:224358
Available from: 2009-06-17 Created: 2009-06-17 Last updated: 2010-01-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Department of Mathematics
In the same journal
The Annals of Applied Probability
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 410 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf