A functional limit theorem for the profile of search trees
From MaRDI portal
Publication:2476407
Abstract: We study the profile of random search trees including binary search trees and -ary search trees. Our main result is a functional limit theorem of the normalized profile for in a certain range of . A central feature of the proof is the use of the contraction method to prove convergence in distribution of certain random analytic functions in a complex domain. This is based on a general theorem concerning the contraction method for random variables in an infinite-dimensional Hilbert space. As part of the proof, we show that the Zolotarev metric is complete for a Hilbert space.
The level profile of a tree, as examined in this paper, is the sequence of numbers each counting the number of nodes with the same distance from the root. This parameter is a very informative shape parameter, useful for many purposes. The authors derive a functional limit law of the form \[ \frac{X_{n,\lfloor \alpha\log n\rfloor}} {E(X_{n,\lfloor \alpha\log n\rfloor})} \to X(\alpha), \] for the profile \(X_{n,k}\) of a class of trees called the generalized \(m\)-ary search trees. Many deep tools are developed for achieving this, which are of independent interest \textit{per se}.
Recommendations
Cites work
- A general limit theorem for recursive algorithms and combinatorial structures
- An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
- Analytic combinatorics
- Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
- Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
- Connecting Yule process, bisection and binary search tree via martingales
- Estimates of the Distance between Sums of Independent Random Elements in Banach Spaces
- scientific article; zbMATH DE number 1713116 (Why is no real title available?)
- scientific article; zbMATH DE number 4034749 (Why is no real title available?)
- scientific article; zbMATH DE number 3673252 (Why is no real title available?)
- scientific article; zbMATH DE number 3738047 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 53861 (Why is no real title available?)
- scientific article; zbMATH DE number 3548141 (Why is no real title available?)
- scientific article; zbMATH DE number 1022519 (Why is no real title available?)
- scientific article; zbMATH DE number 3272562 (Why is no real title available?)
- scientific article; zbMATH DE number 3274494 (Why is no real title available?)
- Ideal Metrics in the Problem of Approximating Distributions of Sums of Independent Random Variables
- Martingales and profile of binary search trees
- More Combinatorial Properties of Certain Trees
- Orthogonal decompositions and functional limit theorems for random graph statistics
- Profiles of random trees: correlation and width of random recursive trees and binary search trees
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- Profiles of random trees: Plane-oriented recursive trees
- Singularity Analysis of Generating Functions
- The density of the ISE and local limit laws for embedded trees
- The profile of binary search trees
- The random multisection problem, travelling waves and the distribution of the height of m-ary search trees
- Transitional behaviors of the average cost of quicksort with median-of-\((2t+1)\)
- Weak convergence of probability measures and random functions in the function space D[0,∞)
- Width and mode of the profile for some random trees of logarithmic height
Cited in
(32)- Edgeworth expansions for profiles of lattice branching random walks
- General Edgeworth expansions with applications to profiles of random trees
- Process convergence for the complexity of radix selection on Markov sources
- Refined asymptotics for the composition of cyclic urns
- A functional limit theorem for the profile of random recursive trees
- The profile of binary search trees
- Limit theorems for patterns in phylogenetic trees
- On a functional contraction method
- Long and short paths in uniform random recursive dags
- Heavy tailed solutions of multivariate smoothing transforms
- Search trees: metric aspects and strong limit theorems
- Limit laws for functions of fringe trees for binary search trees and random recursive trees
- Continuous-time digital search tree and a border aggregation model
- Limit theorems for subtree size profiles of increasing trees
- Support and density of the limit m-ary search trees distribution
- Pólya urns via the contraction method
- Higher moments of Banach space valued random variables
- Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations
- A limit process for partial match queries in random quadtrees and 2-d trees
- The degree profile of random Pólya trees
- Weak convergence of the number of vertices at intermediate levels of random recursive trees
- On the subtree size profile of binary search trees
- Refined quicksort asymptotics
- Transfer theorems and asymptotic distributional results for m‐ary search trees
- Shape measures of random increasing k-trees
- A repertoire for additive functionals of uniformly distributed m-ary search trees
- Dependence and phase changes in random m-ary search trees
- On martingale tail sums for the path length in random trees
- Partial match queries in random quadtrees
- A caveat on metrizing convergence in distribution on Hilbert spaces
- Profiles of random trees: Limit theorems for random recursive trees and binary search trees
- A functional limit theorem for the profile of \(b\)-ary trees
This page was built for publication: A functional limit theorem for the profile of search trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476407)
