Distribution of distances in random binary search trees.
From MaRDI portal
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.
Recommendations
Cites work
- A fixed point theorem for distributions
- A limit theorem for “quicksort”
- Analytic variations on bucket selection and sorting
- Applications of the theory of records in the study of random trees
- Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
- scientific article; zbMATH DE number 4041254 (Why is no real title available?)
- scientific article; zbMATH DE number 4074878 (Why is no real title available?)
- scientific article; zbMATH DE number 49698 (Why is no real title available?)
- scientific article; zbMATH DE number 53861 (Why is no real title available?)
- scientific article; zbMATH DE number 939772 (Why is no real title available?)
- scientific article; zbMATH DE number 1870234 (Why is no real title available?)
- On a multivariate contraction method for random recursive structures with applications to quicksort
- On the analysis of stochastic divide and conquer algorithms
- Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
- Probabilistic analysis of multiple quick select
- Probability metrics and recursive algorithms
- Randomized search trees
- Rates of convergence for Quicksort
- The contraction method for recursive algorithms
- Universal Limit Laws for Depths in Random Trees
Cited in
(31)- Limit laws for the Randić index of random binary tree models
- Normal limiting distribution of the size of binary interval trees
- Mixed Poisson approximation of node depth distributions in random binary search trees
- On weighted depths in random binary search trees
- Spanning tree size in random binary search trees.
- One-sided variations on binary search trees
- On the contraction method with degenerate limit equation.
- Maximal clades in random binary search trees
- Search trees: metric aspects and strong limit theorems
- Limiting theorems for the nodes in binary search trees
- Labels distance in bucket recursive trees with variable capacities of buckets
- Analysis of Steiner subtrees of random trees for traceroute algorithms
- Branching random walks on binary search trees: convergence of the occupation measure
- Limit theorems for depths and distances in weighted random b-ary recursive trees
- On the subtrees of random binary search trees
- Probabilities Related to Father-Son Distances in Binary Search Trees
- Retracted: Strong limiting behavior in binary search trees
- An almost sure result for path lengths in binary search trees
- On the distribution of distances in recursive trees
- scientific article; zbMATH DE number 852055 (Why is no real title available?)
- On a random search tree: asymptotic enumeration of vertices by distance from leaves
- The Wiener index of random digital trees
- The oscillatory distribution of distances in random tries
- Tree limits and limits of random trees
- The analysis of range quickselect and related problems
- Surrogate selection oversamples expanded T cell clonotypes
- Asymptotic distribution of two-protected nodes in random binary search trees
- Distances in random digital search trees
- The left-right-imbalance of binary search trees
- On the distribution of distances between specified nodes in increasing trees
- Deletions in random binary search trees: a story of errors
This page was built for publication: Distribution of distances in random binary search trees.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1872343)
