Transfer theorems and asymptotic distributional results for m‐ary search trees

DOI10.1002/rsa.20039zbMath1101.68018arXivmath/0306050OpenAlexW2952861789MaRDI QIDQ5311895

Nevin Kapur, James Allen Fill

Publication date: 29 August 2005

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

additive functionalslimit distributionrandom permutation modeltransfer theorems\(m\)-ary search treesEuler differential equationindicial polynomial

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (13)

Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees ⋮ Phase transition in a generalized Eden growth model on a tree ⋮ On the variety of shapes in digital trees ⋮ On densities for solutions to stochastic fixed point equations ⋮ On the Variety of Shapes on the Fringe of a Random Recursive Tree ⋮ The size of random fragmentation trees ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ Dependence and phase changes in random m‐ary search trees ⋮ Singularity analysis, Hadamard products, and tree recurrences ⋮ Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees ⋮ The sum of powers of subtree sizes for conditioned Galton-Watson trees ⋮ Functional limit theorems for multitype branching processes and generalized Pólya urns. ⋮ A note on the quicksort asymptotics

Cites Work

• Unnamed Item
• Unnamed Item
• Multiway Trees of Maximum and Minimum Probability under the Random Permutation Model
• Inequalities: theory of majorization and its applications

This page was built for publication: Transfer theorems and asymptotic distributional results for m‐ary search trees