Width and mode of the profile for some random trees of logarithmic height
From MaRDI portal
Publication:997955
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.
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
- scientific article; zbMATH DE number 432810 (Why is no real title available?)
- scientific article; zbMATH DE number 4053643 (Why is no real title available?)
- scientific article; zbMATH DE number 3762080 (Why is no real title available?)
- scientific article; zbMATH DE number 19286 (Why is no real title available?)
- scientific article; zbMATH DE number 53861 (Why is no real title available?)
- scientific article; zbMATH DE number 3465322 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 2159647 (Why is no real title available?)
- scientific article; zbMATH DE number 1409903 (Why is no real title available?)
- 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)- Profile of random exponential recursive trees
- Almost sure asymptotic expansions for profiles of simply generated random trees
- Profiles of random trees: correlation and width of random recursive trees and binary search trees
- The expected profile of digital search trees
- On the asymptotic joint distribution of height and width in random trees
- scientific article; zbMATH DE number 1552322 (Why is no real title available?)
- The degree profile of random Pólya trees
- The profile of binary search trees
- A functional limit theorem for the profile of search trees
- The shape of unlabeled rooted random trees
- Profile of random exponential binary trees
- A functional limit theorem for the profile of \(b\)-ary trees
- Edgeworth expansions for profiles of lattice branching random walks
- General Edgeworth expansions with applications to profiles of random trees
- Branching random walks on binary search trees: convergence of the occupation measure
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)
