Random records and cuttings in complete binary trees
From MaRDI portal
A rooted complete binary tree with \(n\) vertices is successively reduced by cutting off the part descending from a randomly selected vertex. Let \(X\) be the number of cuts required to eliminate the tree. The normalized distribution of \(X\) is investigated and shown to be asymptotically similar to a 1-stable distribution with some periodic fluctuations. For the entire collection see [Zbl 1047.68003].
Recommendations
- Random records and cuttings in binary search trees
- Random cutting and records in deterministic and random trees
- scientific article; zbMATH DE number 6683495
- Applications of the theory of records in the study of random trees
- Random sequential bisection and its associated binary tree
- Random binary trees. Algorithms, asymptotics and statistics
- On the total heights of random rooted binary trees
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- On the subtrees of random binary search trees
Cited in
(19)- Applications of the theory of records in the study of random trees
- Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
- The \(k\)-cut model in deterministic and random trees
- Cutting resilient networks -- complete binary trees
- The cut-tree of large recursive trees
- Asymptotic results concerning the total branch length of the Bolthausen-Sznitman coalescent
- \(k\)-cut on paths and some trees
- Fluctuations for the number of records on subtrees of the continuum random tree
- scientific article; zbMATH DE number 6683495 (Why is no real title available?)
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- Random records and cuttings in binary search trees
- On moment sequences and mixed Poisson distributions
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- Cutting down trees with a Markov chainsaw
- The fluctuations of the giant cluster for percolation on random split trees
- A note on the asymptotic expansion of the Lerch's transcendent
- Cutting edges at random in large recursive trees
- A modification of the random cutting model
- Quenched worst-case scenario for root deletion in targeted cutting of random recursive trees
This page was built for publication: Random records and cuttings in complete binary trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3154684)
