Random Records and Cuttings in Binary Search Trees

• We study the number of random records in a  binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.

Ämnesord

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Nyckelord

Discrete mathematics

Diskret matematik

Mathematics

Matematik

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)