Martingales and Profile of Binary Search Trees
By Brigitte Chauvin, Thierry Klein, Jean-François Marckert, A. Rouault. 2004
65 citations recorded by the source corpus.
We are interested in the asymptotic analysis of the binary search tree (BST) under the random permutation model. Via an embedding in a continuous time model, we get new results, in particular the asymptotic behavior of the profile.
Subfields: Artificial Intelligence, Mathematical Physics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/5d60076a4d1d0dd530d1152e94eb8eb8e0441178
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- David J. Aldous
- Svante Janson
- Antar Bandyopadhyay
- Cecilia Holmgren
- Johan Wästlund
- Gerold Alsmeyer
- M. Meiners
In Mathematical Physics
- Cecilia Holmgren
- David J. Aldous
- Svante Janson
- Antar Bandyopadhyay
- Grégory Miermont
- Robin Pemantle
- Charles Bordenave
- Remco van der Hofstad
In Statistics and Probability
- Cecilia Holmgren
- David J. Aldous
- Svante Janson
- Antar Bandyopadhyay
- Johan Wästlund
- Robin Pemantle
- Charles Bordenave
- Philippe Flajolet
Citations in the corpus
- A survey of max-type recursive distributional equations (2004, background): “When an RDE depends on a parameter (e.g., our (77) and (96); see also examples involving multiplicative martingales for branching processes, e.g., [ 23 ], Theorem 3.3), it is natural to ask whether the solution depends continuously on the parameter.”
- Fringe trees, Crump-Mode-Jagers branching processes and $m$-ary search trees (2016, result): “More precise results (obtained by other methods) are given by [27], [28], [48], [40], [56], [49] and [44, Section 6.”