Width and mode of the profile for some random trees of logarithmic height

DOI10.1214/105051606000000187zbMATH Open1128.60008arXivmath/0607119OpenAlexW2111880296MaRDI 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

zbMATH Keywords

profilecentral momentswidthrandom recursive treesrandom search trees

Mathematics Subject Classification ID

Trees (05C05) Searching and sorting (68P10) Combinatorial probability (60C05)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• Singularity Analysis of Generating Functions
• Quad trees: A data structure for retrieval by composite keys
• The profile of binary search trees
• Asymptotic expansions for the Stirling numbers of the first kind
• Asymptotic Estimates of Stirling Numbers
• Title not available (Why is that?)
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• Cutting down recursive trees
• On the Altitude of Nodes in Random Trees
• Ignoring ignorance and agreeing to disagree
• Title not available (Why is that?)
• Analytic variations on quadtrees
• An Analysis of Randomd-Dimensional Quad Trees
• Hypergeometrics and the cost structure of quadtrees
• Profiles of random trees: correlation and width of random recursive trees and binary search trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Sums of Products of the Natural Numbers
• On a Conjecture of Hammersley
• On monotone functions of tree structures
• Universal Limit Laws for Depths in Random Trees
• Phase changes in random \(m\)-ary search trees and generalized quicksort
• Title not available (Why is that?)
• Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
• Profiles of random trees: plane-oriented recursive trees
• Distances in random plane-oriented recursive trees
• Title not available (Why is that?)
• DEPTH AND PATH LENGTH OF HEAP ORDERED TREES
• Title not available (Why is that?)
• More Combinatorial Properties of Certain Trees
• Martingales and large deviations for binary search trees
• On the joint distribution of the insertion path length and the number of comparisons in search trees
• Transitional behaviors of the average cost of quicksort with median-of-\((2t+1)\)
• Title not available (Why is that?)
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation

Cited In (14)

• 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)