Exact and asymptotic distributions in digital and binary search trees

DOI10.1051/ITA/1987210404791zbMATH Open0643.68077OpenAlexW46381831MaRDI QIDQ3785960FDOQ3785960

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximate counting: a detailed analysis
• Digital Search Trees Revisited
• Title not available (Why is that?)
• Paths in a random digital tree: limiting distributions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Brownian motion and algorithm complexity
• A probabilistic analysis of the height of tries and of the complexity of triesort
• Title not available (Why is that?)
• On Random Binary Trees
• On the analysis of algorithms for trees

Cited In (26)

• Renewals for exponentially increasing lifetimes, with an application to digital search trees
• On random cartesian trees
• Support and density of the limit \(m\)-ary search trees distribution
• Asymptotic variance of random symmetric digital search trees
• Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis
• 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
• The left-right-imbalance of binary search trees
• Approximate counting with \(m\) counters: a probabilistic analysis
• 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)