Distribution of distances in random binary search trees.
type: Item
instance of: scholarly article
title: Distribution of distances in random binary search trees.
zbMATH Open document ID: 1033.60007
author: Hosam M. Mahmoud
author: Ralph Neininger
published in: The Annals of Applied Probability
publication date: 2003-05-06T00:00:00Z
review text: The authors prove asymptotic normality for the depth of a randomly selected node and for the distance between two randomly selected nodes in a random binary search tree. They also establish logarithmic convergence rates w.r.t. the Zolotarev metric. The proof is based on the contraction method.
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 60F05
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 1906137
zbMATH Keywords: random trees
zbMATH Keywords: recurrence
zbMATH Keywords: fixed-point equation
zbMATH Keywords: contraction method
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1042765668
OpenAlex ID: W2125816608
cites work: Q4713980
cites work: Applications of the theory of records in the study of random trees
cites work: Universal Limit Laws for Depths in Random Trees
cites work: Q3807048
cites work: Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
cites work: Q3779735
cites work: Q4004056
cites work: Analytic variations on bucket selection and sorting
cites work: Probabilistic analysis of multiple quick select
cites work: On a multivariate contraction method for random recursive structures with applications to quicksort
cites work: Q4792912
cites work: Rates of convergence for Quicksort
cites work: Q3999495
cites work: Probability metrics and recursive algorithms
cites work: A limit theorem for “quicksort”
cites work: A fixed point theorem for distributions
cites work: On the analysis of stochastic divide and conquer algorithms
cites work: The contraction method for recursive algorithms
cites work: Randomized search trees
cites work: Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
DOI: 10.1214/AOAP/1042765668
description: scientific article; zbMATH DE number 1906137