Dependence and phase changes in random m‐ary search trees

DOI10.1002/rsa.20659zbMath1364.05023arXiv1501.05135OpenAlexW2149277300MaRDI QIDQ5739094

Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger, Hua-Huai Chern

Publication date: 2 June 2017

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

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

zbMATH Keywords

correlationasymptotic analysisrecurrence relationscontraction methoddependenceasymptotic transferlimit law\(m\)-ary search tree

Mathematics Subject Classification ID

Trees (05C05) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Distance in graphs (05C12)

Related Items (2)

Unnamed Item ⋮ Dependence between path-length and size in random digital trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the asymptotic internal path length and the asymptotic Wiener index of random Split trees
• The total path length of split trees
• The size of random fragmentation trees
• On the average internal path length of m-ary search trees
• Some average measures in m-ary search trees
• Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates
• A general limit theorem for recursive algorithms and combinatorial structures
• On the analysis of stochastic divide and conquer algorithms
• Distributional convergence for the number of symbol comparisons used by QuickSort
• A functional limit theorem for the profile of search trees
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Phase changes in randomm-ary search trees and generalized quicksort
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract)
• A weakly 1-stable distribution for the number of random records and cuttings in split trees
• Analysis of the space of search trees under the random insertion algorithm
• On the internal path length ofd-dimensional quad trees
• The Joint Distribution of Elastic Buckets in Multiway Search Trees
• m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
• Phase transition in a random fragmentation problem with applications to computer science
• Refined quicksort asymptotics
• A note on the quicksort asymptotics
• Transfer theorems and asymptotic distributional results for m‐ary search trees

This page was built for publication: Dependence and phase changes in random m‐ary search trees