DOAJ Open Access 2008

Random Records and Cuttings in Split Trees: Extended Abstract

Cecilia Holmgren

Lihat Sumber DOI

Abstrak

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.

Topik & Kata Kunci

Mathematics

Penulis (1)

Cecilia Holmgren

Format Sitasi

APA MLA BibTeX

Holmgren, C. (2008). Random Records and Cuttings in Split Trees: Extended Abstract. https://doi.org/10.46298/dmtcs.3570

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.3570

Informasi Jurnal

Tahun Terbit: 2008
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.3570
Akses: Open Access ✓