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 (13)

\(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

This page was built for publication: Random Records and Cuttings in Binary Search Trees