The total path length of split trees

• DOI: 10.1214/11-aap812
• Publication Date: 2012-10-31T14:18:50Z
• Authors: Nicolas Broutin; Cecilia Holmgren
• Keywords: FOS: Computer and information sciences; [MATH.MATH-PR] Mathematics [math]/Probability [math.PR]; [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]; [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]; data structure; 0102 computer and information sciences; 01 natural sciences; 05C05; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; Computer Science - Data Structures and Algorithms; FOS: Mathematics; 60C05; Mathematics - Combinatorics; Data Structures and Algorithms (cs.DS); 0101 mathematics; limit distribution; Probability (math.PR); Random tree; 68P05; [MATH.MATH-PR]Mathematics [math]/Probability [math.PR]; [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]; path length; Combinatorics (math.CO); Mathematics - Probability

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.<br/>Published in at http://dx.doi.org/10.1214/11-AAP812 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)<br/>