Exact and asymptotic distributions in digital and binary search trees

DOI10.1051/ITA/1987210404791MaRDI QIDQ3785960zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3829247 (Why is no real title available?)
• scientific article; zbMATH DE number 3961005 (Why is no real title available?)
• scientific article; zbMATH DE number 3978406 (Why is no real title available?)
• scientific article; zbMATH DE number 3755865 (Why is no real title available?)
• scientific article; zbMATH DE number 3536107 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• scientific article; zbMATH DE number 3338262 (Why is no real title available?)
• A probabilistic analysis of the height of tries and of the complexity of triesort
• Approximate counting: a detailed analysis
• Brownian motion and algorithm complexity
• Digital Search Trees Revisited
• On Random Binary Trees
• On the analysis of algorithms for trees
• Paths in a random digital tree: limiting distributions

Cited in

(26)

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

This page was built for publication: Exact and asymptotic distributions in digital and binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785960)