Protected nodes and fringe subtrees in some random trees
From MaRDI portal
Publication:743079
DOI10.1214/ECP.V19-3048zbMATH Open1355.60015arXiv1310.0665MaRDI QIDQ743079FDOQ743079
Authors: Svante Janson, Luc Devroye 
Publication date: 22 September 2014
Published in: Electronic Communications in Probability (Search for Journal in Brave)
Abstract: We study protected nodes in various classes of random rooted trees by putting them in the general context of fringe subtrees introduced by Aldous (1991). Several types of random trees are considered: simply generated trees (or conditioned Galton-Watson trees), which includes several cases treated separately by other authors, binary search trees and random recursive trees. This gives unified and simple proofs of several earlier results, as well as new results.
Full work available at URL: https://arxiv.org/abs/1310.0665
Recommendations
- Asymptotic properties of protected nodes in random recursive trees
- Weakly protected nodes in random binary search trees
- Limit laws for functions of fringe trees for binary search trees and random recursive trees
- Protection number in plane trees
- Normal Limit Law for Protected Node Profile of Random Recursive Trees
Cited In (32)
- \(k\)-protected vertices in binary search trees
- Notes on protected nodes in digital search trees
- Protected points in \(k\)-ary trees
- Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
- Stochastic approximation on noncompact measure spaces and application to measure-valued Pólya processes
- Normal Limit Law for Protected Node Profile of Random Recursive Trees
- Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees
- Degree profile of \(m\)-ary search trees: a vehicle for data structure compression
- On the protected nodes in exponential recursive trees
- Protection number of recursive trees
- Protected vertices in Motzkin trees
- Enumeration of protected nodes in Motzkin trees
- On 2-protected nodes in random digital trees
- \(k\)-protected vertices in unlabeled rooted plane trees
- Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
- On a random search tree: asymptotic enumeration of vertices by distance from leaves
- Protected points in ordered trees
- Limiting probabilities for vertices of a given rank in 1-2 trees
- Central limit theorems for additive functionals and fringe trees in tries
- Weakly protected points in ordered trees
- Local limits of Galton–Watson trees conditioned on the number of protected nodes
- The distribution of the maximum protection number in simply generated trees
- Normal limiting distribution of the size of binary interval trees
- Asymptotic properties of protected nodes in random recursive trees
- Repeated fringe subtrees in random rooted trees
- Distinct fringe subtrees in random trees
- Asymptotic expectation of protected node profile in random digital search trees
- Protection numbers in simply generated trees and Pólya trees
- Protection number in plane trees
- Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
- Weakly protected nodes in random binary search trees
- Survival under random coverings of trees
This page was built for publication: Protected nodes and fringe subtrees in some random trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q743079)
