Protected nodes and fringe subtrees in some random trees
From MaRDI portal
(Redirected from Publication:743079)
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.
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
(31)- On a random search tree: asymptotic enumeration of vertices by distance from leaves
- \(k\)-protected vertices in unlabeled rooted plane trees
- Weakly protected points in ordered trees
- \(k\)-protected vertices in binary search trees
- Asymptotic properties of protected nodes in random recursive trees
- Degree profile of \(m\)-ary search trees: a vehicle for data structure compression
- Asymptotic expectation of protected node profile in random digital search trees
- Protection number of recursive trees
- Notes on protected nodes in digital search trees
- Survival under random coverings of trees
- Stochastic approximation on noncompact measure spaces and application to measure-valued Pólya processes
- Protected vertices in Motzkin trees
- Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
- Local limits of Galton–Watson trees conditioned on the number of protected nodes
- Enumeration of protected nodes in Motzkin trees
- Central limit theorems for additive functionals and fringe trees in tries
- Protected points in ordered trees
- Protected points in \(k\)-ary trees
- On the protected nodes in exponential recursive trees
- Protection numbers in simply generated trees and Pólya trees
- Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
- Normal Limit Law for Protected Node Profile of Random Recursive Trees
- The distribution of the maximum protection number in simply generated trees
- Protection number in plane trees
- Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
- Normal limiting distribution of the size of binary interval trees
- Weakly protected nodes in random binary search trees
- Limiting probabilities for vertices of a given rank in 1-2 trees
- On 2-protected nodes in random digital trees
- Repeated fringe subtrees in random rooted trees
- Distinct fringe subtrees in random 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)
