Profiles of random trees: correlation and width of random recursive trees and binary search trees

DOI10.1239/aap/1118858628zbMath1073.60006OpenAlexW2140003446MaRDI QIDQ5694147

Hsien-Kuei Hwang, Michael Drmota

Publication date: 29 September 2005

Published in: Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1239/aap/1118858628

zbMATH Keywords

correlation coefficientsrandom binary search treetotal path lengthsign-changes

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Analysis of variance and covariance (ANOVA) (62J10)

Related Items (15)

Limit Theorems for Subtree Size Profiles of Increasing Trees ⋮ Convergence in distribution of random metric measure spaces (\(\Lambda \)-coalescent measure trees) ⋮ Profile of random exponential binary trees ⋮ Canonical Trees, Compact Prefix-Free Codes, and Sums of Unit Fractions: A Probabilistic Analysis ⋮ Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication ⋮ Edgeworth expansions for profiles of lattice branching random walks ⋮ General Edgeworth expansions with applications to profiles of random trees ⋮ The degree profile of random Pólya trees ⋮ Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations ⋮ Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication ⋮ A functional limit theorem for the profile of search trees ⋮ The shape of unlabeled rooted random trees ⋮ A functional limit theorem for the profile of \(b\)-ary trees ⋮ Width and mode of the profile for some random trees of logarithmic height ⋮ Limit theorems for patterns in phylogenetic trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hopf-algebraic structure of families of trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• On the analysis of algorithms for trees
• Linear algorithms on recursive representations of trees
• Cutting down recursive trees
• The profile of binary search trees
• Asymptotic expansions for the Stirling numbers of the first kind
• Distribution of nodes of a tree by degree
• Trees, Forests and Rearranging
• On the efficiency of a new method of dictionary construction
• On Random Binary Trees
• Limiting Distributions for Path Lengths in Recursive Trees
• Singularity Analysis of Generating Functions
• A Probability Model of a Pyramid Scheme
• On the Expected Depth of Random Circuits
• Asymptotic Estimates of Elementary Probability Distributions
• On the covariance of the level sizes in random recursive trees
• Total Path Length for Random Recursive Trees
• Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
• More Combinatorial Properties of Certain Trees
• Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting

This page was built for publication: Profiles of random trees: correlation and width of random recursive trees and binary search trees