Speaker
Cecilia Holmgren
(INRIA Rocquencout)
Description
I will discuss the number of random records in an arbitrary
split tree
with n vertices (or equivalently,
the number of random cuttings required to eliminate the
tree). I will
explain how 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. After normalization
the distributions are shown to be asymptotically weakly
1-stable. This
work is a generalization of my earlier results for the
random binary
search tree, which is one specific case of split trees.
Other important
examples of split trees include m-ary search trees,
quadtrees, medians
of (2k+1)-trees, simplex trees, tries and digital
search trees.
