A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries

zbMath1300.68021MaRDI QIDQ405180

Michael Fuchs, Chung-Kuei Lee

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p69

zbMATH Keywords

momentsWiener indexdigital treesmultivariate limit lawsnodes of fixed out-degreetotal path length

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items

On the variety of shapes in digital trees ⋮ Asymptotic normality for the size of graph tries built from M-ary tree labelings ⋮ Dependence between path-length and size in random digital trees ⋮ On 2-protected nodes in random digital trees ⋮ The Wiener Index of Random Digital Trees

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• On the variance of a class of inductive valuations of data structures for digital search
• Analytical depoissonization and its applications
• A general limit theorem for recursive algorithms and combinatorial structures
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Dynamical sources in information theory: A general analysis of trie structures
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Size and path length of Patricia tries: Dynamical sources context
• A Generalisation of Stirling's Formula.
• Asymptotic variance of random symmetric digital search trees
• Profiles of Tries
• A multivariate view of random bucket digital search trees
• The Variance of the Number of 2-Protected Nodes in a Trie
• The Wiener Index of Random Digital Trees

This page was built for publication: A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries