The total path length of split trees
2012 (English)In: The Annals of Applied Probability, ISSN 1050-5164, Vol. 22, no 5, 1745-1777 p.Article in journal (Refereed) Published
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.
Research subject Mathematics
IdentifiersURN: urn:nbn:se:uu:diva-260484OAI: oai:DiVA.org:uu-260484DiVA: diva2:847296
FunderSwedish Research Council