Width and mode of the profile for some random trees of logarithmic height
From MaRDI portal
Publication:997955
DOI10.1214/105051606000000187zbMATH Open1128.60008OpenAlexW2111880296MaRDI QIDQ997955FDOQ997955
Authors: Hsien-Kuei Hwang, Luc Devroye 
Publication date: 8 August 2007
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Abstract: We propose a new, direct, correlation-free approach based on central moments of profiles to the asymptotics of width (size of the most abundant level) in some random trees of logarithmic height. The approach is simple but gives precise estimates for expected width, central moments of the width and almost sure convergence. It is widely applicable to random trees of logarithmic height, including recursive trees, binary search trees, quad trees, plane-oriented ordered trees and other varieties of increasing trees.
Full work available at URL: https://arxiv.org/abs/math/0607119
Recommendations
- Profiles of random trees: correlation and width of random recursive trees and binary search trees
- Profiles of random trees: Plane-oriented recursive trees
- Profiles of random trees: plane-oriented recursive trees
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- The profile of binary search trees
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Analysis of Randomd-Dimensional Quad Trees
- An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
- Analytic combinatorics
- Analytic variations on quadtrees
- Asymptotic Estimates of Stirling Numbers
- Asymptotic expansions for the Stirling numbers of the first kind
- Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
- Cutting down recursive trees
- DEPTH AND PATH LENGTH OF HEAP ORDERED TREES
- Distances in random plane-oriented recursive trees
- Hypergeometrics and the cost structure of quadtrees
- Ignoring ignorance and agreeing to disagree
- Martingales and large deviations for binary search trees
- More Combinatorial Properties of Certain Trees
- On a Conjecture of Hammersley
- On monotone functions of tree structures
- On the Altitude of Nodes in Random Trees
- On the Most Probable Shape of a Search Tree Grown from a Random Permutation
- On the joint distribution of the insertion path length and the number of comparisons in search trees
- Phase changes in random \(m\)-ary search trees and generalized quicksort
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- Profiles of random trees: correlation and width of random recursive trees and binary search trees
- Profiles of random trees: plane-oriented recursive trees
- Quad trees: A data structure for retrieval by composite keys
- Singularity Analysis of Generating Functions
- The Sums of Products of the Natural Numbers
- The profile of binary search trees
- Transitional behaviors of the average cost of quicksort with median-of-\((2t+1)\)
- Universal Limit Laws for Depths in Random Trees
Cited In (15)
- Almost sure asymptotic expansions for profiles of simply generated random trees
- The shape of unlabeled rooted random trees
- Edgeworth expansions for profiles of lattice branching random walks
- The expected profile of digital search trees
- Title not available (Why is that?)
- Profiles of random trees: correlation and width of random recursive trees and binary search trees
- The profile of binary search trees
- Branching random walks on binary search trees: convergence of the occupation measure
- A functional limit theorem for the profile of search trees
- A functional limit theorem for the profile of \(b\)-ary trees
- The degree profile of random Pólya trees
- Profile of random exponential recursive trees
- Profile of random exponential binary trees
- General Edgeworth expansions with applications to profiles of random trees
- On the asymptotic joint distribution of height and width in random trees
This page was built for publication: Width and mode of the profile for some random trees of logarithmic height
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q997955)
