On a random search tree: asymptotic enumeration of vertices by distance from leaves

DOI10.1017/apr.2017.24zbMath1428.05005arXiv1412.2796OpenAlexW2964000676MaRDI QIDQ5233192

Miklós Bóna, Boris G. Pittel

Publication date: 16 September 2019

Published in: Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.2796

zbMATH Keywords

distributionenumerationrankasymptoticrootsearch treenumerical dataleaves

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15) Permutations, words, matrices (05A05) Combinatorial probability (60C05) Asymptotic enumeration (05A16) Structure theory of lattices (06B05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Central limit theorems for additive functionals and fringe trees in tries, Random plane increasing trees: Asymptotic enumeration of vertices by distance from leaves, \(k\)-protected vertices in unlabeled rooted plane trees, The lemniscate tree of a random polynomial, Limiting probabilities for vertices of a given rank in 1-2 trees

Cites Work

• Unnamed Item
• \(k\)-protected vertices in binary search trees
• Notes on protected nodes in digital search trees
• Moment of degeneration of a branching process and height of a random tree
• Asymptotic distribution of two-protected nodes in random binary search trees
• Protected nodes and fringe subtrees in some random trees
• Asymptotic fringe distributions for general families of random trees
• On growing random binary trees
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Asymptotic distribution of two-protected nodes in ternary search trees
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• Limit laws for local counters in random binary search trees
• Random Trees
• A note on the height of binary search trees
• Note on the heights of random recursive trees and random m‐ary search trees
• A local limit theorem for the number of nodes, the height, and the number of final leaves in a critical branching process tree
• Asymptotic Properties of Protected Nodes in Random Recursive Trees
• On 2-protected nodes in random digital trees