Distribution of distances in random binary search trees.

DOI10.1214/aoap/1042765668zbMath1033.60007OpenAlexW2125816608MaRDI QIDQ1872343

Hosam M. Mahmoud, Ralph Neininger

Publication date: 6 May 2003

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1042765668

zbMATH Keywords

recurrencecontraction methodfixed-point equationrandom trees

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Trees (05C05) Combinatorial probability (60C05) Data structures (68P05)

Related Items (19)

Tree limits and limits of random trees ⋮ Spanning tree size in random binary search trees. ⋮ One-sided variations on binary search trees ⋮ On the contraction method with degenerate limit equation. ⋮ Distances in random digital search trees ⋮ Labels distance in bucket recursive trees with variable capacities of buckets ⋮ Retracted: Strong limiting behavior in binary search trees ⋮ The analysis of range quickselect and related problems ⋮ Limiting theorems for the nodes in binary search trees ⋮ On the distribution of distances between specified nodes in increasing trees ⋮ Deletions in random binary search trees: a story of errors ⋮ The oscillatory distribution of distances in random tries ⋮ Mixed Poisson approximation of node depth distributions in random binary search trees ⋮ Analysis of Steiner subtrees of random trees for traceroute algorithms ⋮ On weighted depths in random binary search trees ⋮ Branching random walks on binary search trees: convergence of the occupation measure ⋮ Limit laws for the Randić index of random binary tree models ⋮ Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees ⋮ The Wiener Index of Random Digital Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Applications of the theory of records in the study of random trees
• A fixed point theorem for distributions
• Probabilistic analysis of multiple quick select
• Analytic variations on bucket selection and sorting
• The contraction method for recursive algorithms
• On the analysis of stochastic divide and conquer algorithms
• Randomized search trees
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
• Universal Limit Laws for Depths in Random Trees
• Rates of convergence for Quicksort
• Probability metrics and recursive algorithms
• A limit theorem for “quicksort”

This page was built for publication: Distribution of distances in random binary search trees.