Random Records and Cuttings in Binary Search Trees

DOI10.1017/S096354830999068XzbMath1215.05162MaRDI 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

05C05: Trees

05C80: Random graphs (graph-theoretic aspects)

60F99: Limit theorems in probability theory

Related Items

The fluctuations of the giant cluster for percolation on random split trees, Cutting Edges at Random in Large Recursive Trees, A modification of the random cutting model, The total path length of split trees, Convergence of bi-measure \(\mathbb{R}\)-trees and the pruning process, 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, Inverting the cut-tree transform, The cut-tree of large recursive trees, \(k\)-cut on paths and some trees, Sizes of the largest clusters for supercritical percolation on random recursive trees, A weakly 1-stable distribution for the number of random records and cuttings in split 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