Random Records and Cuttings in Binary Search Trees

DOI10.1017/S096354830999068XzbMath1215.05162OpenAlexW2060679341MaRDI QIDQ3058297

Cecilia Holmgren

Publication date: 19 November 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s096354830999068x

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Limit theorems in probability theory (60F99)

Related Items

\(k\)-cut on paths and some trees, A modification of the random cutting model, Convergence of bi-measure \(\mathbb{R}\)-trees and the pruning process, Cutting Edges at Random in Large Recursive Trees, The \(k\)-cut model in deterministic and random trees, A weakly 1-stable distribution for the number of random records and cuttings in split trees, The total path length of split trees, The fluctuations of the giant cluster for percolation on random split trees, Cutting resilient networks -- complete binary trees, Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey, Inverting the cut-tree transform, The cut-tree of large recursive trees, Sizes of the largest clusters for supercritical percolation on random recursive trees

Cites Work

• Unnamed Item
• Unnamed Item
• The profile of binary search trees
• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• Random cutting and records in deterministic and random trees
• A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
• A note on the height of binary search trees
• Probability: A Graduate Course
• Quicksort asymptotics
• Cutting down random trees