Random Records and Cuttings in Split Trees: Extended Abstract

DMTCS Proceedings, Fifth Colloquium on Mathematics and Computer Science

Random Records and Cuttings in Split Trees: Extended Abstract

Cecilia Holmgren

Abstract

We study the number of records in random split trees on n randomly labelled vertices. Equivalently the number of random cuttings required to eliminate an arbitrary random split tree can be studied. After normalization the distributions are shown to be asymptotically 1-stable. This work is a generalization of our 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, median of (2k+1)-trees, simplex trees, tries and digital search trees.

Full Text: GZIP Compressed PostScript PostScript PDF