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

Direct link
The total path length of split trees
Inria and Cambridge University.
2012 (English)In: The Annals of Applied Probability, ISSN 1050-5164, 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
Research subject
URN: urn:nbn:se:uu:diva-260484OAI: oai:DiVA.org:uu-260484DiVA: diva2:847296
Swedish Research Council
Available from: 2015-08-19 Created: 2015-08-19 Last updated: 2015-08-19

Open Access in DiVA

No full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 154 hits
ReferencesLink to record
Permanent link

Direct link