Change search
ReferencesLink to record
Permanent link

Direct link
Asymptotic distribution of two-protected nodes in ternary search trees
Stockholm University, Faculty of Science, Department of Mathematics.
Uppsala universitet, Sweden.
2015 (English)In: Electronic Journal of Probability, 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 Pólya 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 Pólya 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≤26.

Place, publisher, year, edition, pages
2015. Vol. 20, 9
Keyword [en]
Random trees; Polya urns; Normal limit laws; M-ary search trees
National Category
URN: urn:nbn:se:su:diva-114313DOI: 10.1214/EJP.v20-3577ISI: 000350287500001OAI: diva2:791153
Available from: 2015-02-26 Created: 2015-02-26 Last updated: 2015-04-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Holmgren, Cecilia
By organisation
Department of Mathematics
In the same journal
Electronic Journal of Probability

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: 23 hits
ReferencesLink to record
Permanent link

Direct link