uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Random records and cuttings in split trees.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2008 (English)In: Discrete Mathematics & Theoretical Computer Science, ISSN 1462-7264, E-ISSN 1365-8050, Vol. Proc., no AI, 269-282 p.Article in journal (Refereed) Published
Abstract [en]

We study the number of records in split trees on n randomly labelled vertices. Equivalently the random number of cuttings 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, quad trees median of (2k+1)-trees, simplex trees, tries and digital search trees.

Place, publisher, year, edition, pages
2008. Vol. Proc., no AI, 269-282 p.
Keyword [en]
Random trees
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:uu:diva-288651OAI: oai:DiVA.org:uu-288651DiVA: diva2:924459
Conference
Fifth Colloquium on Mathematics and Computer Science
Available from: 2016-04-28 Created: 2016-04-28 Last updated: 2016-04-28

Open Access in DiVA

No full text

By organisation
Department of Mathematics
In the same journal
Discrete Mathematics & Theoretical Computer Science
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 25 hits
ReferencesLink to record
Permanent link

Direct link