Asymptotic variance of random symmetric digital search trees

zbMath1278.68080arXiv1001.0095MaRDI QIDQ3575480

Hsien-Kuei Hwang, Michael Fuchs, Vytas Zacharovas

Publication date: 27 July 2010

Full work available at URL: https://arxiv.org/abs/1001.0095

zbMATH Keywords

Laplace transformMellin transformdigital search treessaddle-point methodpoissonizationcolless indexPoisson generating functionsweighted path-length

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Data structures (68P05)

Related Items (15)

Normal Limit Law for Protected Node Profile of Random Recursive Trees ⋮ Approximate counting with \(m\) counters: a probabilistic analysis ⋮ The Depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace ⋮ Node profiles of symmetric digital search trees: Concentration properties ⋮ A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries ⋮ On the variety of shapes in digital trees ⋮ Notes on protected nodes in digital search trees ⋮ Approximate counting with \(m\) counters: A detailed analysis ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ From coin tossing to rock-paper-scissors and beyond: a log-exp gap theorem for selecting a leader ⋮ Dependence between path-length and size in random digital trees ⋮ On 2-protected nodes in random digital trees ⋮ Words with a generalized restricted growth property ⋮ A binomial splitting process in connection with corner parking problems ⋮ The Wiener Index of Random Digital Trees

This page was built for publication: Asymptotic variance of random symmetric digital search trees