Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T06:33:37.276Z Has data issue: false hasContentIssue false

A weakly 1-stable distribution for the number of random records and cuttings in split trees

Published online by Cambridge University Press:  01 July 2016

Cecilia Holmgren*
Affiliation:
Uppsala University
*
∗ Current address: Algorithms Project, INRIA Rocquencourt, F-78153 Le Chesnay, France. Email address: cecilia@math.uu.se
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we study the number of random records in an arbitrary split tree (or, equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for the convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree in Holmgren (2010), which is one specific case of split trees. Other important examples of split trees include m-ary search trees, quad trees, medians of (2k + 1)-trees, simplex trees, tries, and digital search trees.

Information

Type
General Applied Probability
Copyright
Copyright © Applied Probability Trust 2011