Exact and asymptotic distributions in digital and binary search trees

DOI10.1051/ita/1987210404791zbMath0643.68077OpenAlexW46381831MaRDI QIDQ3785960

Guy Louchard

Publication date: 1987

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92296

zbMATH Keywords

binary search treesdigital search treeCombinatorial relations

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorial identities, bijective combinatorics (05A19)

Related Items

Universality of critical behaviour in a class of recurrent random walks, Approximate counting with \(m\) counters: a probabilistic analysis, Distances in random digital search trees, On random cartesian trees, Rounding of continuous random variables and oscillatory asymptotics, The left-right-imbalance of binary search trees, Node profiles of symmetric digital search trees: Concentration properties, Asymptotic expectation of protected node profile in random digital search trees, Renewals for exponentially increasing lifetimes, with an application to digital search trees, Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis, Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees, On the variance of a class of inductive valuations of data structures for digital search, Martingales and large deviations for binary search trees, A limiting distribution for quicksort, The expected profile of digital search trees, Distinctness of compositions of an integer: A probabilistic analysis, Mixed Poisson approximation of node depth distributions in random binary search trees, Probabilistic analysis of adaptative sampling, Branching random walks on binary search trees: convergence of the occupation measure, Universal Limit Laws for Depths in Random Trees, The height of a binary search tree: the limiting distribution perspective., Analytic variations on quadtrees

Cites Work

• A probabilistic analysis of the height of tries and of the complexity of triesort
• Approximate counting: a detailed analysis
• Brownian motion and algorithm complexity
• On the analysis of algorithms for trees
• On Random Binary Trees
• Paths in a random digital tree: limiting distributions
• Digital Search Trees Revisited
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item