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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Asymptotic distribution of two-protected nodes in ternary search trees
Stockholms universitet.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
2015 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 20, 9Article in journal (Refereed) Published
Abstract [en]

We study protected nodes in m-ary search trees, by putting them in context of generalised Polya urns. We show that the number of two-protected nodes (the nodes that are neither leaves nor parents of leaves) in a random ternary search tree is asymptotically normal. The methods apply in principle to m-ary search trees with larger m as well, although the size of the matrices used in the calculations grow rapidly with m; we conjecture that the method yields an asymptotically normal distribution for all m <= 26. The one-protected nodes, and their complement, i.e., the leaves, are easier to analyze. By using a simpler Polya urn (that is similar to the one that has earlier been used to study the total number of nodes in m-ary search trees), we prove normal limit laws for the number of one-protected nodes and the number of leaves for all m <= 2 6

Place, publisher, year, edition, pages
2015. Vol. 20, 9
Keyword [en]
Random trees, Polya urns, Normal limit laws, M-ary search trees
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:uu:diva-248462DOI: 10.1214/EJP.v20-3577ISI: 000350287500001OAI: oai:DiVA.org:uu-248462DiVA: diva2:799663
Funder
Swedish Research Council
Available from: 2015-03-31 Created: 2015-03-30 Last updated: 2017-12-04

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Holmgren, CeciliaJanson, Svante

Search in DiVA

By author/editor
Holmgren, CeciliaJanson, Svante
By organisation
Analysis and Probability Theory
In the same journal
Electronic Journal of Probability
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 396 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf