Random Records and Cuttings in Binary Search Trees
2010 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 19, no 3, 391-424 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2010. Vol. 19, no 3, 391-424 p.
Research subject Mathematics
IdentifiersURN: urn:nbn:se:uu:diva-112233DOI: 10.1017/S096354830999068XISI: 000277473600004OAI: oai:DiVA.org:uu-112233DiVA: diva2:285445