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
The total path length of split trees
Inria and Cambridge University.
2012 (English)In: The Annals of Applied Probability, ISSN 1050-5164, E-ISSN 2168-8737, Vol. 22, no 5, 1745-1777 p.Article in journal (Refereed) Published
Abstract [en]

We consider the model of random trees introduced by Devroye [SIAM J. Comput. 28 (1999) 409–432]. The model encompasses many important randomized algorithms and data structures. The pieces of data (items) are stored in a randomized fashion in the nodes of a tree. The total path length (sum of depths of the items) is a natural measure of the efficiency of the algorithm/data structure. Using renewal theory, we prove convergence in distribution of the total path length toward a distribution characterized uniquely by a fixed point equation. Our result covers, using a unified approach, many data structures such as binary search trees, m-ary search trees, quad trees, median-of-(2k+1) trees, and simplex trees.

Place, publisher, year, edition, pages
2012. Vol. 22, no 5, 1745-1777 p.
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-260484OAI: oai:DiVA.org:uu-260484DiVA: diva2:847296
Funder
Swedish Research Council
Available from: 2015-08-19 Created: 2015-08-19 Last updated: 2017-12-04

Open Access in DiVA

No full text

Authority records BETA

Holmgren, Cecilia

Search in DiVA

By author/editor
Holmgren, Cecilia
In the same journal
The Annals of Applied Probability
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 333 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