THE TOTAL PATH LENGTH OF SPLIT TREES

被引：10

作者：

Broutin, Nicolas ^{[1
]}

Holmgren, Cecilia ^{[1
]}

机构：

[1] Univ Cambridge, Cambridge CB2 1TN, England

来源：

ANNALS OF APPLIED PROBABILITY | 2012年 / 22卷 / 05期

关键词：

Random tree; path length; data structure; limit distribution; SEARCH-TREES; LIMITING DISTRIBUTION; WEIGHTED HEIGHT; RANDOM RECORDS; THEOREM; CUTTINGS; NUMBER; SPACE;

D O I：

10.1214/11-AAP812

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

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.

引用

页码：1745 / 1777

页数：33

共 50 条

[1] Split Trees - A Unifying Model for Many Important Random Trees of Logarithmic Height: A Brief Survey
Holmgren, Cecilia
DISCRETE GEOMETRY AND MATHEMATICAL MORPHOLOGY, DGMM 2021, 2021, 12708 : 20 - 57
[2] Inversions in Split Trees and Conditional Galton-Watson Treest
Cai, Xing Shi
Holmgren, Cecilia
Janson, Svante
Johansson, Tony
Skerman, Fiona
COMBINATORICS PROBABILITY & COMPUTING, 2019, 28 (03) : 335 - 364
[3] A note on the expected path length of trees with known fringe
DePrisco, R
Parlati, G
Persiano, G
INFORMATION PROCESSING LETTERS, 1996, 59 (06) : 309 - 315
[4] A NOTE ON THE PATH-LENGTH OF RED BLACK TREES
CAMERON, H
WOOD, D
INFORMATION PROCESSING LETTERS, 1992, 42 (05) : 287 - 292
[5] The fluctuations of the giant cluster for percolation on random split trees
Ojeda, Gabriel Berzunza
Cai, Xing Shi
Holmgren, Cecilia
ALEA-LATIN AMERICAN JOURNAL OF PROBABILITY AND MATHEMATICAL STATISTICS, 2022, 19 (01): : 665 - 700
[6] A q-analogue of the path length of binary search trees
Prodinger, H
ALGORITHMICA, 2001, 31 (03) : 433 - 441
[7] On the Number of t-Ary Trees with a Given Path Length
Gadiel Seroussi
Algorithmica, 2006, 46 : 557 - 565
[8] On the number of t-ary trees with a given path length
Seroussi, Gadiel
ALGORITHMICA, 2006, 46 (3-4) : 557 - 565
[9] ON THE EXTERNAL PATH LENGTH OF RANDOM RECURSIVE k-ARY TREES
Javanian, Mehri
ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2013, (31): : 21 - 26
[10] TIGHT UPPER AND LOWER BOUNDS ON THE PATH-LENGTH OF BINARY-TREES
DESANTIS, A
PERSIANO, G
SIAM JOURNAL ON COMPUTING, 1994, 23 (01) : 12 - 23

← 1 2 3 4 5 →