THE TOTAL PATH LENGTH OF SPLIT TREES

• 成果类型: Article
• 署名作者: Broutin, Nicolas; Holmgren, Cecilia
• 署名单位: University of Cambridge
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/11-AAP812
• 发表日期: 2012
• 页码: 1745-1777
• 关键词: search-trees; LIMITING DISTRIBUTION; weighted height; random records; THEOREM; cuttings; number; SPACE

摘要

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.