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

Direct link
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
URN: urn:nbn:se:uu:diva-248462DOI: 10.1214/EJP.v20-3577ISI: 000350287500001OAI: oai:DiVA.org:uu-248462DiVA: diva2:799663
Swedish Research Council
Available from: 2015-03-31 Created: 2015-03-30 Last updated: 2016-02-17

Open Access in DiVA

No full text

Other links

Publisher's full text

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
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

Altmetric score

Total: 208 hits
ReferencesLink to record
Permanent link

Direct link